-
Computational supremacy in quantum simulation
Authors:
Andrew D. King,
Alberto Nocera,
Marek M. Rams,
Jacek Dziarmaga,
Roeland Wiersema,
William Bernoudy,
Jack Raymond,
Nitin Kaushal,
Niclas Heinsdorf,
Richard Harris,
Kelly Boothby,
Fabio Altomare,
Andrew J. Berkley,
Martin Boschnak,
Kevin Chern,
Holly Christiani,
Samantha Cibere,
Jake Connor,
Martin H. Dehn,
Rahul Deshpande,
Sara Ejtemaee,
Pau Farré,
Kelsey Hamer,
Emile Hoskinson,
Shuiyuan Huang
, et al. (37 additional authors not shown)
Abstract:
Quantum computers hold the promise of solving certain problems that lie beyond the reach of conventional computers. Establishing this capability, especially for impactful and meaningful problems, remains a central challenge. One such problem is the simulation of nonequilibrium dynamics of a magnetic spin system quenched through a quantum phase transition. State-of-the-art classical simulations dem…
▽ More
Quantum computers hold the promise of solving certain problems that lie beyond the reach of conventional computers. Establishing this capability, especially for impactful and meaningful problems, remains a central challenge. One such problem is the simulation of nonequilibrium dynamics of a magnetic spin system quenched through a quantum phase transition. State-of-the-art classical simulations demand resources that grow exponentially with system size. Here we show that superconducting quantum annealing processors can rapidly generate samples in close agreement with solutions of the Schrödinger equation. We demonstrate area-law scaling of entanglement in the model quench in two-, three- and infinite-dimensional spin glasses, supporting the observed stretched-exponential scaling of effort for classical approaches. We assess approximate methods based on tensor networks and neural networks and conclude that no known approach can achieve the same accuracy as the quantum annealer within a reasonable timeframe. Thus quantum annealers can answer questions of practical importance that classical computers cannot.
△ Less
Submitted 1 March, 2024;
originally announced March 2024.
-
Quantum Quench Dynamics of Geometrically Frustrated Ising Models
Authors:
Ammar Ali,
Hanjing Xu,
William Bernoudy,
Alberto Nocera,
Andrew D. King,
Arnab Banerjee
Abstract:
Geometric frustration in two-dimensional Ising models allows for a wealth of exotic universal behavior, both Ising and non-Ising, in the presence of quantum fluctuations. In particular, the triangular antiferromagnet and Villain model in a transverse field can be understood through distinct XY pseudospins, but have qualitatively similar phase diagrams including a quantum phase transition in the (2…
▽ More
Geometric frustration in two-dimensional Ising models allows for a wealth of exotic universal behavior, both Ising and non-Ising, in the presence of quantum fluctuations. In particular, the triangular antiferromagnet and Villain model in a transverse field can be understood through distinct XY pseudospins, but have qualitatively similar phase diagrams including a quantum phase transition in the (2+1)-dimensional XY universality class. While the quantum dynamics of modestly-sized systems can be simulated classically using tensor-based methods, these methods become infeasible for larger lattices. Here we perform both classical and quantum simulations of these dynamics, where our quantum simulator is a superconducting quantum annealer. Our observations on the triangular lattice suggest that the dominant quench dynamics are not described by the quantum Kibble-Zurek scaling of the quantum phase transition, but rather a faster coarsening dynamics in an effective two-dimensional XY model in the ordered phase. Similarly, on the Villain model, the scaling exponent does not match the Kibble-Zurek expectation. These results demonstrate the ability of quantum annealers to simulate coherent quantum dynamics and scale beyond the reach of classical approaches.
△ Less
Submitted 29 February, 2024;
originally announced March 2024.
-
Quantum error mitigation in quantum annealing
Authors:
Mohammad H. Amin,
Andrew D. King,
Jack Raymond,
Richard Harris,
William Bernoudy,
Andrew J. Berkley,
Kelly Boothby,
Anatoly Smirnov,
Fabio Altomare,
Michael Babcock,
Catia Baron,
Jake Connor,
Martin Dehn,
Colin Enderud,
Emile Hoskinson,
Shuiyuan Huang,
Mark W. Johnson,
Eric Ladizinsky,
Trevor Lanting,
Allison J. R. MacDonald,
Gaelen Marsden,
Reza Molavi,
Travis Oh,
Gabriel Poulin-Lamarre,
Hugh Ramp
, et al. (10 additional authors not shown)
Abstract:
Quantum Error Mitigation (QEM) presents a promising near-term approach to reduce error when estimating expectation values in quantum computing. Here, we introduce QEM techniques tailored for quantum annealing, using Zero-Noise Extrapolation (ZNE). We implement ZNE through zero-temperature extrapolation as well as energy-time rescaling. We conduct experimental investigations into the quantum critic…
▽ More
Quantum Error Mitigation (QEM) presents a promising near-term approach to reduce error when estimating expectation values in quantum computing. Here, we introduce QEM techniques tailored for quantum annealing, using Zero-Noise Extrapolation (ZNE). We implement ZNE through zero-temperature extrapolation as well as energy-time rescaling. We conduct experimental investigations into the quantum critical dynamics of a transverse-field Ising spin chain, demonstrating the successful mitigation of thermal noise through both of these techniques. Moreover, we show that energy-time rescaling effectively mitigates control errors in the coherent regime where the effect of thermal noise is minimal. Our ZNE results agree with exact calculations of the coherent evolution over a range of annealing times that exceeds the coherent annealing range by almost an order of magnitude.
△ Less
Submitted 2 November, 2023;
originally announced November 2023.
-
Hybrid quantum annealing for larger-than-QPU lattice-structured problems
Authors:
Jack Raymond,
Radomir Stevanovic,
William Bernoudy,
Kelly Boothby,
Catherine McGeoch,
Andrew J. Berkley,
Pau Farré,
Andrew D. King
Abstract:
Quantum processing units (QPUs) executing annealing algorithms have shown promise in optimization and simulation applications. Hybrid algorithms are a natural bridge to additional applications of larger scale. We present a straightforward and effective method for solving larger-than-QPU lattice-structured Ising optimization problems. Performance is compared against simulated annealing with promisi…
▽ More
Quantum processing units (QPUs) executing annealing algorithms have shown promise in optimization and simulation applications. Hybrid algorithms are a natural bridge to additional applications of larger scale. We present a straightforward and effective method for solving larger-than-QPU lattice-structured Ising optimization problems. Performance is compared against simulated annealing with promising results, and improvement is shown as a function of the generation of D-Wave QPU used.
△ Less
Submitted 7 February, 2022;
originally announced February 2022.
-
Performance benefits of increased qubit connectivity in quantum annealing 3-dimensional spin glasses
Authors:
Andrew D. King,
William Bernoudy
Abstract:
An important challenge in superconducting quantum computing is the need to physically couple many devices using quasi-two-dimensional fabrication processes. Recent advances in the design and fabrication of quantum annealing processors have enabled an increase in pairwise connectivity among thousands of qubits. One benefit of this is the ability to minor-embed optimization problems using fewer phys…
▽ More
An important challenge in superconducting quantum computing is the need to physically couple many devices using quasi-two-dimensional fabrication processes. Recent advances in the design and fabrication of quantum annealing processors have enabled an increase in pairwise connectivity among thousands of qubits. One benefit of this is the ability to minor-embed optimization problems using fewer physical qubits for each logical spin. Here we demonstrate the benefit of this progress in the problem of minimizing the energy of three-dimensional spin glasses. Comparing the previous generation D-Wave 2000Q system to the new Advantage system, we observe improved scaling of solution time and improved consistency over multiple graph embeddings.
△ Less
Submitted 25 September, 2020;
originally announced September 2020.
-
Scaling advantage in quantum simulation of geometrically frustrated magnets
Authors:
Andrew D. King,
Jack Raymond,
Trevor Lanting,
Sergei V. Isakov,
Masoud Mohseni,
Gabriel Poulin-Lamarre,
Sara Ejtemaee,
William Bernoudy,
Isil Ozfidan,
Anatoly Yu. Smirnov,
Mauricio Reis,
Fabio Altomare,
Michael Babcock,
Catia Baron,
Andrew J. Berkley,
Kelly Boothby,
Paul I. Bunyk,
Holly Christiani,
Colin Enderud,
Bram Evert,
Richard Harris,
Emile Hoskinson,
Shuiyuan Huang,
Kais Jooya,
Ali Khodabandelou
, et al. (29 additional authors not shown)
Abstract:
The promise of quantum computing lies in harnessing programmable quantum devices for practical applications such as efficient simulation of quantum materials and condensed matter systems. One important task is the simulation of geometrically frustrated magnets in which topological phenomena can emerge from competition between quantum and thermal fluctuations. Here we report on experimental observa…
▽ More
The promise of quantum computing lies in harnessing programmable quantum devices for practical applications such as efficient simulation of quantum materials and condensed matter systems. One important task is the simulation of geometrically frustrated magnets in which topological phenomena can emerge from competition between quantum and thermal fluctuations. Here we report on experimental observations of relaxation in such simulations, measured on up to 1440 qubits with microsecond resolution. By initializing the system in a state with topological obstruction, we observe quantum annealing (QA) relaxation timescales in excess of one microsecond. Measurements indicate a dynamical advantage in the quantum simulation over the classical approach of path-integral Monte Carlo (PIMC) fixed-Hamiltonian relaxation with multiqubit cluster updates. The advantage increases with both system size and inverse temperature, exceeding a million-fold speedup over a CPU. This is an important piece of experimental evidence that in general, PIMC does not mimic QA dynamics for stoquastic Hamiltonians. The observed scaling advantage, for simulation of frustrated magnetism in quantum condensed matter, demonstrates that near-term quantum devices can be used to accelerate computational tasks of practical relevance.
△ Less
Submitted 8 November, 2019;
originally announced November 2019.
-
Quantum-Assisted Genetic Algorithm
Authors:
James King,
Masoud Mohseni,
William Bernoudy,
Alexandre Fréchette,
Hossein Sadeghi,
Sergei V. Isakov,
Hartmut Neven,
Mohammad H. Amin
Abstract:
Genetic algorithms, which mimic evolutionary processes to solve optimization problems, can be enhanced by using powerful semi-local search algorithms as mutation operators. Here, we introduce reverse quantum annealing, a class of quantum evolutions that can be used for performing families of quasi-local or quasi-nonlocal search starting from a classical state, as novel sources of mutations. Revers…
▽ More
Genetic algorithms, which mimic evolutionary processes to solve optimization problems, can be enhanced by using powerful semi-local search algorithms as mutation operators. Here, we introduce reverse quantum annealing, a class of quantum evolutions that can be used for performing families of quasi-local or quasi-nonlocal search starting from a classical state, as novel sources of mutations. Reverse annealing enables the development of genetic algorithms that use quantum fluctuation for mutations and classical mechanisms for the crossovers -- we refer to these as Quantum-Assisted Genetic Algorithms (QAGAs). We describe a QAGA and present experimental results using a D-Wave 2000Q quantum annealing processor. On a set of spin-glass inputs, standard (forward) quantum annealing finds good solutions very quickly but struggles to find global optima. In contrast, our QAGA proves effective at finding global optima for these inputs. This successful interplay of non-local classical and quantum fluctuations could provide a promising step toward practical applications of Noisy Intermediate-Scale Quantum (NISQ) devices for heuristic discrete optimization.
△ Less
Submitted 24 June, 2019;
originally announced July 2019.
-
Comment on "Scaling advantages of all-to-all connectivity in physical annealers: the Coherent Ising Machine vs D-Wave 2000Q" [arXiv:1805.05217]
Authors:
Catherine C. McGeoch,
William Bernoudy,
James King
Abstract:
A recent paper [arXiv:1805.05217] compares performance of a D-Wave 2000Q system to two versions of the coherent Ising machine (CIM). This comment points out some flaws in the analysis, which undermine several of the conclusions drawn in the paper.
A recent paper [arXiv:1805.05217] compares performance of a D-Wave 2000Q system to two versions of the coherent Ising machine (CIM). This comment points out some flaws in the analysis, which undermine several of the conclusions drawn in the paper.
△ Less
Submitted 29 June, 2018;
originally announced July 2018.
-
Emulating the coherent Ising machine with a mean-field algorithm
Authors:
Andrew D. King,
William Bernoudy,
James King,
Andrew J. Berkley,
Trevor Lanting
Abstract:
The coherent Ising machine is an optical processor that uses coherent laser pulses, but does not employ coherent quantum dynamics in a computational role. Core to its operation is the iterated simulation of all-to-all spin coupling via mean-field calculation in a classical FPGA coprocessor. Although it has been described as "operating at the quantum limit" and a "quantum artificial brain", interac…
▽ More
The coherent Ising machine is an optical processor that uses coherent laser pulses, but does not employ coherent quantum dynamics in a computational role. Core to its operation is the iterated simulation of all-to-all spin coupling via mean-field calculation in a classical FPGA coprocessor. Although it has been described as "operating at the quantum limit" and a "quantum artificial brain", interaction with the FPGA prevents the coherent Ising machine from exploiting quantum effects in its computations. Thus the question naturally arises: Can the optical portion of the coherent Ising machine be replaced with classical mean-field arithmetic? Here we answer this in the affirmative by showing that a straightforward noisy version of mean-field annealing closely matches CIM performance scaling, while running roughly 20 times faster in absolute terms.
△ Less
Submitted 21 June, 2018;
originally announced June 2018.