Analog Errors in Quantum Annealing: Doom and Hope
arXiv:1907.12678 · doi:10.1038/s41534-020-00297-8
Abstract
Quantum annealing has the potential to provide a speedup over classical algorithms in solving optimization problems. Just as for any other quantum device, suppressing Hamiltonian control errors will be necessary before quantum annealers can achieve speedups. Such analog control errors are known to lead to -chaos, wherein the probability of obtaining the optimal solution, encoded as the ground state of the intended Hamiltonian, varies widely depending on the control error. Here, we show that -chaos causes a catastrophic failure of quantum annealing, in that the scaling of the time-to-solution metric becomes worse than that of a deterministic (exhaustive) classical solver. We demonstrate this empirically using random Ising spin glass problems run on the two latest generations of the D-Wave quantum annealers. We then proceed to show that this doomsday scenario can be mitigated using a simple error suppression and correction scheme known as quantum annealing correction (QAC). By using QAC, the time-to-solution scaling of the same D-Wave devices is improved to below that of the classical upper bound, thus restoring hope in the speedup prospects of quantum annealing.
arXiv comment16 pages, 16 figures
References in corpus (37)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Annealing in the Transverse Ising Model
- Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing
- Quantum annealing with more than one hundred qubits
- Quantum Annealing and Analog Quantum Computation
- Robustness of adiabatic quantum computation
- Quantum advantage with shallow circuits
- Bounds for the adiabatic approximation with applications to quantum computation
- Experimental signature of programmable quantum annealing
- Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
- Computational Role of Multiqubit Tunneling in a Quantum Annealer
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Error corrected quantum annealing with hundreds of qubits
- Experimental Demonstration of a Robust and Scalable Flux Qubit
- Application of Quantum Annealing to Training of Deep Neural Networks
- How Powerful is Adiabatic Quantum Computation?
- Probing for quantum speedup in spin glass problems with planted solutions
- A Cluster Monte Carlo Algorithm for 2-Dimensional Spin Glasses
- Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
- Reverse annealing for the fully connected -spin model
- Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
- Quantum annealing correction for random Ising problems
- Quantum Annealing Correction with Minor Embedding
- Adiabaticity in open quantum systems
- Benchmarking a quantum annealing processor with the time-to-target metric
- Exponential Speedup of Quantum Annealing by Inhomogeneous Driving of the Transverse Field
- Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
- Temperature and Disorder Chaos in Three-Dimensional Ising Spin Glasses
- The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
- Adiabatic quantum optimization with the wrong Hamiltonian
- Quantum annealing of the -spin model under inhomogeneous transverse field driving
- Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
- Nested Quantum Annealing Correction
- Quantum annealing correction at finite temperature: ferromagnetic -spin models
- Performance of two different quantum annealing correction codes
- Mean Field Analysis of Quantum Annealing Correction
- Scalable effective temperature reduction for quantum annealers via nested quantum annealing correction