Putting “Quantumness” to the Test

Graeme Smith; John Smolin

Viewpoint

Putting “Quantumness” to the Test

IBM TJ Watson Research Center, 1101 Kitchawan Road, Yorktown Heights, NY 10598, USA

September 25, 2013• Physics 6, 105

A machine consisting of nearly 100 quantum circuit elements can compute the solution to a classic problem in mathematics, but is it a quantum computer?

Figure caption — **Figure 1:** How can we tell if a machine is a quantum computer? One way is to prove that the machine can solve problems faster or better than any classical approach. Another test is to look inside the machine and show that its elements (qubits) can form highly entangled states and support quantum superpositions. To claim their device is a quantum computer, Bian *et al.* [1] would need to show it meets one or both of these challenges.

What is a quantum computer? We could say it’s a machine that calculates solutions to problems using quantum components. But this definition is incomplete; after all, an abacus is made of quantum elements (atoms) and can do arithmetic. Rather, when physicists envision a quantum computer that, for example, factors large numbers in the blink of an eye, they are imagining a machine whose inner workings harness two purely quantum phenomena: the ability to prepare an object in a superposition of states, such as an electron spin that points both “up” and “down,” and entanglement, in which the quantum states of two objects are intertwined, even at a distance. A report in Physical Review Letters from Zhengbing Bian of D-Wave Systems in Canada and colleagues brings this question of what constitutes a quantum computer front and center. They compute the solution to a problem in graph theory on a machine consisting of 84 logical elements designed to function as quantum bits (or qubits) [1]—a large number of qubits compared to other prototype quantum computers. But the report is certain to meet with skepticism: many more tests would be needed to conclude that the logical elements are functioning as qubits and that the device is a real quantum computer.

There are two main approaches to building a quantum computer. The circuit-based approach builds up a computation from a sequence of simple logical operations on one or two quantum bits. Measuring the final state of the qubits gives the answer to a problem. This process is similar to how a classical digital computer functions, but a quantum computer must support superpositions of states, instead of the either-or state of a classical bit. In the adiabatic approach, which is the inspiration for Bian et al.’s work, a controllable quantum system evolves, under externally controlled parameters, from an initial (known) state to a final state that encodes the answer. For example, the initialized system could be an array of noninteracting spins in its lowest energy state, while the final state corresponds to spins with interactions that specify the problem. As long as the interactions are turned on slowly enough (i.e., adiabatically), the system remains in its lowest energy state throughout, and the final state reveals the desired answer.

Researchers have tried to make quantum computers based on both approaches. But from the start, they realized that noise and imperfections were major problems for any practical quantum computer. The reason is that the dramatic speed up of a quantum computer rests on the assumption that its qubits can form coherent superpositions (meaning the wave properties of the qubits are preserved over time) long enough for a computation to take advantage of highly entangled states [2]. Yet even tiny amounts of noise can cause a quantum state to lose coherence, which is why our ordinary world appears classical [3]. Fortunately, there are theoretical tools for fighting decoherence, though they only apply to the circuit model and not to the adiabatic approach.

Experimentalists have been able to couple qubits coherently, but these devices consist of just a handful of qubits. In their new work, Bian et al. describe a device that employs 84 coupled superconducting loops or “SQUIDS,” each meant to encode a qubit with two states: current circulating clockwise in the loop, or anticlockwise. The SQUID can also exist in a superposition of these two states.

Using this machine, Bian et al. computed what are called Ramsey numbers. The Ramsey problem is an optimization challenge often recast as the “party problem”: What is the smallest number of guests one can invite to a party such that either there is a group of $m$ guests that all know each other, or there is a group of $n$ guests, none of whom know each other? F. P. Ramsey proved in 1928 [4] that such a number, called the Ramsey number $R (m, n)$ , always exists.

Describing Ramsey numbers in words is simple; finding them for even small values of $m$ and $n$ turns out to be a devilishly difficult combinatorial challenge. In fact, $R (5, 5)$ is unknown, and $R (m, n)$ for $m$ or $n$ greater than $5$ may remain forever out of reach. If quantum computers could help evaluate these elusive beasts, it would be tremendously interesting. Based on the adiabatic algorithm described in [5], Bian et al. devised a method that maps the Ramsey number to the lowest energy state of an array of coupled SQUIDs. Using this approach, they computed $R (3, 3) = 6$ , and $R (m, 2) = m$ for values of $m$ from $4$ up to $8$ , with each computation taking roughly a few milliseconds.

It would be truly incredible if Bian et al. had found these particular Ramsey numbers with a quantum computer, even though the solutions are already known [we know $R (m, 2) = m$ for all $m$ ]. But there is a caveat to interpreting their results: though they did compute the Ramsey numbers correctly, they did so with a machine that has a decoherence rate a hundred-thousand times higher than that of carefully controlled systems of qubits [6]. Such high decoherence rates strongly suggest that the SQUID loops are behaving as classical objects, which would seem to rule out any chance of the computational speed up that quantum computers promise. Though there is a possibility that this type of “noisy” adiabatic computing, referred to as quantum annealing, can still work better than conventional computers regardless, it has not been proven and remains controversial.

So, how can we tell if we’ve got a machine capable of performing a meaningful quantum computation (Fig. 1)? One test of a machine’s quantumness would be to demonstrate that it is significantly faster or better at solving a problem compared to any possible classical approach. This relative speed up should also become more pronounced as the problem gets harder (say as the machine tries to factor larger and larger numbers.) For example, Bian et al. would have to show they can calculate larger Ramsey numbers with their device to demonstrate this sort of scaling. Another option is to scrutinize the inner workings of the computer itself and prove that the elements (such as the SQUIDs in the D-Wave machine) can form entangled states, which have no classical counterpart [7].

Several groups have submitted the D-Wave machine to the first type of test. One research team showed that the D-Wave machine’s success rate at finding the solution to a physics problem (the lowest energy state of an Ising spin glass) was different than that of standard hardware running a classical algorithm called simulated annealing [8]. But it’s not clear these two approaches can be compared, since they are fundamentally different by design [9]. Separately, computer scientists demonstrated that an optimization algorithm run on the D-Wave machine was several thousand times faster than one run on a classical computer [10]. However, the D-Wave machine was tailored for the task and arrived at an approximate solution to the problem, while a less-specialized personal computer was used to solve the same problem exactly. Later theoretical work [11] showed that if an approximate solution is sufficient, it can be found efficiently with a classical computer. In this case, classical simulated annealing [12] outperforms the D-Wave machine [8]. At this point, there is no clear evidence that the D-Wave machine offers a computational speed up compared to classical systems, or that the machine’s components exhibit large-scale quantum effects.

The need to characterize and develop careful techniques to control quantum systems may seem excessively conservative to those eager to reap the rewards of the quantum age. While uncharacterized devices might give useful computational speed ups, one would need to show they can solve an interesting computational problem faster than any classical method. So far, no quantum device of any sort has met this challenge.

References

Z. Bian, F. Chudak, W. G. Macready, L. Clark, and F. Gaitan, “Experimental Determination of Ramsey Numbers,” Phys. Rev. Lett. 111, 130505 (2013)
G. Vidal, “Efficient Classical Simulation of Slightly Entangled Quantum Computations,” Phys. Rev. Lett. 91, 147902 (2003)
W. H. Zurek, “Quantum Darwinism,” Nature Phys. 5, 181 (2009)
F. P. Ramsey, “On a Problem of Formal Logic,” Proc. London Math. Soc. 30, 264 (1930)
F. Gaitan and L. Clark, “Ramsey Numbers and Adiabatic Quantum Computing,” Phys. Rev. Lett. 108, 010501 (2012)
C. Rigetti et al., “Superconducting Qubit in a Waveguide Cavity with a Coherence Time Approaching 0.1 ms,” Phys. Rev. B 86, 100506 (2012)
B. W. Reichardt, F. Unger, and U. Vazirani, “Classical Command of Quantum Systems,” Nature 496, 456 (2013)
S. Boixo et al., “Quantum Annealing with More Than 100 Hundred Qubits,” arXiv:1304.4595
J. A. Smolin and G. Smith, “Classical Signature of Quantum Annealing,” arXiv:1305.4904
C. C. McGeoch and C. Wang, “Experimental Evaluation of an Adiabatic Quantum System for Combinatorial Optimization,” Proceedings of the ACM International Conference on Computing Frontiers, Ischia, Italy, May 13-14, 2013, Article No. 23
R. Saket, “A PTAS for the Classical Ising Spin Glass Problem on the Chimera Graph Structure,” arXiv:1306.6943
S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi, “Optimization by Simulated Annealing,” Science 220, 671 (1983)

About the Authors

Graeme Smith works on quantum information theory, communication and computation in noisy settings, and the physics of information. He studied physics at the University of Toronto (B.Sc., 2001), and the California Institute of Technology (Ph.D., 2006). He is currently a Research Staff Member at IBM Research.

John Smolin received an S.B. in physics from the Massachusetts Institute of Technology in 1989 and Ph.D. in physics from UCLA in 1996. He is responsible for several fundamental concepts in quantum information and error correction and, together with Charles H. Bennett, built the first quantum cryptography device in 1989 at IBM, where he is also a Research Staff Member. He is an APS Fellow.