Recursive QAOA Algorithm¶
Recursive QAOA[1] (hereafter RQAOA) is a method that repeatedly executes QAOA with shallow ansatz circuits, progressively reducing the problem size to identify the optimal solution. It aims to relax the circuit depth constraints that are problematic in standard QAOA, enabling its use on larger-scale problems. For a detailed explanation of standard QAOA theory, see QAOA Algorithm.
Note
RQAOA does not support constrained problems. If constraints are present, the Amplify SDK automatically converts the problem to an unconstrained one by introducing penalty terms. For details, see Constraints and penalty functions.
RQAOA Procedure¶
RQAOA is executed through the following procedure:
Step 1: Variable reduction cycle using shallow-circuit QAOA
Procedure 1: Run QAOA with a shallow circuit
Procedure 2: Determine which variable to eliminate based on the QAOA results
Procedure 3: Reduce a variable and construct a new problem
Step 2: Find the optimal solution for the sufficiently reduced problem
Step 3: Derive the optimal solution for the original problem from the reduced problem’s solution
RQAOA in Detail¶
Below, we examine the procedures performed at each step in more detail.
To illustrate each step, we use the following simple example: minimizing the Ising function
Step 1. Variable Reduction Cycle¶
This is the core step of RQAOA. The variable reduction cycle repeats the following procedures until the problem size (number of variables) is sufficiently small.
For the objective function \({f}(z)\) composed of Ising variables, run QAOA using a shallow ansatz state \(\ket{\psi(\boldsymbol{\theta})}\) (e.g., with depth \(p = 1\)), and measure its final state \(\ket{\psi}\) in the computational basis.
From the measurement results, compute the expectation value of each term in the objective function \({f}(z)\), and identify the term with the largest absolute expectation value. Based on the sign of that expectation value, define \(\sigma = 1\) or \(\sigma = -1\).
For the identified term, introduce the relation \({\rm term}_{\mathrm{max}}= \sigma\). Use this relation to eliminate a variable and define a new objective function \({f}_{\mathrm{new}}(z)\).
Each procedure is explained in more detail below.
1. Running QAOA with a Shallow Circuit¶
The first step in the RQAOA iteration uses QAOA with a shallow circuit to approximately solve the given optimization problem and obtain measurement results from the final state \(\ket{\psi}\).
The measurement results are only used to determine which variable to eliminate in subsequent steps, so an exact optimal solution is not required. This is why the use of shallow ansatz circuits is acceptable.
2. Determining Which Variable to Eliminate¶
From the measurement results obtained in Procedure 1, the term in the objective function with the “most certain value” is identified by computing the expectation value of each term.
Consider the example
In this case, after converting the objective function to a Hamiltonian, the expectation values of the Pauli \(Z\) operators corresponding to each term’s variable part are computed: \(\braket{\psi|Z_0Z_1|\psi}\), \(\braket{\psi|Z_1Z_2|\psi}\), \(\braket{\psi| Z_0 |\psi}\), \(\braket{\psi| Z_2 |\psi}\). For details on the conversion, see QAOA Algorithm.
Let \(Z_{\mathrm{max}}\) denote the Pauli operator with the largest absolute expectation value. The corresponding term is denoted \({\rm term}_{\mathrm{max}}\), and its value is fixed as \({\rm term}_{\mathrm{max}} = \sigma \in \{-1,1\}\): if \(\langle \psi|Z_{\mathrm{max}}|\psi\rangle\) is positive, \(\sigma = 1\); if negative, \(\sigma = -1\). By definition, \(-1 \leq \langle \psi|Z_{\mathrm{max}}|\psi\rangle \leq 1\).
For the polynomial
suppose the expectation value computation yields:
In this case, \(Z_{\mathrm{max}} = Z_1Z_2\), and \({\rm term}_{\mathrm{max}} = z_1z_2\). Since \(\braket{\psi|Z_1Z_2|\psi} = -0.6 < 0\), we set \(\sigma = -1\), giving the relation \({\rm term}_{\mathrm{max}} = \sigma\), i.e., \(z_1z_2 = -1\).
The meaning of this operation is as follows: the fact that \(Z_{\mathrm{max}}\) has the largest absolute expectation value means that the corresponding variable term \({\rm term}_{\mathrm{max}}\) was closest to taking a definite value of \(+1\) or \(-1\). In other words, if we must fix the value of exactly one term in the objective function, \({\rm term}_{\mathrm{max}}\) is the most plausible choice. Based on the sign of the expectation value of \(Z_{\mathrm{max}}\), the term’s value is fixed to \({\rm term}_{\mathrm{max}} = 1\) or \({\rm term}_{\mathrm{max}} = -1\), progressively reducing the problem size.
3. Variable Reduction¶
Variable reduction is performed using the relation \({\rm term}_{\mathrm{max}} = \sigma\) introduced in Procedure 2.
When \({\rm term}_{\mathrm{max}}\) is Linear¶
In this case, for some non-negative integer \(i\), \({\rm term}_{\mathrm{max}} = z_i\), meaning “the value of \(z_i\) is most likely \(\sigma\).” The variable is substituted as \(z_i = \sigma\) in the original Hamiltonian \(H\) to obtain a new objective function \({f}_{\mathrm{new}}\).
When \({\rm term}_{\mathrm{max}}\) is Quadratic or Higher¶
Consider the example again:
Suppose, as established in Procedure 2, \(z_1z_2 = -1\). This implies the relation \(z_1 = -z_2\) between \(z_1\) and \(z_2\). Substituting \(z_1 = -z_2\) into the original objective function \({f}(z)\) yields:
Note that for Ising variables \(z \in \{-1,1\}\), \(z^2 = 1\). As a result, a new objective function with one fewer variable is obtained.
This example deals with a quadratic problem, but the same procedure applies when targeting higher-order terms for variable reduction. For the general case, see Appendix C of the reference.
After Procedures 1-3, if the new objective function \({f}_{\mathrm{new}}(z)\) has sufficiently few variables, the cycle exits. Otherwise, the reduction process returns to Procedure 1 using \({f}_{\mathrm{new}}(z)\).
Step 2. Solving the Reduced Problem¶
Once the problem size has been sufficiently reduced through repeated variable reduction cycles, the optimal solution is found by brute force.
Let us continue the example.
As shown in Step 1, starting from
the relation \(z_1z_2 = -1\) led to the new objective function:
Brute-force evaluation yields the values minimizing \({f}_{\mathrm{new}}(z)\):
Step 3. Deriving the Original Problem’s Optimal Solution¶
In the final step of RQAOA, the solution to the reduced problem from Step 2 is used to reconstruct the optimal solution for the original optimization problem \({f}(z)\). This is done by tracing back the variable reduction relations \({\rm term}_{\mathrm{max}} = \sigma\) obtained in Step 1, Procedure 3.
In Step 2, the optimal solution \((z_0, z_2) = (-1,-1)\) for the reduced problem \({f}_{\mathrm{new}}(z) = -4z_0z_2 + 2z_0 + z_2 -3\) was obtained. In this step, the value of \(z_1\) is derived using the relation:
established during variable reduction. In this case:
Thus, the optimal solution for the original optimization problem \({f}(z) = 4z_0z_1 +3z_1z_2 + 2z_0 + z_2\) is:
Summary¶
As described above, RQAOA is a method that repeatedly leverages QAOA to progressively reduce the optimization problem size, ultimately computing the optimal solution. Since QAOA within the algorithm is used not to compute the optimal solution itself but merely to determine which variable to eliminate, shallower circuits can be expected to suffice compared to computing the optimal solution directly.
In standard QAOA, solving large-scale problems requires deep circuits, which increases computation time. In addition, circuit size and hardware noise are known to hinder effective parameter updates in QAOA (the latter phenomenon has been studied under the name “Barren Plateau” [2]).
RQAOA uses quantum computers only for shallow-circuit QAOA, and is therefore expected to avoid these issues while obtaining more accurate and efficient solutions to optimization problems.