Algorithms · QAOA
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.
Attested & literatureUpdated
A small worked example, computed in your browser. It is not a result from this record's papers.
QAOA, p=1, MaxCut on a 4-cycle
4 qubits on a 4-cycle (edges 0-1, 1-2, 2-3, 3-0), one QAOA layer with gamma=pi/8, beta=3*pi/8.
Step 1 of 2 · Hadamard layer(4)
Probability of each outcome after this step
- 00006%
- 00016%
- 00106%
- 00116%
- 01006%
- 01016%
- 01106%
- 01116%
- 8 more outcomes50%
Starts from the uniform superposition over all 16 possible cuts.
Probability spreads from 1 outcome to 16. All 16 are equally likely.
The cost layer (RZZ(2*gamma) on each of the 4 edges) rewards cuts that separate connected qubits, then the mixer (RX(2*beta) on every qubit) lets amplitude move between cuts.
Probability moves between the same 16 outcomes. Up: 0101 6.3% → 26.6%, 1010 6.3% → 26.6%. Down: 0001 6.3% → 1.6%. This is the step that entangles the qubits: from here on no single qubit has a state of its own, only the register as a whole does.
Readout 0101 and 1010 are the two optimal cuts of a 4-cycle (alternating around the ring); at these angles measuring the register returns one of them clearly more often than any other cut.
Open in Studio- Record typeLiterature reference
- Reference implementationqaoa_in_qaoa
- Reported costNot stated by the sources read
- Papers1
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.
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 →
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 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 demonstration this record covers states no complexity bound of its own. The field is left empty on purpose rather than filled with a bound written from memory.).
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 →
- Record type
- Literature reference
- Reference implementation
- qaoa_in_qaoa
- Reported cost
- Not stated by the sources read
- Complexity 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 demonstration this record covers states no complexity bound of its own. The field is left empty on purpose rather than filled with a bound written from memory.
- Circuit
- Not supplied
This record is not a concrete 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.
Nobody has reviewed this record for gaps yet.
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 demonstration this record covers states no complexity bound of its own. The field is left empty on purpose rather than filled with a bound written from memory.
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.
Related entries
- QAOA MaxCut on a 5-node ring
Algorithms
- MaxCut cost operator
Operators
- Ising formulations of NP-complete and NP-hard problems
Algorithms
- Quantum simulated annealing
Algorithms
References
- Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA
Aniello Esposito, Tamuz Danzig · 2024
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.