An introduction to quantum annealing
arXiv:1107.0794 · doi:10.1051/ita/2011013
Abstract
Quantum Annealing, or Quantum Stochastic Optimization, is a classical randomized algorithm which provides good heuristics for the solution of hard optimization problems. The algorithm, suggested by the behaviour of quantum systems, is an example of proficuous cross contamination between classical and quantum computer science. In this survey paper we illustrate how hard combinatorial problems are tackled by quantum computation and present some examples of the heuristics provided by Quantum Annealing. We also present preliminary results about the application of quantum dissipation (as an alternative to Imaginary Time Evolution) to the task of driving a quantum system toward its state of lowest energy.
References in corpus (21)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Concepts and methods in the theory of open quantum systems
- Quantum Computation by Adiabatic Evolution
- Mathematical Foundation of Quantum Annealing
- Anderson localization casts clouds over adiabatic quantum optimization
- How Powerful is Adiabatic Quantum Computation?
- Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
- First Order Quantum Phase Transition in Adiabatic Quantum Computation
- Adiabatic Quantum Computing for Random Satisfiability Problems
- Time-Dependent Density Functional Theory for Open Quantum Systems with Unitary Propagation
- An Elementary Proof of the Quantum Adiabatic Theorem
- Exponential complexity of an adiabatic algorithm for an NP-complete problem
- Optimization by Quantum Annealing: Lessons from Simple Cases
- On product, generic and random generic quantum satisfiability
- Efficient algorithm for a quantum analogue of 2-SAT
- Quantum Annealing for Clustering
- Quantum annealing and the Schrödinger-Langevin-Kostin equation
- Speed and entropy of an interacting continuous time quantum walk
- Phase transitions and random quantum satisfiability
- Quantum Annealing for Clustering
Cited by in corpus (12)
- Quantum Computing: An Overview Across the System Stack
- Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms
- Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems
- Complex semiclassical analysis of the Loschmidt amplitude and dynamical quantum phase transitions
- Quantum Annealing Approach for the Optimal Real-time Traffic Control using QUBO
- Using Quantum Annealers to Calculate Ground State Properties of Molecules
- Quantum annealing and the Schrödinger-Langevin-Kostin equation
- Deterministic Quantum Annealing Expectation-Maximization Algorithm
- Load Balancing For High Performance Computing Using Quantum Annealing
- TORM: Fast and Accurate Trajectory Optimization of Redundant Manipulator given an End-Effector Path
- Relaxation of the EM Algorithm via Quantum Annealing
- Relaxation of the EM Algorithm via Quantum Annealing for Gaussian Mixture Models