Quantum Approximate Optimization Algorithm (QAOA)

The Quantum Approximate Optimization Algorithm (QAOA) is a heuristic to design variational Ansätze for combinatorial optimization. It is inspired from the digitalization of an analog evolution using a linear ramp, starting from a simple initial Hamiltonian \(H_0 = - \sum_i \sigma_x^i\) to a diagonal Hamiltonian whose ground state encodes the solution to our problem.

The circuits produced by this method have the following shape:

where \(H_0 = - \sum_i \sigma_x^i\), and \(H_C\) is an (efficiently generated) classical cost Hamiltonian that encodes the cost function to optimize. The propagator \(e^{i\gamma H_C}\) is usually simple to implement from a problem specification. \(e^{i\beta H_0}\) simply corresponds to a collection of \(R_X\) rotations of angle \(2\beta\).

Once such a circuit is produced, one can use a QPU, along with a classical optimizer, to minimize the quantity: \(\langle 0|C(\gamma, \beta)^\dagger H_C C(\gamma, \beta)|0 \rangle\) in order to produce a quantum state with the lowest possible energy (i.e that overlaps well with the proper ground state of \(H_C\), which, by construction, corresponds to the optimal solution of our problem). This can be handled via a variational plugin on Qaptiva.

As you can see, the circuit is also parametrized by a depth \(d\) corresponding to the number of alternating variational layers. The larger the depth, the better the approximation of the solution (at least in theory). In practice, increasing this parameter yields a larger circuit with greater number of parameters to optimize, which can slow down the convergence of the algorithm (which is fully described in [FGG14]).

It is possible to directly generate ready to run QAOA jobs (containing an Ansatz and the target Hamiltonian) from an instance of CombinatorialProblem/QUBO/Ising via the CircuitGenerator class from which they inherit. In that case Qaptiva will take care of generating a cost Hamiltonian for the problem (depending on how it is specified).

If you need a lower level interface, the AnsatzFactory provides a recipe to produce such a variational circuit from a target Hamiltonian. In both cases, the Ansatz factory allows you to pick between (at least) three different circuit synthesis strategies, yielding functionally equivalent circuits with different shapes.

Bibliography

FGG14

Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. 2014. arXiv:1411.4028.