Recursive QAOA

Recursive QAOA is a quantum-classical hybrid algorithm that repeatedly executes QAOA as a subroutine, progressively reducing the problem size to identify the optimal solution. At each step, variables to eliminate are determined from the measurement results of a shallow-circuit QAOA, and once the problem is small enough, an exact solution is found by brute force. This approach relaxes the circuit depth constraints that are challenging in standard QAOA, aiming for applicability to larger-scale problems.

It can solve optimization problems with objective functions expressed as \(N\)-th degree polynomials in Ising variables.

To use RQAOA, specify RQAOA as the algorithm when constructing a quantum computer client. This page covers how to configure RQAOA parameters and retrieve detailed results, and make practical use of them.

For algorithm details, see RQAOA Algorithm.

The following example runs RQAOA using QulacsClient and retrieves the execution results:

from amplify import RQAOA, QulacsClient, VariableGenerator, Model, solve

# Generate an array of decision variables
gen = VariableGenerator()
q = gen.array("Binary", 5)

# Create objective function
objective = q[0] * q[1] - q[2]

# Define the model
model = Model(objective)

client = QulacsClient(RQAOA)
result = solve(model, client)

Note

RQAOA does not support constrained problems. If constraints are present, the SDK automatically converts the problem to an unconstrained one by introducing penalty terms.

Evaluating Execution Results

For quantum computer solvers, the amplify.Result.response_time and amplify.Result.execution_time attributes of the amplify.Result class returned by solve() correspond to the communication time and circuit execution time with the quantum computer (real device or simulator), rather than with the solver service itself.

In RQAOA, QAOA is called multiple times as a subroutine to perform optimization. Therefore, amplify.Result.response_time and amplify.Result.execution_time represent the cumulative totals across all QAOA invocations.

result = solve(model, client)

result.response_time      # Total communication time with QPU
result.execution_time     # Total execution time on QPU

In RQAOA, the optimal solution is uniquely determined by brute-force search on the reduced problem. The corresponding unique solution to the original (pre-reduction) problem is then recovered from this reduced solution. Therefore, amplify.Result contains only this single solution.

RQAOA-Specific Results

The amplify.Result.client_result attribute has an algorithm-specific type that contains detailed solution results, including information about the execution process. For RQAOA, the corresponding type is Result.

RQAOA Result Attributes

Attribute	Type	Description
durations	RQAOADurations	Breakdown of execution time
num_execution	int	Total number of cost function evaluations by QAOA at each step (number of classical optimization iterations)
optimized_objective	float	Best cost function value \(C(\boldsymbol{\theta}^{\textup{opt}})\) found
optimized_solution	tuple[int, ...]	Best solution
history	Sequence[RQAOAHistoryItem]`	History of each QAOA variable-reduction step

RQAOADurations (Execution Time Breakdown)

durations provides a breakdown of the time spent in each phase of RQAOA.

d = result.client_result.durations

result.total_time            # Total time for amplify.solve
d.total_time                 # Total elapsed time for RQAOA
d.total_response_time        # Total communication time with the backend
d.total_execution_time       # Total execution time on the backend
d.classical_processing_time  # Time spent on classical optimization (= total_time - total_response_time)

history (RQAOA Optimization History)

history is a list of each QAOA step (RQAOAHistoryItem) performed for variable reduction.

for step in result.client_result.history:
    print(step.timestamp)          # Elapsed time from RQAOA start to completion of this step
    print(step.model)              # Objective function at this step after variable reduction
    print(step.qaoa_result)        # QAOAResult
    print(step.elimination_info)   # Variable elimination information chosen from this step's results

Parameter Configuration

Parameter	Type	Default	Description
reps	int	10	Ansatz circuit depth (number of layers \(p\)). Higher values increase expressiveness but deepen the circuit
shots	int	1024	Number of measurements. Higher values improve statistical accuracy but increase execution time
qaoa_type	RQAOAType	ORIGINAL	QAOA type. Choose from ORIGINAL_QUADRATIC or ORIGINAL
minimize	MinimizeProtocol	ScipyMinimize()	Classical optimization method. Defaults to scipy’s COBYLA
min_size	int	2	Variable reduction continues until the number of variables reaches this value
max_degree	int|None	None	Limits the maximum degree of terms targeted for variable reduction. None means no limit
min_corr	float	0	Only terms whose absolute expectation value exceeds this threshold are targeted for variable reduction

Target Variable Count (min_size)

min_size specifies how far RQAOA should reduce the number of variables in the problem. For details, see RQAOA Algorithm. Depending on the values of max_degree and min_corr described below, variable reduction may not always be possible; in such cases, reduction is halted and the algorithm proceeds to brute-force search for the optimal solution.

• Each reduction step eliminates one variable. The number of QAOA executions equals the difference between the original variable count and min_size.

• Since brute force is used to identify the optimal solution, larger min_size values increase the time needed for exact solution identification.

• Default: 2

Example:

client.parameters.min_size = 2

Maximum Term Degree for Reduction (max_degree)

max_degree limits the degree of terms from which variables are selected for elimination in RQAOA. For details, see RQAOA Algorithm.

• For values of 3 or higher, be aware that variable reduction may increase the degree of the problem.

• If all terms in the objective function have degree lower than max_degree, reduction is halted and the algorithm proceeds to optimal solution search.

• Default: None

Example:

client.parameters.max_degree = 2

Minimum Expectation Value Threshold (min_corr)

min_corr sets the minimum expectation value that a term must exceed to be targeted for variable reduction in RQAOA. For details, see RQAOA Algorithm.

• If the expectation values of all terms in the objective function fall below min_corr, reduction is halted and the algorithm proceeds to optimal solution search.

• Default: 0

Example:

client.parameters.min_corr = 0