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.
QAOAadaptive ansatzcombinatorial optimizationmax-cutshortcuts to adiabaticity
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
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.
Circuit & simulation
problem
encodetransform
algorithm
transformmeasure
readout
measure
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 →
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.
How it works
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 Classiq library carries this subject under applications · optimization. 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 Classiq index entry this record covers, applications/optimization/adapt_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
adapt-qaoa.txt
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 Classiq index entry this record covers, applications/optimization/adapt_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/adapt_qaoa
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.
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
An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer2020 · Linghua Zhu, Ho Lun Tang, George S. Barron, F. A. Calderon-Vargas, Nicholas J. Mayhall, Edwin Barnes, Sophia E. Economou
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.