Abstract
Many NP-hard problems can be seen as the task of finding a ground state of a disordered highly connected Ising spin glass. If solutions are sought by means of quantum annealing, it is often necessary to represent those graphs in the annealer’s hardware by means of the graph-minor embedding technique, generating a final Hamiltonian consisting of coupled chains of ferromagnetically bound spins, whose binding energy is a free parameter. In order to investigate the effect of embedding on problems of interest, the fully connected Sherrington-Kirkpatrick model with random couplings is programmed on the D-Wave annealer using up to 270 qubits interacting on a Chimera-type graph. We present the best embedding prescriptions for encoding the Sherrington-Kirkpatrick problem in the Chimera graph. The results indicate that the optimal choice of embedding parameters could be associated with the emergence of the spin-glass phase of the embedded problem, whose presence was previously uncertain. This optimal parameter setting allows the performance of the quantum annealer to compete with (and potentially outperform, in the absence of analog control errors) optimized simulated annealing algorithms.
- Received 12 March 2015
DOI:https://doi.org/10.1103/PhysRevX.5.031040
This article is available under the terms of the Creative Commons Attribution 3.0 License. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI.
Published by the American Physical Society
Popular Summary
Some problems in computer science, the NP-complete problems, have an enticing property: A “black box” for solving one problem can be used to solve all problems using only a polynomial resource overhead. One example of such a black box, the chip from D-Wave Systems, leverages quantum mechanics to optimize quadratic binary cost functions. With only 512 physical qubits on the D-Wave Two chip, early benchmarking studies naturally looked at random instances “native” to the hardware despite concerns that these instances were insufficiently hard or not representative of real-world instances. Indeed, translations from other complex problems in computer science typically require the introduction of “dummy” qubits. Here, we focus on how the addition of these qubits affects the performance of the quantum annealer.
We consider the D-Wave Two chip at NASA Ames Research Center and its hundreds of superconducting flux qubits. We investigate the performance of the chip, which is subject to both static and dynamical noise sources that affect how well the system can find the ground state of a Hamiltonian. Our work focuses on a fully connected topology of Ising interactions (the NP-complete Sherrington-Kirkpatrick problem) in which each vertex must be represented by multiple qubits since the D-Wave Two hardware is constrained to a quasi-two-dimensional topology. How tightly the qubits must be coupled within each vertex is a tunable parameter, and we investigate the scaling for the optimal choice of this parameter. We find that, after proper tuning, sparsely connected architectures such as the one in D-Wave Two become competitive with classical algorithms on these difficult problems despite the large “embedding” overhead (each logical variable is represented by a number of spins that scales linearly with the problem size) and noise in the programmable fields and couplings.
While we cannot yet conclude if quantum annealing is significantly faster than simulated annealing, we expect that our results will motivate additional studies of how quantum annealers perform given the presence of noise.