Quantum annealing speedup over simulated annealing on random Ising chains
arXiv:1511.01906 · doi:10.1103/PhysRevB.93.224431
Abstract
We show clear evidence of a quadratic speedup of a quantum annealing (QA) Schroedinger dynamics over a Glauber master-equation simulated annealing (SA) for a random Ising model in one dimension, via an equal-footing exact deterministic dynamics of the Jordan-Wigner fermionized problems. This is remarkable, in view of the arguments of Katzgraber et al., PRX 4, 021008 (2014), since SA does not encounter any phase transition, while QA does. We also find a second remarkable result: that a "quantum-inspired" imaginary-time Schroedinger QA provides a further exponential speedup, i.e., an asymptotic residual error decreasing as a power-law of the annealing time .
arXiv commentRevised Abstract and Introduction. Removed 1 figure. Added references. Results unchanged. 5 pages, 2 figures
References in corpus (37)
- Quantum Mechanics helps in searching for a needle in a haystack
- Nonequilibrium dynamics of closed interacting quantum systems
- Quantum Annealing in the Transverse Ising Model
- Cosmological Experiments in Condensed Matter Systems
- Quantum annealing with more than one hundred qubits
- Dynamics of a Quantum Phase Transition
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing and Analog Quantum Computation
- Dynamics of quantum phase transition: exact solution in quantum Ising model
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Quantum Search by Local Adiabatic Evolution
- Mathematical Foundation of Quantum Annealing
- Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
- Computational Role of Multiqubit Tunneling in a Quantum Annealer
- A Numerical Study of the Random Transverse-Field Ising Spin Chain
- Quantum annealing of the Traveling Salesman Problem
- Entanglement in a quantum annealing processor
- Quantum versus Classical Annealing of Ising Spin Glasses
- Transition times in the Landau-Zener model
- Quantum phase transitions in transverse field spin models: from statistical physics to quantum information
- Adiabatic quantum dynamics of a random Ising chain across its quantum critical point
- Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
- The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
- Optimization by Quantum Annealing: Lessons from hard 3-SAT cases
- Dynamics of a quantum phase transition in the random Ising model
- Adiabatic quantum dynamics of the Lipkin-Meshkov-Glick model
- Universal nonequilibrium quantum dynamics in imaginary time
- A Quantum Approach to Classical Statistical Mechanics
- Optimization by Quantum Annealing: Lessons from Simple Cases
- Quantum versus classical annealing: insights from scaling theory and results for spin glasses on 3-regular graphs
- Comparative Study of the Performance of Quantum Annealing and Simulated Annealing
- Cooling dynamics of pure and random Ising chains
- Simulated quantum annealing of double-well and multi-well potentials
- Fast Quantum Methods for Optimization
- Monte Carlo studies of quantum and classical annealing on a double-well
- Adiabatic approximation for the imaginary-time Schroedinger equation and its application to simulated annealing
- Computational Bottlenecks of Quantum Annealing
Cited by in corpus (16)
- Coherent quantum annealing in a programmable 2000-qubit Ising chain
- Efficient partition of integer optimization problems with one-hot encoding
- Variational Neural Annealing
- Scaling and diabatic effects in quantum annealing with a D-Wave device
- Finite temperature quantum annealing solving exponentially small gap problem with non-monotonic success probability
- Entanglement transitions and quantum bifurcations under continuous long-range monitoring
- Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
- Discretized quantum adiabatic process for free fermions and comparison with the imaginary-time evolution
- Engineering non-equilibrium quantum phase transitions via causally gapped Hamiltonians
- On the dynamics of Simulated Quantum Annealing in random Ising chains
- A QUBO model of the RNA folding problem optimized by variational hybrid quantum annealing
- Efficient quantum and simulated annealing of Potts models using a half-hot constraint
- Difference between quantum annealing by imaginary-time and real-time Schrödinger equation of Grover's search
- Time-dependent Real-space Renormalization-Group Approach: application to an adiabatic random quantum Ising model
- Quantum combinatorial optimization beyond the variational paradigm: simple schedules for hard problems
- Mechanism of defect formation in the quantum annealing of the random transverse-field Ising chain