Noise amplification at spin-glass bottlenecks of quantum annealing: a solvable model

Abstract

To gain better insight into the complexity theory of quantum annealing, we propose and solve a class of spin systems which contain bottlenecks of the kind expected to dominate the runtime of quantum annealing as it tries to solve difficult optimization problems. We uncover a noise amplification effect at these bottlenecks, whereby tunneling rates caused by flux-qubit noise scale in proportion to the number of qubits $N$ in the limit that $N\to \infty$. By solving the incoherent annealing dynamics exactly, we find a wide range of regimes where the probability that a quantum annealer remains in the ground-state upon exiting the bottleneck is close to one-half. We corroborate our analysis with detailed simulations of the performance of the D-Wave 2X quantum annealer on our class of computational problems.

18 pages, 12 figures

References in corpus (6)

• Observation of topological phenomena in a programmable lattice of 1,800 qubits
• Reverse Quantum Annealing Approach to Portfolio Optimization Problems
• Compiling quantum circuits to realistic hardware architectures using temporal planners
• Convergence theorems for quantum annealing
• Experimental demonstration of perturbative anticrossing mitigation using non-uniform driver Hamiltonians
• Decoherence induced deformation of the ground state in adiabatic quantum computation

Cited by in corpus (9)

• Comparing relaxation mechanisms in quantum and classical transverse-field annealing
• Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization
• Diabatic Quantum Annealing for the Frustrated Ring Model
• Ising Hamiltonian Minimization: Gain-Based Computing with Manifold Reduction of Soft-Spins vs Quantum Annealing
• Beyond Quantum Annealing: Optimal control solutions to MaxCut problems
• Theoretical survey of unconventional quantum annealing methods applied to adifficult trial problem
• Fighting Exponentially Small Gaps by Counterdiabatic Driving
• Frustration-enhanced quantum annealing correction models with additional inter-replica interactions
• Digital controllability of transverse field Ising chains