Quantum versus Classical Annealing of Ising Spin Glasses
arXiv:1411.5693 · doi:10.1126/science.aaa4170
Abstract
The strongest evidence for superiority of quantum annealing on spin glass problems has come from comparing simulated quantum annealing using quantum Monte Carlo (QMC) methods to simulated classical annealing [G. Santoro et al., Science 295, 2427(2002)]. Motivated by experiments on programmable quantum annealing devices we revisit the question of when quantum speedup may be expected for Ising spin glass problems. We find that even though a better scaling compared to simulated classical annealing can be achieved for QMC simulations, this advantage is due to time discretization and measurements which are not possible on a physical quantum annealing device. QMC simulations in the physically relevant continuous time limit, on the other hand, do not show superiority. Our results imply that care has to be taken when using QMC simulations to assess quantum speedup potential and are consistent with recent arguments that no quantum speedup should be expected for two-dimensional spin glass problems.
References in corpus (8)
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantum annealing with more than one hundred qubits
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing and Analog Quantum Computation
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Defining and detecting quantum speedup
- Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
Cited by in corpus (108)
- Microwave photonics with superconducting quantum circuits
- Quantum generalisation of feedforward neural networks
- Quantum critical dynamics in a 5000-qubit programmable spin glass
- Bifurcation-based adiabatic quantum computation with a nonlinear oscillator network: Toward quantum soft computing
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Probing for quantum speedup in spin glass problems with planted solutions
- Optimizing Variational Quantum Algorithms using Pontryagin's Minimum Principle
- Towards quantum simulation with circular Rydberg atoms
- Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
- Modernizing Quantum Annealing using Local Searches
- Quantum Annealing Correction with Minor Embedding
- Quantum bits with Josephson junctions
- Scaling and diabatic effects in quantum annealing with a D-Wave device
- Tunneling and speedup in quantum optimization for permutation-symmetric problems
- Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
- A deceptive step towards quantum speedup detection
- Autonomous Probabilistic Coprocessing with Petaflips per Second
- Efficiency of quantum versus classical annealing in non-convex learning problems
- Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
- Stabilisers as a design tool for new forms of Lechner-Hauke-Zoller Annealer
- Non-ergodic delocalized states for efficient population transfer within a narrow band of the energy landscape
- Non-Stoquastic Interactions in Quantum Annealing via the Aharonov-Anandan Phase
- Scalable Emulation of Sign-ProblemFree Hamiltonians with Room Temperature p-bits
- Uncertain fate of fair sampling in quantum annealing
- Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms
- Maximum-Entropy Inference with a Programmable Annealer
- Low depth mechanisms for quantum optimization
- Readiness of Quantum Optimization Machines for Industrial Applications
- Travel time optimization on multi-AGV routing by reverse annealing
- Quantum annealing with ultracold atoms in a multimode optical resonator
- Probabilistic Nonunitary Gate in Imaginary Time Evolution
- Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
- Scaling overhead of embedding optimization problems in quantum annealing
- Heavy tails in the distribution of time-to-solution for classical and quantum annealing
- Projective quantum Monte Carlo simulations guided by unrestricted neural network states
- Quantum Monte Carlo tunneling from quantum chemistry to quantum annealing
- Quantum annealing via environment-mediated quantum diffusion
- Wavelength-division multiplexing optical Ising simulator enabling fully programmable spin couplings and external magnetic fields
- Simulated quantum annealing as a simulator of non-equilibrium quantum dynamics
- Practical Integer-to-Binary Mapping for Quantum Annealers
- Controlled Online Optimization Learning (COOL): Finding the ground state of spin Hamiltonians with reinforcement learning
- Self-learning projective quantum Monte Carlo simulations guided by restricted Boltzmann machines
- Quantum Monte Carlo Simulations of Tunneling in Quantum Adiabatic Optimization
- Benchmarking digital quantum simulations above hundreds of qubits using quantum critical dynamics
- Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
- Boosting quantum annealer performance via sample persistence
- Simulated Quantum Annealing with Two All-to-All Connectivity Schemes
- Off-Diagonal Expansion Quantum Monte Carlo
- Open system quantum annealing in mean field models with exponential degeneracy
- Quantum annealing speedup over simulated annealing on random Ising chains
- Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian
- Application of Pontryagin's Minimum Principle to Grover's Quantum Search Problem
- Quantum Optimisation of Complex Systems with a Quantum Annealer
- Quantum trajectories for time-dependent adiabatic master equations
- Simulated quantum annealing of double-well and multi-well potentials
- Optimal working point in digitized quantum annealing
- Computational hardness of spin-glass problems with tile-planted solutions
- Assessment of Quantum Annealing for the Construction of Satisfiability Filters
- Classical-quantum crossover in the critical behavior of the transverse field S-K spin glass model
- Understanding Quantum Tunneling using Diffusion Monte Carlo Simulations
- Error suppression in adiabatic quantum computing with qubit ensembles
- Spectral Gap Analysis for Efficient Tunneling in Quantum Adiabatic Optimization
- Quantum-inspired classical algorithm for molecular vibronic spectra
- Viewing Vanilla Quantum Annealing Through Spin Glasses
- Exponential capacity of associative memories under quantum annealing recall
- Dual time scales in simulated annealing of a two-dimensional Ising spin glass
- Exploring Quantum Annealing Architectures: A Spin Glass Perspective
- Patch-planting spin-glass solution for benchmarking
- A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing
- Ising Hamiltonian Minimization: Gain-Based Computing with Manifold Reduction of Soft-Spins vs Quantum Annealing
- Cluster state generation in one-dimensional Kitaev honeycomb model via shortcut to adiabaticity
- A theory of non-equilibrium local search on random satisfaction problems
- A comparison between D-wave and a classical approximation algorithm and a heuristic for computing the ground state of an Ising spin glass
- Reweight-annealing method for evaluating the partition function via quantum Monte Carlo calculations
- Supervised learning of random quantum circuits via scalable neural networks
- On the dynamics of Simulated Quantum Annealing in random Ising chains
- Tunneling in projective quantum Monte Carlo simulations with guiding wave functions
- Deterministic Quantum Annealing Expectation-Maximization Algorithm
- Quantum optimization within lattice gauge theory model on a quantum simulator
- Extracting the lifetime of a synthetic two-level system
- Toward Practical Benchmarks of Ising Machines: A Case Study on the Quadratic Knapsack Problem
- Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers
- Unraveling the origin of higher success probabilities in quantum versus semi-classical annealing
- Many-body quantum sign structures as non-glassy Ising models
- Demonstration of long-range correlations via susceptibility measurements in a one-dimensional superconducting Josephson spin chain
- Why adiabatic quantum annealing is unlikely to yield speed-up
- Quantum Monte Carlo Annealing with Multi-Spin Dynamics
- Subspace projection method for unstructured searches with noisy quantum oracles using a signal-based quantum emulation device
- From quantum-enhanced to quantum-inspired Monte Carlo
- Path-Integral Quantum Monte Carlo simulation with Open-Boundary Conditions
- Quantum computing for data science
- Exploring the topological sector optimization on quantum computers
- Convergence condition of simulated quantum annealing for closed and open systems
- Performance of quantum annealing for 2-SAT problems with multiple satisfying assignments
- Tunneling time from spin fluctuations in Larmor clock
- Quantum annealing showing an exponentially small success probability despite a constant energy gap with polynomial energy
- Boosting quantum annealing performance through direct polynomial unconstrained binary optimization
- Entanglement-assisted variational algorithm for discrete optimization problems
- Diabatic quantum and classical annealing of the Sherrington-Kirkpatrick model
- Development of research network on Quantum Annealing Computation and Information using Google Scholar data
- Discrepancies between Asymptotic and Exact Spectral Gap Analyses of Quantum Adiabatic Barrier Tunneling
- Compressed sensing enhanced by quantum approximate optimization algorithm
- Hybrid classical-quantum branch-and-bound algorithm for solving integer linear problems
- Transfer Learning for Deep-Unfolded Combinatorial Optimization Solver with Quantum Annealer
- Optimal Quantum Likelihood Estimation
- Generalized Interference of Fermions and Bosons
- Testing Quantum and Simulated Annealers on the Drone Delivery Packing Problem
- Topological and geometric patterns in optimal bang-bang protocols for variational quantum algorithms: application to the model on the square lattice