Temperature scaling law for quantum annealing optimizers
arXiv:1703.03871 · doi:10.1103/PhysRevLett.119.110502
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.
arXiv comment11 pages, 11 figures. v2: Updated to published version
References in corpus (62)
- Quantum Mechanics helps in searching for a needle in a haystack
- Ising formulations of many NP problems
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- Quantum Annealing in the Transverse Ising Model
- Characterizing Quantum Supremacy in Near-Term Devices
- Boson Sampling on a Photonic Chip
- Quantum annealing with more than one hundred qubits
- Theory of Quantum Annealing of an Ising Spin Glass
- Photonic Boson Sampling in a Tunable Circuit
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Quantum Search by Local Adiabatic Evolution
- Defining and detecting quantum speedup
- Quantum Computation by Adiabatic Evolution
- Bounds for the adiabatic approximation with applications to quantum computation
- Architectural considerations in the design of a superconducting quantum annealing processor
- Average-case complexity versus approximate simulation of commuting quantum computations
- Experimental signature of programmable quantum annealing
- Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- Anderson localization casts clouds over adiabatic quantum optimization
- Error corrected quantum annealing with hundreds of qubits
- Achieving quantum supremacy with sparse and noisy commuting quantum computations
- Thermal and Residual Excited-State Population in a 3D Transmon Qubit
- Application of Quantum Annealing to Training of Deep Neural Networks
- First order phase transition in the Quantum Adiabatic Algorithm
- Fabrication Process and Properties of Fully-Planarized Deep-Submicron Nb/Al-AlOx/Nb Josephson Junctions for VLSI Circuits
- A scalable control system for a superconducting adiabatic quantum optimization processor
- Probing for quantum speedup in spin glass problems with planted solutions
- Searching for quantum speedup in quasistatic quantum annealers
- Error correcting codes for adiabatic quantum computation
- Consistency Tests of Classical and Quantum Models for a Quantum Annealer
- Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
- A scalable readout system for a superconducting adiabatic quantum optimization system
- The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
- Quantum annealing correction for random Ising problems
- Modernizing Quantum Annealing using Local Searches
- On the hardness of classically simulating the one clean qubit model
- Quantum Annealing Correction with Minor Embedding
- Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
- Adiabaticity in open quantum systems
- Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
- Benchmarking a quantum annealing processor with the time-to-target metric
- Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
- Inductance of Circuit Structures for MIT LL Superconductor Electronics Fabrication Process with 8 Niobium Layers
- Strong universality and algebraic scaling in two-dimensional Ising spin glasses
- Unraveling Quantum Annealers using Classical Hardness
- Microcanonical Approach to the Simulation of First-Order Phase Transitions
- Zero and low temperature behavior of the two-dimensional Ising spin glass
- Chaos and universality in two-dimensional Ising spin glasses
- Nested Quantum Annealing Correction
- Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
- Quantum annealing correction at finite temperature: ferromagnetic -spin models
- Mean Field Analysis of Quantum Annealing Correction
- Error suppression for Hamiltonian-based quantum computation using subsystem codes
- Universal critical behavior of the 2d Ising spin glass
- Relaxation vs. adiabatic quantum steady state preparation: which wins?
- Performance of a quantum annealer on range-limited constraint satisfaction problems
- Non-commuting two-local Hamiltonians for quantum error suppression
- Boosting quantum annealer performance via sample persistence
- Optimally Stopped Optimization
- Finite-size scaling in two-dimensional Ising spin glass models
- A PTAS for the Classical Ising Spin Glass Problem on the Chimera Graph Structure
Cited by in corpus (40)
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Challenges and Opportunities in Quantum Optimization
- Quantum Variational Autoencoder
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- Domain wall encoding of discrete variables for quantum annealing and QAOA
- 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
- Open quantum generalisation of Hopfield neural networks
- Scalable Emulation of Sign-ProblemFree Hamiltonians with Room Temperature p-bits
- Thermalization, freeze-out and noise: deciphering experimental quantum annealers
- Analog Errors in Ising Machines
- Calculation of molecular vibrational spectra on a quantum annealer
- Fast Route to Thermalization
- The Quantum Transition of the Two-Dimensional Ising Spin Glass: A Tale of Two Gaps
- A dissipative environment may improve the quantum annealing performances of the ferromagnetic p-spin model
- Improved Boltzmann machines with error corrected quantum annealing
- Scaling Advantage in Approximate Optimization with Quantum Annealing
- Comparing relaxation mechanisms in quantum and classical transverse-field annealing
- Scalable effective temperature reduction for quantum annealers via nested quantum annealing correction
- Understanding domain-wall encoding theoretically and experimentally
- Leveraging Adiabatic Quantum Computation for Election Forecasting
- Equation Planting: A Tool for Benchmarking Ising Machines
- Nested Quantum Annealing Correction at Finite Temperature: -spin models
- Making existing software quantum safe: a case study on IBM Db2
- Adiabatic theorem for closed quantum systems initialized at finite temperature
- Exponential capacity of associative memories under quantum annealing recall
- Thermometry and memcapacitance with qubit-resonator system
- A Quantum Extension of Variational Bayes Inference
- VanQver: The Variational and Adiabatically Navigated Quantum Eigensolver
- Large deviations of the ballistic Lévy walk model
- Quantum Annealing Machine based on Floating Gate Array
- Dynamics of open quantum systems by interpolation of von Neumann and classical master equations, and its application to quantum annealing
- Superconducting aluminum heat switch with 3 n equivalent resistance
- Noise-tolerant quantum speedups in quantum annealing without fine tuning
- Applications of Quantum Annealing in Statistics
- Solving rescheduling problems in heterogeneous urban railway networks using hybrid quantum-classical approach
- Understanding the physics of D-Wave annealers: From Schrödinger to Lindblad to Markovian Dynamics
- Exponential speedup of incoherent tunneling via dissipation
- Time-resolved tomography of a driven adiabatic quantum simulation
- Statistical quality assessment of Ising-based annealer outputs
- Finite temperature quantum condensations in the space of states: a new perspective for quantum annealing