#### Experimental Determination of Ramsey Numbers

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).