Adiabatic Quantum Optimization (AQO)

Adiabatic Quantum Optimization (AQO) is a generic optimization framework that utilizes a continuous quantum dynamic to find the global minimum of a target function. In practice, this framework is often applied to combinatorial optimization since combinatorial cost functions are usually simple to encode into a Hamiltonian.

A generic AQO is defined using a target Hamiltonian \(H_{C}\) such that:

\[H_C | x\rangle = C(x)|x\rangle\]

encodes a cost function \(C\), and using a problem-independent mixing Hamiltonian \(H_0\) such that:

\[[H_C, H_0] \neq 0\]

The quantum system is prepared in the (problem-independent) ground state of \(H_0\) and evolved slowly according to the following time-dependent Hamiltonian:

\[H(t) = (1 - \frac{t}{T}) H_0 + \frac{t}{T} H_C\]

during a time \(T\). For large \(T\), the adiabatic theorem states that the final quantum state will ‘largely’ overlap with the ground state of \(H_C\). Thus, measuring this quantum state in the computational basis will produce the global minimum of \(C\) with a large probability.

It is possible to automatically generate aqo jobs from any of the NP-hard problems description classes. For instance, the following piece of code produces an AQO job for a MaxCut instance:

from qat.opt import MaxCut
import networkx as nx

graph = nx.generators.erdos_renyi_graph(10, 0.5)
problem = MaxCut(graph)
# We just need to specify the value of T (tmax)
aqo_job = problem.to_job("aqo", tmax=47)

The default mixing Hamitonian (\(H_0\)) is :

\[H_0 = - \sum \sigma_x^{(i)}\]

Its ground state is \(|+\rangle^{\otimes n}\) (a simple product state).

Some applications may require more advanced mixing Hamiltonians. Qaptiva comes with a few mixing Hamiltonians already pre-programmed in a MixingFactory.

One can, for instance, define a bit-move mixing Hamiltonian that will mix the subspaces of constant Hamming weights. This is useful when one needs to restrict the search to bit-strings of a fixed Hamming weight:

from qat.opt import MaxCut, MixingFactory
import networkx as nx

graph = nx.generators.erdos_renyi_graph(10, 0.5)
problem = MaxCut(graph)

# Looking for a solution of Hamming weight 3
mixing = MixingFactory.bit_move(10, 3)
aqo_job = problem.to_job("aqo", tmax=47, mixing=mixing)

Doing this will effectively change the mixing Hamiltonian, and, of course, the initial state of the computation. This change can lead to an increase in the computation time since some mixing Hamiltonians have non-trivial ground states whose preparation might involve a problem-independent optimization to take place before the true optimization.