Quantum Computers Run on Just the Right Amount of Connectivity

Scientists know that entanglement, a special connection that intertwines the fate of quantum particles, is a crucial ingredient for quantum computers. Without it, a quantum computer loses its ability to harness the fullness of quantum complexity—that special sauce that makes the quantum world impossible to emulate on ordinary computers. But whether entanglement is the only key, and exactly how much of it is needed, no one really knows. 

Now, JQI Fellow Alexey Gorshkov and his group, in collaboration with researchers at the University of Chicago, have found a partial answer to the conundrum of what powers quantum complexity. In their new theoretical work, they considered a particular arrangement of many particles and found that the key to knowing whether this group of particles requires a quantum computer to simulate does indeed depend on entanglement; but simply increasing the connections between particles doesn’t do the trick. They showed that quantum complexity needs just the right amount of connectivity—not too little, not too much. They published their results recently in the journal Physical Review Letters.

“In general, simulating quantum systems on a classical computer is a very difficult task,” says Dominik Hangleiter, a postdoctoral fellow at the Joint Center for Quantum Information and Computer Science (QuICS) and a co-author on the work. “We have a lot of different algorithms that fail for different reasons. What we wanted to ask is ‘Can you find an intrinsic property of the quantum system that doesn’t depend on which algorithm you use to simulate it?’ And one of those properties is entanglement.”

They focused on a particular theoretical concoction called a regular graph state. Imagine this like a tightly knit spiderweb, where each particle interacts with a fixed number of other particles in the bunch. The interactions entangle a particle with its neighbors, and the neighbors then become entangled with their neighbors, spreading entanglement throughout the web. The researchers wanted to know how the number of interacting neighbors per particle impacts the quantum complexity of the whole web.

First, they tackled the simplest case, where each particle only interacts with one other particle. This isn’t much of a spiderweb. It’s just a collection of interacting particle pairs, and the researchers showed this could be simulated on a classical computer. Then, they looked at the case where each particle interacts with two others—a peculiar web that looks like one big circle. They found that this, too, would be easy to simulate on a classical computer. 

If each particle interacts with three others, the whole thing starts to look more like a web a real spider might spin up, and the entanglement spreads across the web in more complicated ways. The researchers found that this is exactly where quantum complexity kicks in as well—a web with three connections per particle can be impossible to simulate on a classical computer. To prove this, the team turned to a particular type of quantum computing, known as measurement-based quantum computing.

Measurement-based quantum computing works like this: An entangled particle web, often a graph state, is created, and the web is then chiseled down with select measurements in a specific order to perform a computation. If the initial web is complex enough to perform any quantum computation one might dream up, it is known as a resource state. 

To construct their proof, Hangleiter and his collaborators showed that some of their web-like states with three or more interacting neighbors per particle can be used as resource states, capable of performing any quantum computation a scientist’s heart desires. If these resource states were easy to simulate classically, the entire quantum world would be easy to simulate on a classical computer, which does not appear to be the case. Therefore, the commonly accepted conjecture is that these complex webs cannot be easily simulated on a classical computer. 

For one or two neighbors per particle, classical computers suffice. For three, quantum complexity kicks in. Next, the researchers turned up the interaction knob of their quantum web. They found that quantum complexity persisted for a while—until it didn’t. “The surprising thing is, as you go to a very highly connected graph, you again come into a regime where everything becomes easy to simulate, but for non-trivial reasons,” Hangleiter says.

The non-trivial reason turned out to be that these highly connected webs are exactly as complicated, or as uncomplicated, as the barely connected webs. By leveraging the theory of graphs, the researchers made a direct analogy between a web where nothing is connected and a web where everything is connected. From there, one could add single connections (or remove single connections) and preserve the analogy. Strangely, a web where all particles are connected to each other has very little entanglement, just like a barely connected web.  So, when it comes to connectivity, resource states are like Goldilocks—they need not too much, not too little, but just the right amount. 

The group is working on generalizing their results to new kinds of webs, with more complex interaction structures. As for the original question of what causes quantum complexity, the team feels they have answered it in part. "Honestly it's a particular case in which we studied the question, and it's not a full resolution," Hangleiter says. "But also, I think there is no full resolution that you can hope for. It's really a multifaceted question."

Story by Dina Genkina