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. This enables 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\)). Then 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)\). Then 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. It approximately solves the given optimization problem and obtains 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, we compute the expectation value of each term. This identifies the term in the objective function with the “most certain value”.
Consider the example
In this case, we first convert the objective function to a Hamiltonian. Then we compute the expectation values of the Pauli \(Z\) operators corresponding to each term’s variable part: \(\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 it is 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 largest absolute expectation value of \(Z_{\mathrm{max}}\) 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\). This progressively reduces 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, \({\rm term}_{\mathrm{max}} = z_i\) for some non-negative integer \(i\). This means that the value of \(z_i\) is most likely \(\sigma\). We substitute \(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:
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 is 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 reconstructs 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 uses QAOA to progressively reduce the optimization problem size. It ultimately computes the optimal solution. QAOA within the algorithm is used not to compute the optimal solution itself but merely to determine which variable to eliminate. Therefore, 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 is studied under the name “Barren Plateau” [2].
RQAOA uses quantum computers only for shallow-circuit QAOA. It is therefore expected to avoid these issues while obtaining more accurate and efficient solutions to optimization problems.