1
|
Bernaschi M, González-Adalid Pemartín I, Martín-Mayor V, Parisi G. The quantum transition of the two-dimensional Ising spin glass. Nature 2024; 631:749-754. [PMID: 38987607 PMCID: PMC11269196 DOI: 10.1038/s41586-024-07647-y] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/12/2023] [Accepted: 06/03/2024] [Indexed: 07/12/2024]
Abstract
Quantum annealers are commercial devices that aim to solve very hard computational problems1, typically those involving spin glasses2,3. Just as in metallurgic annealing, in which a ferrous metal is slowly cooled4, quantum annealers seek good solutions by slowly removing the transverse magnetic field at the lowest possible temperature. Removing the field diminishes the quantum fluctuations but forces the system to traverse the critical point that separates the disordered phase (at large fields) from the spin-glass phase (at small fields). A full understanding of this phase transition is still missing. A debated, crucial question regards the closing of the energy gap separating the ground state from the first excited state. All hopes of achieving an exponential speed-up, compared to classical computers, rest on the assumption that the gap will close algebraically with the number of spins5-9. However, renormalization group calculations predict instead that there is an infinite-randomness fixed point10. Here we solve this debate through extreme-scale numerical simulations, finding that both parties have grasped parts of the truth. Although the closing of the gap at the critical point is indeed super-algebraic, it remains algebraic if one restricts the symmetry of possible excitations. As this symmetry restriction is experimentally achievable (at least nominally), there is still hope for the quantum annealing paradigm11-13.
Collapse
Affiliation(s)
| | | | - Víctor Martín-Mayor
- Departamento de Física Teórica, Universidad Complutense de Madrid, Madrid, Spain
| | - Giorgio Parisi
- Dipartimento di Fisica, Sapienza Università di Roma, Rome, Italy
- Nanotec-Rome unit, CNR, Rome, Italy
| |
Collapse
|
2
|
Fernandez LA, Martin-Mayor V, Yllanes D. Phase transition in the computational complexity of the shortest common superstring and genome assembly. Phys Rev E 2024; 109:014133. [PMID: 38366408 DOI: 10.1103/physreve.109.014133] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/17/2023] [Accepted: 12/11/2023] [Indexed: 02/18/2024]
Abstract
Genome assembly, the process of reconstructing a long genetic sequence by aligning and merging short fragments, or reads, is known to be NP-hard, either as a version of the shortest common superstring problem or in a Hamiltonian-cycle formulation. That is, the computing time is believed to grow exponentially with the problem size in the worst case. Despite this fact, high-throughput technologies and modern algorithms currently allow bioinformaticians to handle datasets of billions of reads. Using methods from statistical mechanics, we address this conundrum by demonstrating the existence of a phase transition in the computational complexity of the problem and showing that practical instances always fall in the "easy" phase (solvable by polynomial-time algorithms). In addition, we propose a Markov-chain Monte Carlo method that outperforms common deterministic algorithms in the hard regime.
Collapse
Affiliation(s)
- L A Fernandez
- Departamento de Física Teórica, Universidad Complutense, 28040 Madrid, Spain
- Instituto de Biocomputación y Física de Sistemas Complejos (BIFI), 50018 Zaragoza, Spain
| | - V Martin-Mayor
- Departamento de Física Teórica, Universidad Complutense, 28040 Madrid, Spain
- Instituto de Biocomputación y Física de Sistemas Complejos (BIFI), 50018 Zaragoza, Spain
| | - D Yllanes
- Instituto de Biocomputación y Física de Sistemas Complejos (BIFI), 50018 Zaragoza, Spain
- Chan Zuckerberg Biohub - SF, 499 Illinois Street, San Francisco, California 94158, USA
| |
Collapse
|
3
|
Hauke P, Katzgraber HG, Lechner W, Nishimori H, Oliver WD. Perspectives of quantum annealing: methods and implementations. REPORTS ON PROGRESS IN PHYSICS. PHYSICAL SOCIETY (GREAT BRITAIN) 2020; 83:054401. [PMID: 32235066 DOI: 10.1088/1361-6633/ab85b8] [Citation(s) in RCA: 48] [Impact Index Per Article: 12.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/02/2023]
Abstract
Quantum annealing is a computing paradigm that has the ambitious goal of efficiently solving large-scale combinatorial optimization problems of practical importance. However, many challenges have yet to be overcome before this goal can be reached. This perspectives article first gives a brief introduction to the concept of quantum annealing, and then highlights new pathways that may clear the way towards feasible and large scale quantum annealing. Moreover, since this field of research is to a strong degree driven by a synergy between experiment and theory, we discuss both in this work. An important focus in this article is on future perspectives, which complements other review articles, and which we hope will motivate further research.
Collapse
Affiliation(s)
- Philipp Hauke
- INO-CNR BEC Center and Department of Physics, University of Trento, 38123Povo (TN), Italy. Kirchhoff-Institute for Physics, Heidelberg University, 69120 Heidelberg, Germany. Institute for Theoretical Physics, Heidelberg University, 69120 Heidelberg, Germany
| | | | | | | | | |
Collapse
|
4
|
Weinberg P, Tylutki M, Rönkkö JM, Westerholm J, Åström JA, Manninen P, Törmä P, Sandvik AW. Scaling and Diabatic Effects in Quantum Annealing with a D-Wave Device. PHYSICAL REVIEW LETTERS 2020; 124:090502. [PMID: 32202854 DOI: 10.1103/physrevlett.124.090502] [Citation(s) in RCA: 11] [Impact Index Per Article: 2.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 10/03/2019] [Accepted: 02/10/2020] [Indexed: 05/02/2023]
Abstract
We discuss quantum annealing of the two-dimensional transverse-field Ising model on a D-Wave device, encoded on L×L lattices with L≤32. Analyzing the residual energy and deviation from maximal magnetization in the final classical state, we find an optimal L dependent annealing rate v for which the two quantities are minimized. The results are well described by a phenomenological model with two powers of v and L-dependent prefactors to describe the competing effects of reduced quantum fluctuations (for which we see evidence of the Kibble-Zurek mechanism) and increasing noise impact when v is lowered. The same scaling form also describes results of numerical solutions of a transverse-field Ising model with the spins coupled to noise sources. We explain why the optimal annealing time is much longer than the coherence time of the individual qubits.
Collapse
Affiliation(s)
- Phillip Weinberg
- Department of Physics, Boston University, 590 Commonwealth Avenue, Boston, Massachusetts 02215, USA
| | - Marek Tylutki
- Department of Applied Physics, Aalto University School of Science, FI-00076 Aalto, Finland
- Faculty of Physics, Warsaw University of Technology, Ulica Koszykowa 75, PL-00662 Warsaw, Poland
| | - Jami M Rönkkö
- CSC-IT Center for Science, P.O. Box 405, FIN-02101 Espoo, Finland
| | - Jan Westerholm
- Faculty of Science and Engineering, Åbo Akademi University, Vattenborgsvägen 3, FI 20500 Åbo, Finland
| | - Jan A Åström
- CSC-IT Center for Science, P.O. Box 405, FIN-02101 Espoo, Finland
| | - Pekka Manninen
- CSC-IT Center for Science, P.O. Box 405, FIN-02101 Espoo, Finland
| | - Päivi Törmä
- Department of Applied Physics, Aalto University School of Science, FI-00076 Aalto, Finland
| | - Anders W Sandvik
- Department of Physics, Boston University, 590 Commonwealth Avenue, Boston, Massachusetts 02215, USA
- Beijing National Laboratory of Condensed Matter Physics and Institute of Physics, Chinese Academy of Sciences, Beijing 100190, China
| |
Collapse
|
5
|
Decelle A, Martin-Mayor V, Seoane B. Learning a local symmetry with neural networks. Phys Rev E 2019; 100:050102. [PMID: 31869906 DOI: 10.1103/physreve.100.050102] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/07/2019] [Indexed: 06/10/2023]
Abstract
We explore the capacity of neural networks to detect a symmetry with complex local and non-local patterns: the gauge symmetry Z_{2}. This symmetry is present in physical problems from topological transitions to quantum chromodynamics, and controls the computational hardness of instances of spin-glasses. Here, we show how to design a neural network, and a dataset, able to learn this symmetry and to find compressed latent representations of the gauge orbits. Our method pays special attention to system-wrapping loops, the so-called Polyakov loops, known to be particularly relevant for computational complexity.
Collapse
Affiliation(s)
- A Decelle
- Laboratoire de Recherche en Informatique, TAU - INRIA, CNRS, Université Paris-Sud et Université Paris-Saclay, Bât. 660, 91190 Gif-sur-Yvette, France
| | - V Martin-Mayor
- Departamento de Física Teórica, Universidad Complutense, 28040 Madrid, Spain
- Instituto de Biocomputación y Física de Sistemas Complejos (BIFI), 50018 Zaragoza, Spain
| | - B Seoane
- Sorbonne Université, CNRS, IBPS, UMR 7238, Laboratoire de Biologie Computationnelle et Quantitative (LCQB), 75005 Paris, France
- Sorbonne Université, Institut des Sciences du Calcul et des Données (ISCD), 75005 Paris, France
| |
Collapse
|
6
|
Zhu Z, Ochoa AJ, Katzgraber HG. Fair sampling of ground-state configurations of binary optimization problems. Phys Rev E 2019; 99:063314. [PMID: 31330750 DOI: 10.1103/physreve.99.063314] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/18/2019] [Indexed: 11/07/2022]
Abstract
Although many efficient heuristics have been developed to solve binary optimization problems, these typically produce correlated solutions for degenerate problems. Most notably, transverse-field quantum annealing-the heuristic employed in current commercially available quantum annealing machines-has been shown to often be exponentially biased when sampling the solution space. Here we present an approach to sample ground-state (or low-energy) configurations for binary optimization problems. The method samples degenerate states with almost equal probability and is based on a combination of parallel tempering Monte Carlo with isoenergetic cluster moves. We illustrate the approach using two-dimensional Ising spin glasses, as well as spin glasses on the D-Wave Systems quantum annealer chimera topology. In addition, a simple heuristic to approximate the number of solutions of a degenerate problem is introduced.
Collapse
Affiliation(s)
- Zheng Zhu
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA
| | - Andrew J Ochoa
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA
| | - Helmut G Katzgraber
- Department of Physics and Astronomy, Texas A&M University, College Station, Texas 77843-4242, USA.,Microsoft Quantum, Microsoft, Redmond, Washington 98052, USA.,Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA
| |
Collapse
|
7
|
Wendin G. Quantum information processing with superconducting circuits: a review. REPORTS ON PROGRESS IN PHYSICS. PHYSICAL SOCIETY (GREAT BRITAIN) 2017; 80:106001. [PMID: 28682303 DOI: 10.1088/1361-6633/aa7e1a] [Citation(s) in RCA: 107] [Impact Index Per Article: 15.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/28/2023]
Abstract
During the last ten years, superconducting circuits have passed from being interesting physical devices to becoming contenders for near-future useful and scalable quantum information processing (QIP). Advanced quantum simulation experiments have been shown with up to nine qubits, while a demonstration of quantum supremacy with fifty qubits is anticipated in just a few years. Quantum supremacy means that the quantum system can no longer be simulated by the most powerful classical supercomputers. Integrated classical-quantum computing systems are already emerging that can be used for software development and experimentation, even via web interfaces. Therefore, the time is ripe for describing some of the recent development of superconducting devices, systems and applications. As such, the discussion of superconducting qubits and circuits is limited to devices that are proven useful for current or near future applications. Consequently, the centre of interest is the practical applications of QIP, such as computation and simulation in Physics and Chemistry.
Collapse
Affiliation(s)
- G Wendin
- Department of Microtechnology and Nanoscience-MC2, Chalmers University of Technology, SE-41296 Gothenburg, Sweden
| |
Collapse
|
8
|
Hen I. Solving spin glasses with optimized trees of clustered spins. Phys Rev E 2017; 96:022105. [PMID: 28950492 DOI: 10.1103/physreve.96.022105] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/14/2017] [Indexed: 11/07/2022]
Abstract
We present an algorithm for the optimization and thermal equilibration of spin glasses, or more generally, cost functions of the Ising form H=∑_{〈ij〉}J_{ij}s_{i}s_{j}+∑_{i}h_{i}s_{i}, defined on graphs with arbitrary connectivity. The algorithm consists of two repeated steps: (i) the optimized construction of a random tree of spin clusters on the input problem graph, and (ii) the thermal sampling of the generated tree. The randomly generated trees are constructed so as to optimize a balance between the size of the tree and the complexity required to draw Boltzmann samples from it. We benchmark the algorithm on several classes of problems and demonstrate its advantages over existing approaches.
Collapse
Affiliation(s)
- Itay Hen
- Information Sciences Institute, University of Southern California, Marina del Rey, California 90292, USA and Department of Physics and Astronomy and Center for Quantum Information Science & Technology, University of Southern California, Los Angeles, California 90089, USA
| |
Collapse
|
9
|
Albash T, Martin-Mayor V, Hen I. Temperature Scaling Law for Quantum Annealing Optimizers. PHYSICAL REVIEW LETTERS 2017; 119:110502. [PMID: 28949216 DOI: 10.1103/physrevlett.119.110502] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/27/2017] [Indexed: 06/07/2023]
Abstract
Physical implementations of quantum annealing unavoidably operate at finite temperatures. We point to a fundamental limitation of fixed finite temperature quantum annealers that prevents them from functioning as competitive scalable optimizers and show that to serve as optimizers annealer temperatures must be appropriately scaled down with problem size. We derive a temperature scaling law dictating that temperature must drop at the very least in a logarithmic manner but also possibly as a power law with problem size. We corroborate our results by experiment and simulations and discuss the implications of these to practical annealers.
Collapse
Affiliation(s)
- Tameem Albash
- Information Sciences Institute, University of Southern California, Marina del Rey, California 90292, USA
- Department of Physics and Astronomy and Center for Quantum Information Science & Technology, University of Southern California, Los Angeles, California 90089, USA
| | - Victor Martin-Mayor
- Departamento de Física Teórica I, Universidad Complutense, 28040 Madrid, Spain
- Instituto de Biocomputación y Física de Sistemas Complejos (BIFI), Zaragoza 50018, Spain
| | - Itay Hen
- Information Sciences Institute, University of Southern California, Marina del Rey, California 90292, USA
- Department of Physics and Astronomy and Center for Quantum Information Science & Technology, University of Southern California, Los Angeles, California 90089, USA
| |
Collapse
|
10
|
Çağlar T, Berker AN. Phase transitions between different spin-glass phases and between different chaoses in quenched random chiral systems. Phys Rev E 2017; 96:032103. [PMID: 29346860 DOI: 10.1103/physreve.96.032103] [Citation(s) in RCA: 9] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/14/2017] [Indexed: 11/07/2022]
Abstract
The left-right chiral and ferromagnetic-antiferromagnetic double-spin-glass clock model, with the crucially even number of states q=4 and in three dimensions d=3, has been studied by renormalization-group theory. We find, for the first time to our knowledge, four spin-glass phases, including conventional, chiral, and quadrupolar spin-glass phases, and phase transitions between spin-glass phases. The chaoses, in the different spin-glass phases and in the phase transitions of the spin-glass phases with the other spin-glass phases, with the non-spin-glass ordered phases, and with the disordered phase, are determined and quantified by Lyapunov exponents. It is seen that the chiral spin-glass phase is the most chaotic spin-glass phase. The calculated phase diagram is also otherwise very rich, including regular and temperature-inverted devil's staircases and reentrances.
Collapse
Affiliation(s)
- Tolga Çağlar
- Faculty of Engineering and Natural Sciences, Sabancı University, Tuzla, Istanbul 34956, Turkey
| | - A Nihat Berker
- Faculty of Engineering and Natural Sciences, Kadir Has University, Cibali, Istanbul 34083, Turkey.,Department of Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
| |
Collapse
|
11
|
Çağlar T, Berker AN. Devil's staircase continuum in the chiral clock spin glass with competing ferromagnetic-antiferromagnetic and left-right chiral interactions. Phys Rev E 2017; 95:042125. [PMID: 28505813 DOI: 10.1103/physreve.95.042125] [Citation(s) in RCA: 7] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/10/2016] [Indexed: 11/07/2022]
Abstract
The chiral clock spin-glass model with q=5 states, with both competing ferromagnetic-antiferromagnetic and left-right chiral frustrations, is studied in d=3 spatial dimensions by renormalization-group theory. The global phase diagram is calculated in temperature, antiferromagnetic bond concentration p, random chirality strength, and right-chirality concentration c. The system has a ferromagnetic phase, a multitude of different chiral phases, a chiral spin-glass phase, and a critical (algebraically) ordered phase. The ferromagnetic and chiral phases accumulate at the disordered phase boundary and form a spectrum of devil's staircases, where different ordered phases characteristically intercede at all scales of phase-diagram space. Shallow and deep reentrances of the disordered phase, bordered by fragments of regular and temperature-inverted devil's staircases, are seen. The extremely rich phase diagrams are presented as continuously and qualitatively changing videos.
Collapse
Affiliation(s)
- Tolga Çağlar
- Faculty of Engineering and Natural Sciences, Sabancı University, Tuzla, Istanbul 34956, Turkey
| | - A Nihat Berker
- Faculty of Engineering and Natural Sciences, Sabancı University, Tuzla, Istanbul 34956, Turkey.,Faculty of Engineering and Natural Sciences, Kadir Has University, Cibali, Istanbul 34083, Turkey.,Department of Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
| |
Collapse
|
12
|
Zhang BH, Wagenbreth G, Martin-Mayor V, Hen I. Advantages of Unfair Quantum Ground-State Sampling. Sci Rep 2017; 7:1044. [PMID: 28432287 PMCID: PMC5430793 DOI: 10.1038/s41598-017-01096-6] [Citation(s) in RCA: 12] [Impact Index Per Article: 1.7] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/26/2017] [Accepted: 03/21/2017] [Indexed: 11/28/2022] Open
Abstract
The debate around the potential superiority of quantum annealers over their classical counterparts has been ongoing since the inception of the field. Recent technological breakthroughs, which have led to the manufacture of experimental prototypes of quantum annealing optimizers with sizes approaching the practical regime, have reignited this discussion. However, the demonstration of quantum annealing speedups remains to this day an elusive albeit coveted goal. We examine the power of quantum annealers to provide a different type of quantum enhancement of practical relevance, namely, their ability to serve as useful samplers from the ground-state manifolds of combinatorial optimization problems. We study, both numerically by simulating stoquastic and non-stoquastic quantum annealing processes, and experimentally, using a prototypical quantum annealing processor, the ability of quantum annealers to sample the ground-states of spin glasses differently than thermal samplers. We demonstrate that (i) quantum annealers sample the ground-state manifolds of spin glasses very differently than thermal optimizers (ii) the nature of the quantum fluctuations driving the annealing process has a decisive effect on the final distribution, and (iii) the experimental quantum annealer samples ground-state manifolds significantly differently than thermal and ideal quantum annealers. We illustrate how quantum annealers may serve as powerful tools when complementing standard sampling algorithms.
Collapse
Affiliation(s)
| | | | - Victor Martin-Mayor
- Departamento de Física Teórica I, Universidad Complutense, 28040, Madrid, Spain.,Instituto de Biocomputación y Física de Sistemas Complejos (BIFI), Zaragoza, Spain
| | - Itay Hen
- Information Sciences Institute, University of Southern California, Marina del Rey, California, 90292, USA. .,Department of Physics and Astronomy and Center for Quantum Information Science & Technology, University of Southern California, Los Angeles, California, 90089, USA.
| |
Collapse
|
13
|
Nishimori H, Takada K. Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stoquastic Hamiltonians. ACTA ACUST UNITED AC 2017. [DOI: 10.3389/fict.2017.00002] [Citation(s) in RCA: 62] [Impact Index Per Article: 8.9] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/13/2022]
|
14
|
Çağlar T, Berker AN. Chiral Potts spin glass in d=2 and 3 dimensions. Phys Rev E 2016; 94:032121. [PMID: 27739736 DOI: 10.1103/physreve.94.032121] [Citation(s) in RCA: 11] [Impact Index Per Article: 1.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/29/2016] [Indexed: 11/07/2022]
Abstract
The chiral spin-glass Potts system with q=3 states is studied in d=2 and 3 spatial dimensions by renormalization-group theory and the global phase diagrams are calculated in temperature, chirality concentration p, and chirality-breaking concentration c, with determination of phase chaos and phase-boundary chaos. In d=3, the system has ferromagnetic, left-chiral, right-chiral, chiral spin-glass, and disordered phases. The phase boundaries to the ferromagnetic, left- and right-chiral phases show, differently, an unusual, fibrous patchwork (microreentrances) of all four (ferromagnetic, left-chiral, right-chiral, chiral spin-glass) ordered phases, especially in the multicritical region. The chaotic behavior of the interactions, under scale change, are determined in the chiral spin-glass phase and on the boundary between the chiral spin-glass and disordered phases, showing Lyapunov exponents in magnitudes reversed from the usual ferromagnetic-antiferromagnetic spin-glass systems. At low temperatures, the boundaries of the left- and right-chiral phases become thresholded in p and c. In d=2, the chiral spin-glass Potts system does not have a spin-glass phase, consistently with the lower-critical dimension of ferromagnetic-antiferromagnetic spin glasses. The left- and right-chirally ordered phases show reentrance in chirality concentration p.
Collapse
Affiliation(s)
- Tolga Çağlar
- Faculty of Engineering and Natural Sciences, Sabancı University, Tuzla, Istanbul 34956, Turkey
| | - A Nihat Berker
- Faculty of Engineering and Natural Sciences, Sabancı University, Tuzla, Istanbul 34956, Turkey.,Department of Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
| |
Collapse
|
15
|
Zero-temperature quantum annealing bottlenecks in the spin-glass phase. Nat Commun 2016; 7:12370. [PMID: 27491338 PMCID: PMC4980455 DOI: 10.1038/ncomms12370] [Citation(s) in RCA: 42] [Impact Index Per Article: 5.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/25/2015] [Accepted: 06/24/2016] [Indexed: 11/08/2022] Open
Abstract
A promising approach to solving hard binary optimization problems is quantum adiabatic annealing in a transverse magnetic field. An instantaneous ground state-initially a symmetric superposition of all possible assignments of N qubits-is closely tracked as it becomes more and more localized near the global minimum of the classical energy. Regions where the energy gap to excited states is small (for instance at the phase transition) are the algorithm's bottlenecks. Here I show how for large problems the complexity becomes dominated by O(log N) bottlenecks inside the spin-glass phase, where the gap scales as a stretched exponential. For smaller N, only the gap at the critical point is relevant, where it scales polynomially, as long as the phase transition is second order. This phenomenon is demonstrated rigorously for the two-pattern Gaussian Hopfield model. Qualitative comparison with the Sherrington-Kirkpatrick model leads to similar conclusions.
Collapse
|
16
|
Wang Y, Wu S, Zou J. Quantum Annealing with Markov Chain Monte Carlo Simulations and D-Wave Quantum Computers. Stat Sci 2016. [DOI: 10.1214/16-sts560] [Citation(s) in RCA: 11] [Impact Index Per Article: 1.4] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/19/2022]
|
17
|
Determination and correction of persistent biases in quantum annealers. Sci Rep 2016; 6:18628. [PMID: 26783120 PMCID: PMC4725997 DOI: 10.1038/srep18628] [Citation(s) in RCA: 25] [Impact Index Per Article: 3.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/24/2015] [Accepted: 11/10/2015] [Indexed: 11/08/2022] Open
Abstract
Calibration of quantum computers is essential to the effective utilisation of their quantum resources. Specifically, the performance of quantum annealers is likely to be significantly impaired by noise in their programmable parameters, effectively misspecification of the computational problem to be solved, often resulting in spurious suboptimal solutions. We developed a strategy to determine and correct persistent, systematic biases between the actual values of the programmable parameters and their user-specified values. We applied the recalibration strategy to two D-Wave Two quantum annealers, one at NASA Ames Research Center in Moffett Field, California, and another at D-Wave Systems in Burnaby, Canada. We show that the recalibration procedure not only reduces the magnitudes of the biases in the programmable parameters but also enhances the performance of the device on a set of random benchmark instances.
Collapse
|
18
|
Computational multiqubit tunnelling in programmable quantum annealers. Nat Commun 2016; 7:10327. [PMID: 26739797 PMCID: PMC4729842 DOI: 10.1038/ncomms10327] [Citation(s) in RCA: 134] [Impact Index Per Article: 16.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/03/2015] [Accepted: 11/26/2015] [Indexed: 11/17/2022] Open
Abstract
Quantum tunnelling is a phenomenon in which a quantum state traverses energy barriers higher than the energy of the state itself. Quantum tunnelling has been hypothesized as an advantageous physical resource for optimization in quantum annealing. However, computational multiqubit tunnelling has not yet been observed, and a theory of co-tunnelling under high- and low-frequency noises is lacking. Here we show that 8-qubit tunnelling plays a computational role in a currently available programmable quantum annealer. We devise a probe for tunnelling, a computational primitive where classical paths are trapped in a false minimum. In support of the design of quantum annealers we develop a nonperturbative theory of open quantum dynamics under realistic noise characteristics. This theory accurately predicts the rate of many-body dissipative quantum tunnelling subject to the polaron effect. Furthermore, we experimentally demonstrate that quantum tunnelling outperforms thermal hopping along classical paths for problems with up to 200 qubits containing the computational primitive. Quantum tunnelling may be advantageous for quantum annealing, but multiqubit tunnelling has not yet been observed or characterized theoretically. Here, the authors demonstrate that 8-qubit tunnelling plays a role in a D-Wave Two device through a nonperturbative theory and experimental data.
Collapse
|