NREL authors publish quantum computing first in Nature Communications | New


In the coming years, quantum computers should explore beyond what is possible with classical computers. This could be true for the study of complex systems, which manifest themselves in everything from our brains to the power grid, and often maximize the capabilities of supercomputers when simulated.

The first complexity analysis with a quantum computer has just been performed by a team of scientists, including two from the National Renewable Energy Laboratory (NREL), who implemented quantum cellular automata on a 23-qubit quantum computer. Their article, “Small-world complex network generation on a digital quantum processor”, was published in the journal Nature Communication.

Physical complexity appears everywhere in nature and is indicated by qualities such as spontaneous pattern formation and self-organization. For example, NREL researchers face complexity in areas such as nanoscale materials and urban infrastructure. But, true to its name, complexity can be difficult to study. Scientists expect that quantum computers, which use a fundamentally different mode of computation than classical computers, can also represent complexity in a fundamentally different and more useful way. This publication showed that complexity can in fact be simulated on a quantum computer – a first in 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 that generate realistic systems. The question for the research team was: Could a quantum version of cellular automata display complexity on a quantum computer?

Structure from simplicity

Cellular automata are an exhilarating toy for computer scientists. The automata are modeled on a lattice, where each square is either black or white (1 or 0, or up and down, if you prefer). Squares update their state based on the state of neighboring squares. As simple as it sounds, there are many different rules that lead to unique and amazing structures – some that evolve forever, some that are real computers. From this vast domain, the authors have identified “Goldilocks rules”, cellular automata that are neither too active nor too passive, just in time to reproduce common features of complexity. Too active would fall into chaos, while too passive would fall into triviality.

The blue diamond structure shows persistent coherence between qubits during execution of the Quantum Cellular Automata (QCA) algorithm. The emulated data is from a classic computer emulation of the experiment, the raw data is unfiltered results of the experiment, and the post-selected data shows experimental results after post-selection processing.

The graphs show the emulated, raw, and post-selected states of the experiment.
The blue diamond structure shows persistent coherence between qubits during execution of the Quantum Cellular Automata (QCA) algorithm. The emulated data is from a classic computer emulation of the experiment, the raw data is unfiltered results of the experiment, and the post-selected data shows experimental results after post-selection processing.

Starting with one qubit “up” and the rest “down”, the scientists let their circuit evolve and periodically measured the qubits. The scientists then cleverly filtered the data to reveal an underlying structure that persisted throughout the program’s run – a diamond pattern of qubit correlations that bucked the random trend. It was their mark of quantum complexity.

To measure the degree of complexity, the scientists borrowed a metric used in neuroscience called mutual information, which quantifies the degree of correlation between qubits. From their analysis, the scientists found that the qubits evolved in a self-organizing pattern that retained order for a significant number of time cycles. Like brains or groups of friends, correlations between qubits indicated the formation of “small world networks,” which are networks that exhibit high connectivity and short path length between nodes. Basically, the evolution of one qubit is closely linked to the evolution of others.

Applications and origins of complexity

The team’s findings are an experimental milestone for quantum computing. The research provides a model for how to study quantum cellular automata – a large area for future study – and a starting point for studying complexity with quantum computers. Future applications could use analyzes with 20,000 qubits, instead of 20, to simulate highly correlated complex systems. The hope is that qubits could replicate some of the deep entanglement seen in complex networks in a truer way than computers currently can.

Potentially even deeper, researchers are hitting at the origins of complexity itself. Complexity emerges ubiquitously in nature, and the quantum scale is no exception. This work provides experimental validation of quantum complexity and may begin to wonder how dynamics at this scale relate to the complexity we see every day.

Learn about complex systems simulation and optimization research at NREL.

Sherry J. Basler