Fast Quantum Methods for Optimization

Abstract

Discrete combinatorial optimization consists in finding the optimal configuration that minimizes a given discrete objective function. An interpretation of such a function as the energy of a classical system allows us to reduce the optimization problem into the preparation of a low-temperature thermal state of the system. Motivated by the quantum annealing method, we present three strategies to prepare the low-temperature state that exploit quantum mechanics in remarkable ways. We focus on implementations without uncontrolled errors induced by the environment. This allows us to rigorously prove a quantum advantage. The first strategy uses a classical-to-quantum mapping, where the equilibrium properties of a classical system in $d$ spatial dimensions can be determined from the ground state properties of a quantum system also in $d$ spatial dimensions. We show how such a ground state can be prepared by means of quantum annealing, including quantum adiabatic evolutions. This mapping also allows us to unveil some fundamental relations between simulated and quantum annealing. The second strategy builds upon the first one and introduces a technique called spectral gap amplification to reduce the time required to prepare the same quantum state adiabatically. If implemented on a quantum device that exploits quantum coherence, this strategy leads to a quadratic improvement in complexity over the well-known bound of the classical simulated annealing method. The third strategy is not purely adiabatic; instead, it exploits diabatic processes between the low-energy states of the corresponding quantum system. For some problems it results in an exponential speedup (in the oracle model) over the best classical algorithms.

15 pages (2 figures)

References in corpus (31)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Annealing in the Transverse Ising Model
• Ultracold atomic gases in optical lattices: mimicking condensed matter physics and beyond
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Exponential algorithmic speedup by quantum walk
• Quantum annealing with more than one hundred qubits
• Theory of Quantum Annealing of an Ising Spin Glass
• Shortcuts to adiabaticity
• Quantum Annealing: A New Method for Minimizing Multidimensional Functions
• Defining and detecting quantum speedup
• Criticality, the area law, and the computational power of PEPS
• Mathematical Foundation of Quantum Annealing
• Bounds for the adiabatic approximation with applications to quantum computation
• Exponential improvement in precision for simulating sparse Hamiltonians
• Quantum Simulations of Classical Annealing Processes
• Quantum Speedup by Quantum Annealing
• Optimized simulated annealing for Ising spin glasses
• Beyond the Quantum Adiabatic Approximation: Adiabatic Perturbation Theory
• From quantum mechanics to classical statistical physics: generalized Rokhsar-Kivelson Hamiltonians and the "Stochastic Matrix Form" decomposition
• From classical to quantum dynamics at Rokhsar-Kivelson points
• How "Quantum" is the D-Wave Machine?
• A Quantum Approach to Classical Statistical Mechanics
• Different Strategies for Optimization Using the Quantum Adiabatic Algorithm
• Convergence theorems for quantum annealing
• Spectral Gap Amplification
• The Adiabatic Theorem for Quantum Systems with Spectral Degeneracy
• Adiabatic Perturbation Theory and Geometric Phases for Degenerate Systems
• Quantum Computation Beyond the Circuit Model
• Degenerate Adiabatic Perturbation Theory: Foundations and Applications
• Improved Bounds for Eigenpath Traversal
• Fast quantum algorithms for traversing paths of eigenstates

Cited by in corpus (8)

• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Controlling quantum critical dynamics of isolated systems
• Quantum Sampling Algorithms for Near-Term Devices
• Quantum annealing speedup over simulated annealing on random Ising chains
• Quantum Sampling Algorithms, Phase Transitions, and Computational Complexity
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
• Q-CHOP: Quantum constrained Hamiltonian optimization