Algorithms · QAOA
ADAPT-QAOA: an iterative, problem-tailored QAOA
Find a better parameterized ansatz for the quantum approximate optimization algorithm (QAOA) applied to combinatorial optimization problems such as Max-Cut, where the standard, fixed-form QAOA ansatz is not known to be optimal and no systematic method exists for improving on it.
Attested & literatureUpdated
Open on the mapView frozen graph
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 implementationadapt_qaoa
- Reported costNot stated by the sources read
- Papers1
Find a better parameterized ansatz for the quantum approximate optimization algorithm (QAOA) applied to combinatorial optimization problems such as Max-Cut, where the standard, fixed-form QAOA ansatz is not known to be optimal and no systematic method exists for improving on it. Zhu, Tang, Barron, Calderon-Vargas, Mayhall, Barnes and Economou address the fixed, potentially suboptimal form of the standard QAOA ansatz by developing an iterative version of QAOA that is problem-tailored and that can also be adapted to specific hardware constraints. Rather than fixing the ansatz's structure in advance, their algorithm builds it up step by step for the specific problem instance being solved. The authors simulate the algorithm on a class of Max-Cut graph problems and report that it converges much faster than the standard QAOA, while simultaneously reducing the required number of CNOT gates and optimization parameters. They connect this improvement to the concept of shortcuts to adiabaticity, and state that they provide evidence for that connection rather than a proof of it. The abstract frames the underlying motivation as addressing a documented gap: evidence that the standard ansatz is not optimal, without a systematic approach existing for finding a better one.
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 →
Zhu, Tang, Barron, Calderon-Vargas, Mayhall, Barnes and Economou address the fixed, potentially suboptimal form of the standard QAOA ansatz by developing an iterative version of QAOA that is problem-tailored and that can also be adapted to specific hardware constraints. Rather than fixing the ansatz's structure in advance, their algorithm builds it up step by step for the specific problem instance being solved. The authors simulate the algorithm on a class of Max-Cut graph problems and report that it converges much faster than the standard QAOA, while simultaneously reducing the required number of CNOT gates and optimization parameters. They connect this improvement to the concept of shortcuts to adiabaticity, and state that they provide evidence for that connection rather than a proof of it. The abstract frames the underlying motivation as addressing a documented gap: evidence that the standard ansatz is not optimal, without a systematic approach existing for finding a better one. The sources read state no complexity bound for this record (The abstract of arXiv:2005.10258, the only source read for this record, states no complexity expression, no qubit count and no formal speedup bound. Its performance claim is comparative and empirical: "We simulate the algorithm on a class of Max-Cut graph problems and show that it converges much faster than the standard QAOA, while simultaneously reducing the required number of CNOT gates and optimization parameters." The word "speedup" used elsewhere in the abstract names this same convergence comparison, not a proven separation from any classical or standard-QAOA running-time bound: "We provide evidence that this speedup is connected to the concept of shortcuts to adiabaticity." No number of gates, parameters, graphs or qubits is quoted anywhere in the abstract, and the comparison throughout is to "the standard QAOA" on the graph class simulated, not to a stated general bound. 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
- adapt_qaoa
- Reported cost
- Not stated by the sources read
- Complexity basis
- The abstract of arXiv:2005.10258, the only source read for this record, states no complexity expression, no qubit count and no formal speedup bound. Its performance claim is comparative and empirical: "We simulate the algorithm on a class of Max-Cut graph problems and show that it converges much faster than the standard QAOA, while simultaneously reducing the required number of CNOT gates and optimization parameters." The word "speedup" used elsewhere in the abstract names this same convergence comparison, not a proven separation from any classical or standard-QAOA running-time bound: "We provide evidence that this speedup is connected to the concept of shortcuts to adiabaticity." No number of gates, parameters, graphs or qubits is quoted anywhere in the abstract, and the comparison throughout is to "the standard QAOA" on the graph class simulated, not to a stated general bound. 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: ADAPT-QAOA: an iterative, problem-tailored QAOA
PROBLEM: Find a better parameterized ansatz for the quantum approximate optimization algorithm (QAOA) applied to combinatorial optimization problems such as Max-Cut, where the standard, fixed-form QAOA ansatz is not known to be optimal and no systematic method exists for improving on it.
IDEA: Zhu, Tang, Barron, Calderon-Vargas, Mayhall, Barnes and Economou address the fixed, potentially suboptimal form of the standard QAOA ansatz by developing an iterative version of QAOA that is problem-tailored and that can also be adapted to specific hardware constraints. Rather than fixing the ansatz's structure in advance, their algorithm builds it up step by step for the specific problem instance being solved. The authors simulate the algorithm on a class of Max-Cut graph problems and report that it converges much faster than the standard QAOA, while simultaneously reducing the required number of CNOT gates and optimization parameters. They connect this improvement to the concept of shortcuts to adiabaticity, and state that they provide evidence for that connection rather than a proof of it. The abstract frames the underlying motivation as addressing a documented gap: evidence that the standard ansatz is not optimal, without a systematic approach existing for finding a better one.
REPORTED COST: Not stated by the sources read
BASIS: The abstract of arXiv:2005.10258, the only source read for this record, states no complexity expression, no qubit count and no formal speedup bound. Its performance claim is comparative and empirical: "We simulate the algorithm on a class of Max-Cut graph problems and show that it converges much faster than the standard QAOA, while simultaneously reducing the required number of CNOT gates and optimization parameters." The word "speedup" used elsewhere in the abstract names this same convergence comparison, not a proven separation from any classical or standard-QAOA running-time bound: "We provide evidence that this speedup is connected to the concept of shortcuts to adiabaticity." No number of gates, parameters, graphs or qubits is quoted anywhere in the abstract, and the comparison throughout is to "the standard QAOA" on the graph class simulated, not to a stated general bound. 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: Linghua Zhu, Ho Lun Tang, George S. Barron, F. A. Calderon-Vargas, Nicholas J. Mayhall, Edwin Barnes, Sophia E. Economou (2020), An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer — https://arxiv.org/abs/2005.10258
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.
Where this sits
This record is named by the layer graph at:
- Choose a parameterised trial state Slot
Takes The Hamiltonian whose ground state is wanted, together with whatever structure is to be respected — particle number, spin, point-group symmetry, a reference determinant — and the connectivity and native gate set of the device the family has to run on. Returns A circuit family with a fixed structure and free real parameters, together with the number of those parameters — which is the size of the classical search problem handed to the next layer.
Related entries
- ADAPT-VQE
Algorithms
- Qubit-ADAPT-VQE
Algorithms
- QAOA MaxCut on a 5-node ring
Algorithms
- MaxCut cost operator
Operators
References
- An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer
Linghua Zhu, Ho Lun Tang, George S. Barron, F. A. Calderon-Vargas, Nicholas J. Mayhall, Edwin Barnes, Sophia E. Economou · 2020
Primary source: it develops the iterative, problem-tailored QAOA ansatz, reports from simulation on a class of Max-Cut graph problems that it converges much faster than the standard QAOA while reducing the required CNOT gate and parameter counts, and connects the improvement to shortcuts to adiabaticity. Consult it for the ansatz-growing procedure itself, the graph instances and sizes simulated, and the numerical results the abstract does not quote.