The real problem
Make many linked choices without trying every possible combination one by one.
Recursive QAOA for MaxCut and Ising optimization
RQAOA is a way to attack hard yes-or-no optimization problems. It first uses QAOA to learn which decisions are strongly linked, then repeatedly shrinks the graph until the remaining small problem can be solved by brute force.
What it can model
Problems where many small choices affect each other
Imagine you must make many yes-or-no choices: put a task on server A or B, assign a person to one team or another, or split a network into two groups. Each choice is simple by itself, but pairs of choices can create a reward, a conflict, or a cost. RQAOA is useful when those pair relationships can be drawn as a graph and optimized together.
The graph model
Dots are decisions, lines are pair effects, and line weights show how strong the effect is.
What RQAOA does
It looks for strongly related pairs, fixes their relation, and makes the problem smaller.
The benefit
Instead of brute forcing the full graph, brute force is used only after the graph is small.
Concrete example
Split 12 connected tasks between two machines
Suppose a small workflow has 12 tasks and each task must run on machine A or machine B. Some task pairs interfere if they run together, while other pairs communicate often and should be treated consistently. The goal is to choose the A/B assignment that gives the best overall pairwise score. Brute forcing all 12 tasks means checking 2^12 assignments; after RQAOA folds the graph down to 8 active tasks, the final direct search checks 2^8 assignments instead.
- Node
- one task, or one binary decision
- Edge
- how strongly two tasks affect each other
- Final colors
- the two groups, machine A and machine B
- Dimmed nodes
- tasks folded away by RQAOA, later reconstructed
Methodology
Use QAOA first, then brute force the small remainder
The core idea is simple: QAOA estimates useful pair relations on the current graph. RQAOA then removes one variable using the strongest relation and repeats. When the graph reaches the cutoff size n_c, the remaining problem is small enough to solve directly by brute force.
Build the graph problem
Represent binary decisions as graph nodes and pair effects as weighted edges.
Run QAOA
Estimate which variables tend to agree or disagree in good candidate solutions.
Shrink the graph
Choose the strongest pair relation and fold one variable into the other.
Brute force the rest
After the graph reaches n_c variables, solve the small remaining problem directly.
Algorithm sketch
RQAOA core loop
The highlighted line follows the interactive demo below. Each pass through the loop uses QAOA for guidance, removes one variable, and stores the relation needed to rebuild the full assignment at the end.
function RQAOA(graph G, depth p, cutoff n_c)
problem <- graph_to_maxcut_qubo(G)
stack <- empty elimination log
while number_of_variables(problem) > n_c:
H_C <- convert QUBO objective to Ising Hamiltonian
state <- run depth-p QAOA and optimize beta, gamma
(i, j) <- pair with largest abs(<Z_i Z_j>)
relation <- sign(<Z_i Z_j>)
problem <- fold variable i into variable j
push (i, j, relation) into stack
reduced_solution <- brute force the remaining n_c variables
return lift_solution(reduced_solution, stack)Interactive demo
Watch RQAOA on three increasingly messy graphs
The same 12-task example runs on three problem instances - a structured cycle, a 3-regular random graph, and an irregular weighted graph. Each one tightens the difficulty: weights become less uniform, correlations get weaker, and the final cut is harder to recover. Switch between them with the buttons below to see where RQAOA stays clean and where it starts to strain.
Final cut for this instance
Cut edge - paired tasks ended on different machines
Same-group edge - same machine
Negative coupling - preferred apart, didn't get split
Methodology & references
Theory and implementation sources
This demo is built on published academic and open-source work.
QAOA theoretical background. The discussion of QAOA mechanics, parameter landscapes, and known variants follows the survey of Blekos et al. (2023): “A Review on Quantum Approximate Optimization Algorithm and its Variants”, arXiv:2306.09198v2 (revised 26 Jun 2023). arxiv.org/abs/2306.09198
RQAOA implementation pattern. The recursive elimination scheme — measuring 〈ZiZj〉 correlations, freezing the most-confident edge, contracting the graph, and recursing — mirrors the public API and algorithmic structure of the RecursiveMinimumEigenOptimizer in Qiskit Optimization 0.7.0 (Sphinx-generated API reference, 2025). qiskit-community.github.io / RecursiveMinimumEigenOptimizer