Fast quantum methods for optimization
Venue
The European Physical Journal Special Topics, vol. 224 (2015), pp. 35
Publication Year
2015
Authors
S. Boixo, G. Ortiz, R. Somma
BibTeX
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.
