In the coming years, quantum computers are expected to go beyond what is possible with classical computers. This could apply to the study of complex systems, manifesting themselves in everything from our brains to the electrical grid, often pushing the capabilities of supercomputers when simulated.
The first complexity analysis using a quantum computer has now been achieved by a team of scientists, including two from the National Renewable Energy Laboratory (NREL), who have implemented cellular quantum automata on a 23-qubit quantum computer. Her article “Small-World Complex Network Generation on a Digital Quantum Processor” was published in the journal nature communication.
Physical complexity occurs throughout nature and is indicated by qualities such as spontaneous pattern formation and self-organization. For example, researchers at NREL encounter complexities in areas such as nanoscale materials and urban infrastructure. But, true to the name, complexity can be difficult to study. Scientists expect that quantum computers, which use a fundamentally different way of calculating than classical computers, could also represent complexity in a fundamentally different, more useful way. This publication showed that complexity can indeed be simulated on a quantum computer – a first for the field and an important step towards future complexity analysis.
While simulating a brain is certainly not an option in these early days of quantum computing, complexity can still emerge from relatively simple algorithms. For this study, the authors turned to cellular automata, a class of elementary rules known to generate lifelike systems. The question for the research team was: can a quantum version of cellular automata represent complexity on a quantum computer?
Structure for simplicity
Cellular automata are an exhilarating toy for computer scientists. Slot machines are modeled on a grid where each square is either black or white (1 or 0, or up and down if you prefer). The squares update their state according to the state of neighboring squares. As simple as it sounds, there are many different rules that lead to unique and amazing structures – some infinitely evolving, others are real computers. From this vast field, the authors identified “Goldilocks rules,” cellular automata that are not too active, not too passive, just right to reproduce common features of complexity. Too active would result in chaos, while too passive would result in triviality.
The blue diamond structure shows sustained coherence between the qubits while the QCA (Quantum Cellular Automata) algorithm is running. The emulated data are from a classical computer emulation of the experiment, the raw data are unfiltered results of the experiment, and the post-selected data show experimental results after a post-selection treatment.
Starting with one qubit “up” and the rest “down,” the scientists let their circuit evolve and periodically measured the qubits. The scientists then artfully filtered the data to reveal an underlying structure that persisted throughout the life of the program — a diamond pattern of qubit correlations that bucked the trend toward randomness. This was their stamp of quantum complexity.
To measure the level of complexity, the scientists borrowed a metric used in neuroscience called mutual information, which quantifies the extent of correlation between qubits. From their analysis, the scientists found that the qubits evolved in a self-organized pattern that maintained order for a significant number of time cycles. As with brains or groups of friends, the correlations between qubits suggested the formation of “small-world networks,” which are networks that exhibit high connectivity and short path lengths between nodes. Basically, the evolution of a qubit is closely related to the evolution of others.
Applications and the origins of complexity
The team’s results are an experimental milestone for quantum computing. The research provides a template for studying cellular quantum automata – a vast field for future studies – and a starting point to explore complexity with quantum computers. Future applications could use analyzes with 20,000 instead of 20 qubits to simulate highly correlated complex systems. The hope is that qubits will more faithfully recreate some of the deep interconnections seen in complex networks than computers can currently do.
Potentially even more profound, researchers are striking at the origins of complexity itself. Complexity is ubiquitous in nature, and the quantum scale is no exception. This work provides an experimental validation of quantum complexity and can begin to ask how dynamics at this scale relate to the complexity we see every day.
Learn more about complex systems simulation and optimization research at NREL.