Noise amplification at spin-glass bottlenecks of quantum annealing: a solvable model
arXiv:1909.00322 · doi:10.1103/PhysRevA.101.042317
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 in the limit that . 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.
arXiv comment18 pages, 12 figures
References in corpus (24)
- Local unitary transformation, long-range quantum entanglement, wave function renormalization, and topological order
- Quantum annealing with more than one hundred qubits
- Theory of Quantum Annealing of an Ising Spin Glass
- Dynamics of quantum phase transition: exact solution in quantum Ising model
- Topological quantum order: stability under local perturbations
- Observation of topological phenomena in a programmable lattice of 1,800 qubits
- Anderson localization casts clouds over adiabatic quantum optimization
- Reverse Quantum Annealing Approach to Portfolio Optimization Problems
- Computational Role of Multiqubit Tunneling in a Quantum Annealer
- A case study in programming a quantum annealer for hard operational planning problems
- Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
- First order phase transition in the Quantum Adiabatic Algorithm
- Searching for quantum speedup in quasistatic quantum annealers
- Compiling quantum circuits to realistic hardware architectures using temporal planners
- Role of Single Qubit Decoherence Time in Adiabatic Quantum Computation
- Dissipation in adiabatic quantum computers: Lessons from an exactly solvable model
- Convergence theorems for quantum annealing
- Thermalization, freeze-out and noise: deciphering experimental quantum annealers
- Experimental demonstration of perturbative anticrossing mitigation using non-uniform driver Hamiltonians
- Heavy tails in the distribution of time-to-solution for classical and quantum annealing
- Degeneracy, degree, and heavy tails in quantum annealing
- Form-factors of the finite quantum XY-chain
- Decoherence induced deformation of the ground state in adiabatic quantum computation
- Computational Bottlenecks of Quantum Annealing
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