Scientists have created a test of determining whether a quantum processor is functioning in a way that could one day provide a practical advantage over classical computers.
The test, published in the journal Science this week, searches for a “quantum speedup” by having a quantum processor and a classical processor both solve increasingly complex optimization problems.
Both processors should take longer and longer to solve the problems as they get more complex. But a quantum processor should slow down at a slower rate, according to the study’s authors.
“Our study identifies five possible types of quantum speedup and establishes standards by which such speedups can be rigorously quantified,” said Daniel Lidar, one of the study’s lead authors and the scientific director at the USC-Lockheed Martin Quantum Computation Center.
The promise of quantum processors lies in their hoped-for ability to solve certain types of problems more quickly than would be possible with a traditional computer by taking advantage of quantum mechanics.
As opposed to traditional computer bits, which can encode distinctly either a one or a zero, qubits can encode a one and a zero at the same time. This property, called superposition, along with the ability of quantum states to “tunnel” through energy barriers, should allow quantum processors to solve optimization problems more efficiently.
The researchers reported on a speedup experiment designed around the D-Wave Two quantum processor, which is currently the only quantum processor large enough to be subjected to such a test. Previous research has shown that quantum bits (or “qubits”) on the D-Wave Two are, in fact, entangled — one of the key measures of whether a processor is operating quantumly. The next step is to determine whether the processor uses that quantum-ness in a practical way.
In the new experiment, the researchers designed thousands of random optimization problems of varying degree of difficulty and checked how long each processor took before they were reasonably certain that a solution was found.
In its first test, the D-Wave Two did not appear to show a quantum speedup for most cases and a small speedup for some cases. More tests are needed, the study’s authors said, pointing out that noise may have masked the speedup and that the current study did not include quantum error correction, which is widely believed to be essential to overcome such noise.
“If you can show a speedup, that’s good. If you don’t, that doesn’t necessarily mean one doesn’t exist. For now, you need to keep testing,” said Matthias Troyer of ETH Zurich, the study’s corresponding author.
The test was created by researchers from USC, ETH, Google, Microsoft Research and the University of California, Santa Barbara. They are planning new tests that will include more difficult problems, which might be more suitable for teasing apart the quantum from the classical performance.
“Detecting and confidently identifying a quantum speedup experimentally can be very subtle, and our study is a first step in quantifying the possibility that such a speedup will be found for optimization problems,” Lidar said.
The project was funded by the Swiss National Science Foundation through the National Competence Center in Research, the Army Research Office MURI (grant number W911NF11-1-0268), Army Research Office (grant number W911NF-12-1-0523), the Lockheed Martin Corp. and Microsoft Research.
