Quantum approximate optimization algorithm

In quantum computing, The Quantum Approximate Optimization Algorithm (QAOA) is an iterative NISQ-era quantum algorithm designed to solve combinatorial optimization problems. This algorithm was first proposed by Farhi, Goldstone, and Gutmann in 2014^[1] to find approximate solutions to the MaxCut problem. This algorithm is based on variational principle, much like the Variational quantum eigensolver (VQE).

QAOA is a hybrid quantum-classical approach that leverages the principles of both quantum mechanics and classical optimization to solve problems more efficiently than conventional algorithms. The algorithm utilizes a quantum computer to prepare a quantum state according to a set of variational parameters, which are then refined through a classical process that iteratively optimizes the parameters based on the outcomes of these quantum computations. In the QAOA, the quantum state is prepared by a ${\displaystyle p}$-level circuit specified by ${\displaystyle 2p}$ variational parameters.

The development and study of the QAOA are motivated by the promise of quantum advantage. As of now, QAOA has not demonstrated a provable quantum speed-up over classical algorithms for any practically relevant task with NISQ devices.^[2][3] The potential of QAOA compared to classical algorithms remains an active area of study, fueled by ongoing research.^[4]

Description

Combinatorial optimization problems are represented on a classical cost function ${\displaystyle C(z)}$ defined on ${\displaystyle n}$-bit strings ${\displaystyle z=(z_{1},z_{2},...,z_{n})}$. The fundamental concept of QAOA is to encode the objective function into the problem Hamiltonian ${\displaystyle {\hat {H}}_{P}}$, aiming to identify an optimal bit string ${\displaystyle z^{*}}$ so that that ${\displaystyle C(z)}$ is approximate to its absolute minimum. The original QAOA ^[1] follows below steps:

1. Define a problem Hamiltonian ${\displaystyle {\hat {H}}_{P}}$ such that it encodes the solution to the optimization problem. Define a mixing Hamiltonian ${\displaystyle {\hat {H}}_{m}}$. Generally, with computational basis vector ${\displaystyle |z\rangle }$, one can map the problem Hamiltonian as ${\displaystyle {\hat {H}}_{P}|z\rangle =C(z)\ |z\rangle }$. Mixing Hamiltonian ${\displaystyle {\hat {H}}_{m}}$ is usually define as ${\displaystyle {\hat {H}}_{m}=\sum _{i=1}^{n}\sigma _{x}^{i}}$, where ${\displaystyle \sigma _{x}}$ is the Pauli-x gate acting on qubit ${\displaystyle i}$.
2. Initialize the quamtum circuit to be in the state ${\displaystyle |s\rangle ={\frac {1}{\sqrt {2^{n}}}}\ \sum _{z}|z\rangle }$, where n is the number of qubits.
3. Construct the ansatz by defining the two unitaries related to the two operators: ${\displaystyle {\hat {U}}_{p}(\gamma )\ =\ e^{-i\gamma {\hat {H}}_{P}};\ {\hat {U}}_{m}(\beta )\ =\ e^{-i\beta {\hat {H}}_{m}}=\prod _{i=1}^{n}e^{-i\beta \sigma _{x}^{i}}}$, where ${\displaystyle \gamma }$ and ${\displaystyle \beta }$ are variational parameters of the circuit.
4. Set the total layer depth of the algorithm, ${\displaystyle p}$, where ${\displaystyle p}$ is a positive integer.
5. Initialize the ${\displaystyle 2p}$ variational parameters and ${\displaystyle p}$ layers of ${\displaystyle {\hat {U}}_{p}(\gamma )\ }$ and ${\displaystyle {\hat {U}}_{m}(\beta )}$ are applied to the initial state ${\displaystyle |s\rangle }$. let ${\displaystyle \mathbf {\gamma } \ =\ \gamma _{1},\gamma _{2},...,\gamma _{p}}$ and ${\displaystyle \mathbf {\beta } =\ \beta _{1},\beta _{2},...,\beta _{p}}$, then the circuit prepares the final state ${\displaystyle |\psi (\gamma ,\ \beta )\rangle =e^{-i\gamma _{p}{\hat {H}}_{P}}e^{-i\beta _{p}{\hat {H}}_{m}}...e^{-i\gamma _{1}{\hat {H}}_{P}}e^{-i\beta _{1}{\hat {H}}_{m}}|s\rangle }$.
6. For the given problem Hamiltonian ${\displaystyle {\hat {H}}_{P}}$, the expectation value of the Hamiltonian is represented by the objective function ${\displaystyle \langle \psi (\gamma ,\ \beta )|{\hat {H}}_{P}|\psi (\gamma ,\ \beta )\rangle }$. The final state is then measured in the computational basis.
7. A classical optimization routine is used to iteratively adjust the parameters ${\displaystyle \gamma }$ and ${\displaystyle \beta }$. The purpose of this process is to identify the optimal parameters (${\displaystyle \gamma ^{*}}$, ${\displaystyle \beta ^{*}}$) that maximize the expectation value.

See also

• Quantum optimization algorithms
• Variational quantum eigensolver

References

External Links

• Implementation of QAOA on a MaxCut problem using Qiskit, IBM Quantum Platform, IBM Quantum Learning