• Open Access

Quantum Optimization of Fully Connected Spin Glasses

Davide Venturelli, Salvatore Mandrà, Sergey Knysh, Bryan O’Gorman, Rupak Biswas, and Vadim Smelyanskiy
Phys. Rev. X 5, 031040 – Published 18 September 2015
PDFHTMLExport Citation

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 ±1 couplings is programmed on the D-Wave TwoTM 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.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • 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

Authors & Affiliations

Davide Venturelli1,2,*, Salvatore Mandrà1,3, Sergey Knysh1,4, Bryan O’Gorman1, Rupak Biswas1, and Vadim Smelyanskiy5

  • 1NASA Ames Research Center Quantum Artificial Intelligence Laboratory (QuAIL), Mail Stop 269-1, Moffett Field, California 94035, USA
  • 2USRA Research Institute for Advanced Computer Science (RIACS), 615 National, Mountain View, California 94043, USA
  • 3Department of Chemistry and Chemical Biology, Harvard University, 12 Oxford Street, Cambridge, Massachusetts 02139, USA
  • 4Stinger Ghaffarian Technologies Inc., 7701 Greenbelt Road, Suite 400, Greenbelt, Maryland 20770, USA
  • 5Google, 150 Main Street, Venice Beach, California 90291, USA

  • *Author to whom correspondence should be addressed. davide.venturelli@nasa.gov

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.

Key Image

Article Text

Click to Expand

Supplemental Material

Click to Expand

References

Click to Expand
Issue

Vol. 5, Iss. 3 — July - September 2015

Subject Areas
Reuse & Permissions
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review X

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 3.0 License. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

×

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×