QAOA Algorithm¶
This page describes the mathematical framework of QAOA (Quantum Approximate Optimization Algorithm)[1].
The Optimization Problem Solved by QAOA¶
QAOA is an algorithm that solves combinatorial optimization problems using quantum computers and classical optimization. Specifically, QAOA handles the class of problems known as Polynomial Unconstrained Binary Optimization (PUBO).
As the name suggests, PUBO involves minimizing an objective function expressed as a polynomial of binary variables \(x = (x_1, x_2, \ldots, x_n) \quad (x_i \in \{0,1\},\ i=1,2,\ldots,n)\) without constraints (unconstrained). Formally, with \(f\) as a polynomial in \(x\):
In quantum computing, it is generally more convenient to work with Ising variables \(z = (z_1, z_2, \ldots, z_n), \quad z_i \in \{-1,1\}\) rather than binary variables \(x \in \{0,1\}^n\). Therefore, given a binary function \(f(x)\) to optimize, we apply the variable transformation \(z_i = 2x_i - 1\) and define an equivalent Ising function \(\tilde f\) such that \(\tilde f(z) = f(x)\). In what follows, we consider the minimization of this Ising function \(\tilde f(z)\).
Important
In the Amplify SDK, binary variables \(x \in \{0,1\}\) and Ising variables \(z \in \{-1,1\}\) satisfy the following relationship:
Since \(z\) is defined in terms of \(x\), and \(f(x)\) is a polynomial in \(x\), it follows that \(\tilde f(z)\) is also a polynomial in \(z\).
In the following, we denote each monomial composing the polynomial \(\tilde f(z)\) as \(\tilde f_{\alpha}(z)\), and write:
Quantum States¶
Before describing QAOA itself, let us briefly review how information is represented in quantum computers.
In classical computing, information is represented as sequences of “bits” consisting of \(0\) and \(1\). In the quantum computing world, the analog of a bit is called a qubit, which is represented as a complex-valued 2-dimensional vector normalized to unit length — a quantum state.
While a classical bit takes only one of two values, \(0\) or \(1\), a qubit can exist in a richer variety of quantum states. Mathematically, a quantum state \(\ket{\psi}\) is represented as a column vector \((\alpha,\beta)^T\) with complex numbers \(\alpha, \beta\) satisfying \(|\alpha|^2 + |\beta|^2 = 1\). In quantum information, one typically defines an orthonormal basis \(\{\ket{0}, \ket{1}\}\) with \(\ket{0} = (1,0)^{T},\quad \ket{1} = (0,1)^{T}\) and writes:
This orthonormal basis is called the computational basis. Throughout this document, all matrix representations of quantum states are given in the computational basis.
In general, an \(n\)-qubit quantum state is represented by a \(2^n\)-dimensional complex vector. The basic principles are the same as in the single-qubit case.
Hamiltonians¶
In QAOA, the given objective function is converted into a Hermitian operator acting on qubits, and its value is evaluated on the quantum computer. This operator corresponding to the objective function is called the Hamiltonian.
Mathematically, a Hermitian operator is a linear operator whose conjugate transpose (transpose combined with complex conjugation) equals itself. As an example, consider the matrix representation for a single qubit (2-dimensional complex vector space). A linear operator expressed using complex numbers \(a,b,c,d\):
is Hermitian if and only if its conjugate transpose
satisfies \(A^\dagger = A\). From this condition, any single-qubit Hermitian operator \(A\) can be expressed using real numbers \(x,y\) and a complex number \(z\) as:
Important examples of single-qubit Hermitian operators are the Pauli operators. In matrix form:
These are called the identity operator \(I\), Pauli \(X\) operator, Pauli \(Y\) operator, and Pauli \(Z\) operator, respectively.
As described in Hamiltonian Construction, QAOA constructs the Hamiltonian by replacing the Ising variables in the objective function with Pauli \(Z\) operators.
From the definition of the Pauli \(Z\) operator, the computational basis \(\{\ket{0}, \ket{1}\}\) consists of eigenvectors of the Pauli \(Z\) operator. In particular:
That is, the Pauli \(Z\) operator takes the value \(Z = 1\) when the qubit is in \(\ket{0}\) and \(Z = -1\) when the qubit is in \(\ket{1}\), showing that in the computational basis the Pauli \(Z\) operator behaves like an Ising variable. In this sense, a Hamiltonian built from Pauli \(Z\) operators corresponds to the objective function originally defined in terms of Ising variables. This relationship also shows that the quantum state \(\ket{0}\) corresponds to the Ising value \(1\), and \(\ket{1}\) corresponds to the Ising value \(-1\).
Quantum Measurement¶
Quantum measurement extracts classical bit information from the state of qubits in a quantum computer. Here we discuss the most fundamental type: measurement in the computational basis. Since all measurements required in QAOA are computational basis measurements, we simply refer to this as “quantum measurement” unless stated otherwise.
A quantum measurement on the single-qubit state
is understood as an operation that yields the value “0” with probability \(|\alpha|^2\) and “1” with probability \(|\beta|^2\).
A crucial point is that performing a quantum measurement destroys the state \(\ket{\psi}\). Specifically, if the measurement yields “0”, the state collapses to \(\ket{0}\); if it yields “1”, the state collapses to \(\ket{1}\). Since some quantum hardware may not preserve the post-measurement state due to physical constraints, this document treats the state as destroyed and unusable after measurement.
Evaluating Expectation Values of Hermitian Operators¶
The expectation value of a physical quantity represented by a Hermitian operator \(H\) in state \(\ket{\psi}\) is:
Here \(\bra{\psi}\) is defined as the adjoint (conjugate transpose) of the quantum state (complex column vector) \(\ket{\psi}\). For example, in the single-qubit case, if \(\ket{\psi} = (a,b)^T\) then \(\bra{\psi} = (a^*, b^*)\). The same definition applies to \(n\) qubits.
In QAOA, evaluating the expectation value of the Pauli \(Z\) operator is required. Here we explain how to evaluate this expectation value using quantum measurement.
Given the quantum state
the expectation value of the Pauli \(Z\) operator in state \(\ket{\psi}\) can be computed using the computational basis matrix representation:
When the state \(\ket{\psi}\) is unknown (i.e., the values of \(\alpha\) and \(\beta\) are unknown), the expectation value cannot be computed directly. However, by preparing sufficiently many copies of the unknown quantum state \(\ket{\psi}\) and performing repeated measurements, the expectation value can be estimated approximately.
Consider preparing \(N\) copies of the quantum state \(\ket{\psi}\) and measuring each one. Suppose this yields “0” a total of \(N_{\alpha}\) times and “1” a total of \(N_{\beta}\) times (where \(N = N_{\alpha} + N_{\beta}\)). For sufficiently large \(N\):
Using this approximation, the expectation value of the Pauli \(Z\) operator can be estimated as:
Although we considered the single-qubit case here, the same approach applies to evaluating Pauli \(Z\) operator expectation values for general \(n\)-qubit systems.
Important
As mentioned in the section on quantum measurement, performing a quantum measurement destroys the state \(\ket{\psi}\). Therefore, to perform \(N\) measurements of \(\ket{\psi}\), \(N\) copies of \(\ket{\psi}\) must be prepared. This value is called the number of shots or number of samples.
Increasing the number of shots is expected to improve computational accuracy, but at the cost of increased computation time. Therefore, choosing an appropriate number of shots is essential in QAOA.
QAOA Procedure¶
QAOA solves optimization problems through the following steps:
Construct a Hamiltonian \(H\) corresponding to the objective function from the given Ising function \(\tilde f\). The minimum eigenvalue of \(H\) corresponds to the minimum value of \(\tilde f\).
To search for the minimum eigenvalue (and corresponding eigenstate) of \(H\), construct a parametric quantum circuit (ansatz circuit) characterized by real parameters \(\boldsymbol{\theta} = (\theta_1,\theta_2,\ldots,\theta_k)\). The quantum state corresponding to parameters \(\boldsymbol{\theta}\) is written as \(\ket{\psi(\boldsymbol{\theta})}\) and called the ansatz state.
Define the cost function as \(C(\boldsymbol{\theta}) = \bra{\psi(\boldsymbol{\theta})} H \ket{\psi(\boldsymbol{\theta})}\).
Alternate between evaluating \(C(\boldsymbol{\theta})\) on the quantum computer and updating parameters \(\boldsymbol{\theta}\) using a classical optimization algorithm until a convergence criterion is met.
Each step is explained in detail below.
1. Hamiltonian Construction¶
Assume the Ising function serving as the QAOA objective function is given as:
The goal is to find the Ising variable sequence \(z = (z_1,\ldots,z_n) \in \{-1,1\}^n\) that minimizes \(\tilde f(z)\).
To perform optimization on a quantum computer, this Ising function is transformed into a Hermitian operator (Hamiltonian) acting on qubits. Specifically, the Hamiltonian \(H = \sum_{\alpha} H_{\alpha}\) corresponding to the objective function is defined by replacing each Ising variable \(z_i\) appearing in each monomial \(\tilde f_\alpha(z)\) with the corresponding Pauli \(Z\) operator \(Z_i\).
Here are concrete examples:
When \(\tilde f_{\alpha}(z) = 2z_1z_2\):
When \(\tilde f_{\alpha}(z) = -3 z_3\):
A constant term like \(\tilde f_{\alpha}(z) = 5\) corresponds to a coefficient of the identity operator \(I\):
Such constant terms only shift the entire spectrum by a fixed amount without changing the ground state, so they can often be ignored (though they are retained when absolute energy values are needed).
Here \(Z_i\) denotes “the Pauli \(Z\) operator acting on the \(i\)-th qubit.” In this document, tensor products \(\otimes\) are omitted, writing \(Z_1 \otimes Z_2\) as \(Z_1 Z_2\).
From the above, optimizing an Ising function \(\tilde f\) with \(n\) variables via QAOA requires a Hamiltonian \(H\) defined on \(n\) qubits. Consequently, a quantum computer with at least \(n\) qubits is needed.
2. Ansatz State Preparation¶
To solve the given problem, a parameterized quantum state (ansatz state) is defined. The ansatz state is the state obtained by applying a parameterized quantum circuit to an initial state. QAOA uses a specifically structured QAOA ansatz. The circuit that creates the QAOA ansatz is:
Initial State¶
In QAOA, the initial state is typically the \(+\) state. The single-qubit \(+\) state is defined as:
Hint
The \(+\) state is obtained by applying the Hadamard gate
to the \(0\) state \(\ket{0}\).
The QAOA initial state is \(\ket{+}^{\otimes n}\), where all \(n\) qubits are in the \(+\) state.
Definition of the QAOA Ansatz¶
The QAOA ansatz is a quantum state characterized by a sequence of real parameters:
Here \(p\) is the “depth” (number of layers) of QAOA. In this document, the entire set of parameters is denoted collectively as \(\boldsymbol{\theta}\). The quantum circuit \(U(\boldsymbol{\theta})\) generating the QAOA ansatz is defined as:
Here \(H\) is the cost Hamiltonian defined above, and \(X_k\) is the Pauli \(X\) operator acting on the \(k\)-th qubit. The product \(\prod_{j=1}^{p}\) is interpreted as applying sequentially from the rightmost layer \(j=1\) to the leftmost layer \(j=p\). In this document, \(\gamma_j\) is the parameter associated with the cost Hamiltonian \(H\), and \(\beta_j\) is the parameter associated with \(X\)-mixing. Intuitively:
\(\exp(-i \gamma_j H)\) evolves the state along the Pauli \(Z\) direction (cost function), and
\(\exp\left(-i \beta_j \sum_k X_k\right)\) mixes the state along the Pauli \(X\) direction,
enabling the representation of diverse quantum states.
Thus, the QAOA ansatz state corresponding to parameters \(\boldsymbol{\theta}\) is defined as:
3. Cost Function Definition¶
The cost function \(C(\boldsymbol{\theta})\) is defined as the expectation value of the Hamiltonian \(H\) in the ansatz state \(\ket{\psi(\boldsymbol{\theta})}\):
As mentioned earlier, in the computational basis representation, a quantum state \(\ket{\psi}\) is a complex column vector and \(\bra{\psi}\) is its adjoint.
If the minimum eigenvalue of the Hamiltonian \(H\) is \(\lambda_{\min}\) with eigenvector \(\ket{\psi_{\min}}\), then \(C(\boldsymbol{\theta})\) attains its minimum value \(\lambda_{\min}\) when \(\ket{\psi(\boldsymbol{\theta})}\) coincides with \(\ket{\psi_{\min}}\).
QAOA operates under the premise that the \(\ket{\psi(\boldsymbol{\theta})}\) minimizing \(C(\boldsymbol{\theta})\) should be a good approximation to the ground state of \(H\), and uses classical optimization to search for the parameters \(\boldsymbol{\theta}\) that minimize \(C(\boldsymbol{\theta})\).
4. Classical Optimization Parameter Update Cycle¶
This is the core step of QAOA. Here, the following are repeated:
Evaluating the cost function \(C(\boldsymbol{\theta})\) on the quantum computer
Updating the parameters \(\boldsymbol{\theta}\) on the classical computer
to find \(\boldsymbol{\theta}^{\textup{opt}}\) that minimizes \(C(\boldsymbol{\theta})\).
Evaluating the Cost Function \(C(\boldsymbol{\theta})\)¶
Evaluating the cost function \(C(\boldsymbol{\theta})\) is the quantum computer’s task.
From its construction method, the Hamiltonian \(H\) built from the objective function can be written as:
Here, \(c_{\alpha}\) is the coefficient of monomial \(\tilde{f}_{\alpha}(z)\), and \(Z_{\alpha}\) is the Pauli \(Z\) operator corresponding to its variable part. Using this expression, the cost function \(C(\boldsymbol{\theta})\) becomes:
Each \(\bra{\psi(\boldsymbol{\theta})} Z_{\alpha} \ket{\psi(\boldsymbol{\theta})}\) can be evaluated using the measurement results of \(\ket{\psi(\boldsymbol{\theta})}\), as explained in the section on expectation value evaluation. Substituting each value into the equation above yields the cost function value \(C(\boldsymbol{\theta})\).
Updating Parameters \(\boldsymbol{\theta}\)¶
Based on the cost function value evaluated by the quantum computer, the classical computer updates the parameters \(\boldsymbol{\theta}\) to find the optimal values.
The parameter update cycle can be summarized as:
Execute the QAOA circuit \(U(\boldsymbol{\theta})\) with given parameters \(\boldsymbol{\theta}\),
Estimate the expectation value \(C(\boldsymbol{\theta})\) of Hamiltonian \(H\) for state \(\ket{\psi(\boldsymbol{\theta})}\) through measurement,
Use a classical optimization algorithm (gradient methods, gradient-free optimization, Bayesian optimization, etc.) to determine the next \(\boldsymbol{\theta}\),
repeating these steps until a convergence criterion is satisfied.
QAOA Summary¶
Finally, let us summarize the typical steps of QAOA.
flowchart TD
S1["Step 1: Define Hamiltonian"]
S2["Step 2: Construct ansatz circuit"]
S3["Step 3: Define cost function"]
S4["Step 4: Optimize parameters"]
S5["Step 5: Extract solution"]
S1 --> S2 --> S3 --> S4
S4 -->|"Not converged"| S4
S4 -->|"Converged"| S5
- Step 1: Define Hamiltonian
Write the classical cost function to optimize as \(f(z) = \sum_{\alpha} c_{\alpha} f_{\alpha}(z)\), where \(z = (z_1,\ldots,z_n)\) is a sequence of Ising variables with \(z_i \in \{-1,1\}\), \(c_{\alpha}\) are real coefficients, and \(f_{\alpha}\) are monomials. Replace each Ising variable \(z_i\) in each monomial \(f_{\alpha}(z)\) with the corresponding Pauli \(Z\) operator \(Z_i\), using the identity operator \(I\) as needed, to construct the Hamiltonian \(H = \sum_{\alpha} H_{\alpha}\) on the qubit space. The goal of QAOA is to approximately find the minimum eigenvalue/eigenvector of \(H\), thereby obtaining the Ising variable sequence \(z\) that minimizes \(f(z)\).
- Step 2: Prepare Ansatz State
To search for the minimum eigenvalue of Hamiltonian \(H\) constructed above, build the QAOA ansatz circuit \(U(\boldsymbol{\theta})\) characterized by real parameter sequence \(\boldsymbol{\theta} = (\boldsymbol{\gamma},\boldsymbol{\beta})\). Define \(\ket{\psi(\boldsymbol{\theta})} = U(\boldsymbol{\theta}) \ket{+}^{\otimes n}\) with initial state \(\ket{+}^{\otimes n}\), and call \(\ket{\psi(\boldsymbol{\theta})}\) the ansatz state.
- Step 3: Define Cost Function
Define the cost function as \(C(\boldsymbol{\theta}) = \bra{\psi(\boldsymbol{\theta})} H \ket{\psi(\boldsymbol{\theta})}\). \(C(\boldsymbol{\theta})\) is the expectation value of Hamiltonian \(H\) in the ansatz state \(\ket{\psi(\boldsymbol{\theta})}\) corresponding to parameters \(\boldsymbol{\theta}\).
- Step 4: Update Parameters
Evaluate \(C(\boldsymbol{\theta})\) on the quantum computer and update parameters \(\boldsymbol{\theta}\) using a classical optimization algorithm based on the result. Repeat this “evaluation (quantum side)” and “update (classical side)” cycle until the prescribed convergence criterion is met.
- Step 5: Extract Solution
Denote the parameters at convergence as \(\boldsymbol{\theta}^{\textup{opt}}\). At this point, \(C(\boldsymbol{\theta}^{\textup{opt}})\) and \(\ket{\psi(\boldsymbol{\theta}^{\textup{opt}})}\) are expected to be good approximations to the minimum eigenvalue/eigenvector of Hamiltonian \(H\). From the measurement results on the state \(\ket{\psi(\boldsymbol{\theta}^{\textup{opt}})}\), compute the objective function \(\tilde{f}(z)\) for each obtained Ising variable sequence \(z\), and select the one minimizing \(\tilde{f}(z)\) as the candidate solution. The most frequently observed Ising variable sequence \(z^{\textup{opt}}\) is expected to yield the minimum (or near-minimum) value of \(\tilde{f}(z)\).