Source-linked AI summary
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
TL;DR
The paper addresses the lack of a systematic way to improve QAOA’s fixed ansatz for combinatorial optimization. It introduces ADAPT-QAOA, which iteratively selects problem-tailored mixers, and reports faster convergence with fewer CNOT gates and optimization parameters in Max-Cut simulations.
Problem
Standard QAOA’s fixed ansatz may be nonoptimal, while identifying better problem-tailored ansätze is highly nontrivial.
Method
ADAPT-QAOA iteratively grows an alternating ansatz by selecting mixers from a predefined operator pool using an energy-gradient criterion.
Results
ADAPT-QAOA converges faster than standard QAOA on simulated Max-Cut problems while using fewer CNOT gates and optimization parameters.
Takeaways & Limitations
The adaptive construction can tailor mixers to optimization problems and hardware constraints, and its speedup is connected to shortcuts to adiabaticity.
Abstract
from arXiv · showhide
The quantum approximate optimization algorithm (QAOA) is a hybrid variational quantum-classical algorithm that solves combinatorial optimization problems. While there is evidence suggesting that the fixed form of the standard QAOA ansatz is not optimal, there is no systematic approach for finding better ansätze. We address this problem by developing an iterative version of QAOA that is problem-tailored, and which can also be adapted to specific hardware constraints. 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. We provide evidence that this speedup is connected to the concept of shortcuts to adiabaticity.
I. INTRODUCTION
Standard QAOA applies a finite-order, variational version of adiabatic evolution to combinatorial optimization, but its fixed ansatz can be constrained by hardware and optimization difficulties. The paper proposes ADAPT-QAOA to systematically construct problem-tailored alternatives.
- Motivation: QAOA uses a finite-order adiabatic-evolution operator as a variational ansatz and minimizes the Ising-Hamiltonian expectation value on a quantum processor with classical optimization.The processor measures energy expectation values, while a classical computer optimizes the ansatz parameters.
- Limitations of standard QAOA: Increasing QAOA layers can improve performance, but coherence-time limits and additional variational parameters constrain deeper ansätze.The paper also identifies locality, symmetry, and the ad hoc form of short-depth QAOA as potential performance limitations.
- Motivation: Short-depth, problem-tailored ansätze could address standard QAOA limitations, but selecting among the vast space of alternatives is highly nontrivial.The challenge motivates a systematic ansatz-construction strategy.
- Proposed approach: ADAPT-QAOA iteratively grows the ansatz two operators at a time, using a gradient criterion to select mixers from a predefined operator pool.The approach is general but is evaluated in this work on Max-Cut problems.
- Reported outcome: For Max-Cut, entangling mixers produce dramatically faster convergence while reducing optimization parameters and CNOT gates by approximately 50% each versus standard QAOA.The paper connects this speedup to shortcuts to adiabaticity.
A. Framework
ADAPT-QAOA replaces QAOA’s fixed mixer with layer-dependent mixers selected iteratively from a problem-defined pool. Gradients determine which operator to add, after which all current parameters are reoptimized until convergence.
- Standard QAOA: Standard QAOA uses p alternating layers containing the cost Hamiltonian HC and a mixer, with variational parameters optimized to minimize energy.The resulting energy and state provide an approximate solution to the optimization problem encoded in HC.
- Adaptive construction: ADAPT-QAOA replaces the fixed mixer HM with a sequence of mixers Ak that can change from one layer to the next.This gives the ansatz additional flexibility while retaining QAOA’s alternating-operator structure.
- Iterative procedure: The algorithm defines a mixer pool and reference state, prepares the current ansatz, and measures energy gradients for pool operators.Gradients are evaluated through commutator decompositions into Pauli-string expectation values.
- Iterative procedure: If the gradient norm exceeds a threshold, ADAPT-QAOA adds the selected operator with a predefined parameter value and reoptimizes all parameters currently in the ansatz.The process repeats until the gradient norm falls below the stopping threshold.
- Interpretation: ADAPT-QAOA combines QAOA’s alternating structure with ADAPT-VQE-inspired flexibility in choosing mixers during ansatz construction.The distinction is adaptive mixer selection rather than a fixed mixer repeated across layers.
B. Operator Pool
The mixer pool determines the operators available to ADAPT-QAOA, ranging from the standard single operator to single-qubit and multi-qubit pools. For Max-Cut, operator selection is restricted by the Hamiltonian’s symmetry.
- Pool construction: The standard QAOA pool contains one operator, while the single-qubit pool includes Xi and Yi operators and the multi-qubit pool adds entangling Pauli strings.The pools satisfy PQAOA ⊂ Psingle ⊂ Pmulti.
- Pool construction: The QAOA, single-qubit, and multi-qubit pools contain O(1), O(n), and O(n^2) elements, respectively.Larger pools provide more operator choices but increase the pool size with system dimension.
- Max-Cut encoding: Max-Cut is an NP-hard quadratic unconstrained binary optimization problem whose weighted graph objective can be encoded in an Ising Hamiltonian.Its ground state corresponds to the maximum cut, making it a benchmark for QAOA.
- Symmetry restriction: For Max-Cut, the Hamiltonian’s Z2 symmetry is generated by F = ⊗iXi, and only pool operators commuting with F have nonzero gradients.The retained Pauli strings therefore have an even number of Y or Z operators.
C. Performance and Resource Comparison
ADAPT-QAOA with multi-qubit mixer pools converges rapidly on the tested Max-Cut graphs and reduces both optimization parameters and CNOT gates relative to standard QAOA.
- Benchmark: 20 random edge-weight instances on n=6 regular graphs benchmark ADAPT-QAOA at degrees D=3 and D=5.Edge weights are drawn from U(0, 1).
- Convergence: Multi-qubit mixer pools reach the exact solution after approximately 3 ansatz layers for both graph degrees.Single-qubit pools provide only a modest improvement over standard QAOA.
- Convergence: Degree-5 graphs slow standard QAOA and single-qubit ADAPT-QAOA, while multi-qubit ADAPT-QAOA remains approximately unchanged.The comparison uses energy error versus ansatz layers.
- Resource comparison: The operator pool can be tailored to hardware constraints, while retaining a systematic procedure for improving performance and reducing resources.The paper contrasts this with restricted entangling-gate approaches that add variational parameters.
- Ansatz structure: Multi-qubit ADAPT-QAOA selects nonstandard operators approximately 75% of the time for D=3 and 80% for D=5.The authors relate this trend to the greater entanglement needed for more connected graphs.
- Resource comparison: ADAPT-QAOA uses fewer parameters and CNOTs than standard QAOA at the same convergence threshold, with the multi-qubit pool requiring about half as many CNOTs.For D=5 standard QAOA does not reach δE = 10^-3 within the simulation and is counted at 15 layers.
III. SHORTCUTS TO ADIABATICITY
The paper interprets ADAPT-QAOA as potentially related to shortcuts to adiabaticity, which enable nonadiabatic evolution while retaining instantaneous ground-state tracking.
- Motivation: Short-depth standard QAOA is an ad hoc ansatz rather than a fully digitized adiabatic evolution, motivating a shortcut-based interpretation of ADAPT-QAOA.The paper presents this as a possible explanation for ADAPT-QAOA's faster convergence.
- STA concept: Shortcuts to adiabaticity add a counterdiabatic term HCD so a system can follow instantaneous ground states without slow evolution.The resulting evolution is nonadiabatic while the instantaneous eigenstates become exact solutions of the updated Hamiltonian.
- STA concept: The authors provide evidence that ADAPT-QAOA is related to shortcuts to adiabaticity and may therefore explain its faster convergence than standard QAOA.The comparison is specifically framed against standard QAOA as the adiabatic counterpart.
A. Approximate adiabatic gauge potentials
The paper reviews adiabatic gauge potentials and their approximate nested-commutator construction, while noting that exact matrix elements can diverge as system size increases.
- Gauge-potential framework: Adiabatic gauge potentials transform the time-dependent Hamiltonian into an instantaneous eigenbasis where the transformed Hamiltonian is diagonal.The state evolves under H(θ(t)), and a unitary U(θ(t)) defines the instantaneous basis.
- Approximation: Exact gauge-potential matrix elements contain energy denominators that can become exponentially small, causing divergences as system size grows.This motivates approximate gauge-potential constructions.
- Approximation: The approximate gauge potential is expanded in nested commutators with coefficients {a1, a2, ..., ap}, where p specifies the expansion order.The coefficients are determined by minimizing a trace-based objective.
- Approximation: The trace-based objective is minimized when the trial operator equals the exact adiabatic gauge potential.The construction uses matrix-calculus identities and trace properties.
- Gauge-potential framework: Their defining condition is [H, i∂θH − [Aθ, H]] = 0, which follows from differentiating the instantaneous-basis Hamiltonian.This condition identifies the gauge potential operators relevant to the adiabatic evolution.
B. Connection between ADAPT-QAOA and STA
The authors examine whether ADAPT-QAOA’s selected mixers align with dominant operators in approximate counterdiabatic Hamiltonians. Across 32 Max-Cut instances, higher-order counterdiabatic approximations increase this overlap, supporting a connection between ADAPT-QAOA and shortcuts to adiabaticity.
- STA connection: ADAPT-QAOA is compared with approximate counterdiabatic Hamiltonians for 32 regular Max-Cut graphs with n = 6 and D = 3.The analysis uses the five operators with the largest coefficients in the time-averaged HCD for each graph.
- STA connection: The probability P measures how often the mixer selected at layer p belongs to the five dominant operators of the corresponding HCD.It is averaged over the 32 graph instances and plotted for different approximation orders.
- Results: 100% of first-layer mixer operators belong to the corresponding dominant-operator sets O(i).For higher layers, the probability is inversely proportional to the layer number.
- Results: Higher-order HCD approximations increase the probability that ADAPT-QAOA mixers appear among the dominant HCD operators.The authors suggest ADAPT-QAOA identifies rotation axes associated with faster convergence and that STA may help construct operator pools.
IV. CONCLUSION
The paper concludes that ADAPT-QAOA builds problem-tailored ansätze iteratively and outperforms standard QAOA on the tested random diagonal Hamiltonians. Its mixer-pool flexibility also permits adaptation to hardware constraints, while extensions to higher-dimensional problems and further STA study remain open.
- Conclusion: ADAPT-QAOA grows the ansatz iteratively in a way that is naturally tailored to the optimization problem.
- Conclusion: ADAPT-QAOA always outperforms standard QAOA on the tested instances of random diagonal Hamiltonians.
- Conclusion: Flexible mixer-pool selection allows ADAPT-QAOA to accommodate native gates, hardware connectivity, and experimental constraints.
- Conclusion: The authors identify higher-dimensional optimization problems and the connection to shortcuts to adiabaticity as directions for further work.
Appendix B: First Layer of ADAPT-QAOA ansatz
The first-layer analysis identifies the stationary points and shows that the energy minimum occurs only at nonzero γ, while γ = 0 is a saddle point requiring a nonzero initialization. Simulations also indicate better performance for larger, less-connected D = 2 graphs.
- First-layer stationary points: At the first layer, the energy minimum never occurs at γ = 0 for any operator in the pool.
- First-layer stationary points: For p = 1, the initial state is |+⟩⊗n, giving ⟨Ha⟩ = 0 and β = ±π/4 when ⟨0|G(γ)|0⟩ ≠ 0.
- First-layer stationary points: γ = 0 is excluded from the nonzero-γ stationary condition because ⟨0|H_a^2|0⟩ > 0 for the nonzero state H_a|+⟩⊗n.
- First-layer stationary points: The alternative extrema with ⟨0|G(γ*)|0⟩ = 0 are saddle points, including γ = 0.
- Initialization: The implementation therefore initializes γ at a small nonzero value, such as γ0 = 0.01, rather than at the critical point γ0 = 0.
- Scalability: For D = 2 graphs with n = 8 and n = 10 qubits, ADAPT-QAOA shows substantially better performance than standard QAOA even when D/n < 1/2.
Appendix D: Role of entangling mixers versus entangling gates
Entangling mixers are associated with ADAPT-QAOA’s faster convergence and are selected frequently, while the compiled ansatz can use fewer entangling gates than standard QAOA. The comparison is made using energy error versus CNOT count.
- Resource comparison: Including entangling mixers produces dramatically faster convergence to the exact solution than original QAOA while reducing compiled-ansatz entangling gates.
- Operator selection: For n = 6 regular graphs, the multi-qubit mixer pool selects two-qubit entangling operators approximately 70% of the time.
- Operator selection: The single-qubit mixer pool selects Xi operators instead of the original mixer approximately 25% of the time.
- CNOT-based comparison: Figure 7 compares energy error against total CNOTs for original QAOA and ADAPT-QAOA using single-qubit or multi-qubit pools on n = 6 graphs with D = 3 and D = 5.