The realm of quantum computing is so often regarded as a mythic place of near-infinite possibility. If it can't be computed now with our classical bit-based computers, then it's just a matter of time before quantum computers swoop in and save us from the once-impossible.
It's not that easy, however: the quantum world has limits too. And now researchers at the National Institute of Standards and Technology have defined the theorized "speed limit" of quantum computing more precisely than ever before.
The bad news is that speed limit is likely a bit lower than many had hoped. As described in a paper published in the current Physical Review Letters and authored by NIST scientists, the increase in speed allowed by quantum entanglement-based processing is more likely to be linear than exponential. This is the difference between a steady (if extremely steep) increase and a stratospheric upward curve.
The question, as posed in the NIST study: "Can information be transmitted with an arbitrarily large velocity, and if so, how quickly (in space or time) does that velocity grow?" The answer to the first part appears to be "no."
"Our results impose strong new constraints on the growth of correlations and the production of entangled states in a variety of rapidly emerging, long-range interacting atomic, molecular, and optical systems," the NIST group explains.
We should clarify what speed even means in this context, as it's not quite movement as we usually understand it. One way that information in quantum computers is represented is through particle spin. A binary 1 here might correspond to an "up" orientation, while a 0 might correspond to "down," except in the quantum world we actually get states that are sort of both up and down (1 and 0) at the same time.
A quantum computer would be able to move these states around through a process of quantum entanglement, which is where two or more (many more) particles are allowed to share the same quantum state, essentially becoming a single particle in multiple locations (depending on the interpretation). Imagine an array of suspended particles as a row of dominos. Entangled states propagate as each particle passes on its state to a neighbor. It's this domino effect of state transmission that has the limit.
The idea of instant communication over large distances (not just next-door neighbor to next-door neighbor, but neighbor to neighbor's neighbor's neighbor's neighbor) has been taken somewhat for granted as advances in technology began to imply the possibility of quantum computing taking advantage of these huge jumps, which would allow the great increases in speeds. By 2005, theoretical studies had all but promised this capability, but experiments since then haven't really been able to make it work.
"Those results implied a quantum computer might be able to operate really fast, much faster than anyone had thought possible," said Michael Foss-Feig, a NIST scientist and co-author of the current paper, in a statement. "But over the next decade, no one saw any evidence that the information could actually travel that quickly."
What the mid-00s results actually offered was the possibility of the size of a given particle arrangement increasing exponentially while the time required to process information in that system grows logarithmically (like the opposite of exponential: very, very slowly). This is shown as the blue line in the above graph. But here we see that the propagation time of a particle state grows in accordance with the system size. No free rides, in other words.
The new NIST results (the red line) are a bit closer to very early-days predictions made in the 1970s, where physicists had assumed that particles can only "talk" to their next door neighbors. So, to pass along a certain quantum state, one particle would hand it over to the next particle in line and so on, like a game of telephone. By the 2005 study, it had become clear that more is possible: one particle might be able to talk to another particle much farther away than its immediate neighbor. That implies a whole lot more speed.
While the new calculations are closer to the 1970s assumptions, they also allow for the possibility of jumping from distant particle to distant particle. "What the 2005 derivation failed to constrain properly was in fact those very same next-door interactions that the 1970s paper dealt with," Alexey Gorshkov, of the University of Maryland's Gorshkov Research Group and a co-author of the study, told me. "We, or rather Mike [Foss-Feig], realized that when one has both next-door and beyond-next-door interactions, one has to be much more careful with the next-door ones."
There is an upside, at least. Understanding better how this whole process works means that researchers may in the future be able to better simulate quantum computers using classical, non-quantum machines. That's significant.
"[T]he findings tell us something important about how entanglement works," noted Foss-Feig in a separate statement. "They could help us understand how to model quantum systems more efficiently."
An open-access preprint version of the NIST paper is available at arXiv.