Sign in
← Atlas
Attested & literatureAlgorithmsQAOA

QAOA-in-QAOA (QAOA²) for large-scale MaxCut

Solve large-scale Maximum Cut (MaxCut) problems on near-term quantum hardware by decomposing the graph into many subgraph problems that can be solved in parallel, and determine how such a decomposition compares to a purely classical alternative for the same task.

QAOAOptimization
QAOAmaxcutdivide-and-conquergoemans-williamsonlarge-scale simulation

Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.

Solve large-scale Maximum Cut (MaxCut) problems on near-term quantum hardware by decomposing the graph into many subgraph problems that can be solved in parallel, and determine how such a decomposition compares to a purely classical alternative for the same task. Esposito and Danzig present an implementation of QAOA-in-QAOA (QAOA²), a divide-and-conquer heuristic that solves large-scale MaxCut problems by splitting the graph into many subgraph problems that can be solved in parallel, each still handled by QAOA. Their implementation is built on the Classiq platform and is executed on an HPE-Cray EX supercomputer, using the Message Passing Interface (MPI) and the SLURM workload manager to run the framework at scale. Alongside the quantum route, the authors investigate the limits of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA, to see whether QAOA² could benefit from solving certain sub-graphs classically instead. They report results from large-scale simulations of up to 33 qubits, which they say show the advantage of QAOA in certain cases, the efficiency of their implementation, and the adequacy of the workflow for preparing real quantum devices. For the graphs they considered, however, the authors report that the best choice of sub-graphs does not significantly improve results and is still outperformed by GW.

Circuit & simulation
What this takes and returns
TakesNothingWhat joins here

No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.

Nothing in the Atlas meets this end.

ReturnsNothingWhat joins here

No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.

Nothing in the Atlas meets this end.

This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →

How it works

Esposito and Danzig present an implementation of QAOA-in-QAOA (QAOA²), a divide-and-conquer heuristic that solves large-scale MaxCut problems by splitting the graph into many subgraph problems that can be solved in parallel, each still handled by QAOA. Their implementation is built on the Classiq platform and is executed on an HPE-Cray EX supercomputer, using the Message Passing Interface (MPI) and the SLURM workload manager to run the framework at scale. Alongside the quantum route, the authors investigate the limits of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA, to see whether QAOA² could benefit from solving certain sub-graphs classically instead. They report results from large-scale simulations of up to 33 qubits, which they say show the advantage of QAOA in certain cases, the efficiency of their implementation, and the adequacy of the workflow for preparing real quantum devices. For the graphs they considered, however, the authors report that the best choice of sub-graphs does not significantly improve results and is still outperformed by GW. The Classiq library carries this subject under applications · optimization. The sources read state no complexity bound for this record (The abstract of arXiv:2406.17383, the only source read for this record, states no complexity expression, no big-O bound and no formal speedup. Its scale and outcome statements are both empirical, from simulation: "Results from large-scale simulations of up to 33 qubits are presented, showing the advantage of QAOA in certain cases and the efficiency of the implementation, as well as the adequacy of the workflow in the preparation of real quantum devices." Its comparison against the classical alternative is stated for the specific graphs studied, not as a general bound: "For the considered graphs, the best choice for the sub-graphs does not significantly improve results and is still outperformed by GW." GW is fixed earlier in the same abstract as "the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA". No qubit count is given for any single subgraph, no runtime is quoted for either the quantum or the classical route, and no scaling law is stated in the number of qubits, subgraphs, or graph size. The Classiq index entry this record covers, applications/optimization/qaoa_in_qaoa, gives a directory path and a file list and states no bound. The field is left empty on purpose rather than filled with a bound written from memory.).

Implementation
Unsupported
qaoa-in-qaoa.txt
ALGORITHM: QAOA-in-QAOA (QAOA²) for large-scale MaxCut
PROBLEM: Solve large-scale Maximum Cut (MaxCut) problems on near-term quantum hardware by decomposing the graph into many subgraph problems that can be solved in parallel, and determine how such a decomposition compares to a purely classical alternative for the same task.
IDEA: Esposito and Danzig present an implementation of QAOA-in-QAOA (QAOA²), a divide-and-conquer heuristic that solves large-scale MaxCut problems by splitting the graph into many subgraph problems that can be solved in parallel, each still handled by QAOA. Their implementation is built on the Classiq platform and is executed on an HPE-Cray EX supercomputer, using the Message Passing Interface (MPI) and the SLURM workload manager to run the framework at scale. Alongside the quantum route, the authors investigate the limits of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA, to see whether QAOA² could benefit from solving certain sub-graphs classically instead. They report results from large-scale simulations of up to 33 qubits, which they say show the advantage of QAOA in certain cases, the efficiency of their implementation, and the adequacy of the workflow for preparing real quantum devices. For the graphs they considered, however, the authors report that the best choice of sub-graphs does not significantly improve results and is still outperformed by GW.
REPORTED COST: Not stated by the sources read
BASIS: The abstract of arXiv:2406.17383, the only source read for this record, states no complexity expression, no big-O bound and no formal speedup. Its scale and outcome statements are both empirical, from simulation: "Results from large-scale simulations of up to 33 qubits are presented, showing the advantage of QAOA in certain cases and the efficiency of the implementation, as well as the adequacy of the workflow in the preparation of real quantum devices." Its comparison against the classical alternative is stated for the specific graphs studied, not as a general bound: "For the considered graphs, the best choice for the sub-graphs does not significantly improve results and is still outperformed by GW." GW is fixed earlier in the same abstract as "the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA". No qubit count is given for any single subgraph, no runtime is quoted for either the quantum or the classical route, and no scaling law is stated in the number of qubits, subgraphs, or graph size. The Classiq index entry this record covers, applications/optimization/qaoa_in_qaoa, gives a directory path and a file list and states no bound. The field is left empty on purpose rather than filled with a bound written from memory.
DEMONSTRATED BY: the Classiq library entry applications/optimization/qaoa_in_qaoa
PRIMARY SOURCE: Aniello Esposito, Tamuz Danzig (2024), Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA — https://arxiv.org/abs/2406.17383

This is a literature reference record, not an executable circuit.

A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.

Quantum vs classical

Classical baseline

Compare QAOA with the strongest classical method for the same instance, input budget, and output metric.

Quantum claim

This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.

How to compare

Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.

Declared gaps

Nobody has reviewed this record for gaps yet.

Literature & references
Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA2024 · Aniello Esposito, Tamuz Danzig

Primary source: it presents an implementation of QAOA-in-QAOA (QAOA²) for large-scale MaxCut, reports large-scale simulations of up to 33 qubits, and finds that for the graphs it considers, the best choice of sub-graphs does not significantly improve results and is still outperformed by the classical Goemans-Williamson algorithm. Consult it for the decomposition procedure, the graphs and scales tested, and the numerical results the abstract summarizes but does not quote.

arxiv.org/abs/2406.17383 ↗

Related entries

AlgorithmsQAOA MaxCut on a 5-node ringOperatorsMaxCut cost operatorAlgorithmsIsing formulations of NP-complete and NP-hard problemsAlgorithmsQuantum simulated annealing