Source-linked AI summary
Digitized-counterdiabatic quantum approximate optimization algorithm
P. Chandarana, N. N. Hegade, K. Paul, F. Albarrán-Arriagada, E. Solano, A. del Campo, Xi Chen
TL;DR
QAOA's dependence on its trial-state ansatz and its need for large layer counts motivate a search for improved circuits. The paper adds counterdiabatic driving to a digitized QAOA ansatz and reports better performance than standard QAOA across the studied models and problems.
Problem
QAOA depends on its trial-state ansatz, and large layer counts can make it unsuitable for NISQ devices while increasing classical-optimization costs and exposing optimization difficulties.
Source: §I · p. 1Method
DC-QAOA adds a variational counterdiabatic driving term to the digitized QAOA ansatz alongside the problem and mixing Hamiltonians.
Source: §I · p. 1, §II · p. 2Results
DC-QAOA outperforms QAOA across the models studied, with faster ground-state convergence for low-layer circuits.
Source: §VI · p. 6Takeaways & Limitations
For high-depth circuits, DC-QAOA can be applied in the initial layers to enhance standard QAOA's performance.
Source: §VI · p. 6
Abstract
from arXiv · showhide
The quantum approximate optimization algorithm (QAOA) has proved to be an effective classical-quantum algorithm serving multiple purposes, from solving combinatorial optimization problems to finding the ground state of many-body quantum systems. Since QAOA is an ansatz-dependent algorithm, there is always a need to design ansatz for better optimization. To this end, we propose a digitized version of QAOA enhanced via the use of shortcuts to adiabaticity. Specifically, we use a counterdiabatic (CD) driving term to design a better ansatz, along with the Hamiltonian and mixing terms, enhancing the global performance. We apply our digitized-counterdiabatic QAOA to Ising models, classical optimization problems, and the P-spin model, demonstrating that it outperforms standard QAOA in all cases we study.
I. INTRODUCTION
QAOA uses shallow parameterized circuits and classical optimization, but its performance depends on the trial-state ansatz and large layer counts can make optimization costly. The paper proposes DC-QAOA, adding counterdiabatic driving to improve performance, and compares it with QAOA across physical and optimization problems.
I. INTRODUCTION
- QAOA is a shallow-circuit approach to combinatorial optimization with classically optimized parameters, also applied to ground-state problems in physical systems.The paper frames QAOA as an ansatz-dependent algorithm.Source: §I · p. 1
- Large p can increase classical-optimization cost and contribute to vanishing gradients and local minima in QAOA.The section says adiabatic algorithms produce near-optimal results at large p, which is unsuitable for current NISQ devices.Source: §I · p. 1
- Shortcuts to adiabaticity include counterdiabatic driving, which has been used in applications such as entangled-state preparation and quantum annealing.The section presents these methods as a way to improve traditional adiabatic processes without requiring slow driving.Source: §I · p. 1
- DC-QAOA adds counterdiabatic driving to QAOA to improve its performance.The introduction describes two advantages of CD driving: fewer circuit layers and optimization parameters, and a better approximate trial state.Source: §I · p. 1
- The paper compares DC-QAOA with QAOA on Ising models, MaxCut, the Sherrington-Kirkpatrick model, and P-spin variants.The introduction says the comparison uses approximation ratios and focuses on shallow circuits.Source: §I · p. 2
II. DIGITIZED COUNTER-DIABATIC QUANTUM APPROXIMATE OPTIMIZATION ALGORITHM (DC-QAOA)
The section builds DC-QAOA from a digitized annealing ansatz and adds a variational counterdiabatic term to the conventional QAOA circuit. It describes how the CD operators are selected and optimized, and how the cost function is evaluated.
II. DIGITIZED COUNTER-DIABATIC QUANTUM APPROXIMATE OPTIMIZATION ALGORITHM (DC-QAOA)
- The digitized annealing ansatz uses p subunitaries for time steps, with the annealing Hamiltonian decomposed into M terms having at most k-body interactions.In the conventional QAOA parameterization, the mixer and problem-Hamiltonian evolutions are controlled by β and γ parameters.Source: §II · p. 2
- DC-QAOA adds a variational CD parameter at each step to address the large layer counts and gate burden associated with QAOA for interacting systems.The additional parameter is quantified as inclusion of the CD driving term in the problem Hamiltonian.Source: §II · p. 2
- The CD term is selected from a problem-dependent operator pool derived using nested commutators, with the studied second-order pool containing local and two-body operators.The paper says the pool may contain other operators for other problem Hamiltonians.Source: §II · p. 2
- The authors choose CD operators by system and success probability; local driving works better for TFIM and P-spin but is unsuitable for MaxCut.The CD coefficients become additional variational parameters, and the method does not require complex calculation of those coefficients.Source: §II · p. 3
- The cost function is the trial state's energy expectation for the problem Hamiltonian, and the paper uses Momentum and Adagrad optimizers.These are stochastic-gradient-descent methods; the section notes their performance depends on the problem.Source: §II · p. 3
III. ISING SPIN MODELS
The section applies DC-QAOA to homogeneous periodic 1D Ising chains and GHZ-state preparation, choosing CD operators according to the model and balancing circuit depth against parameter count.
III. ISING SPIN MODELS
- With periodic boundaries, the homogeneous chain yields LFIM when k_i = 0, TFIM when h_i = 0, and a GHZ ground state when both fields vanish.The mixer is chosen to prepare an equal superposition of the qubits.Source: §III · p. 4
- The CD operator is selected heuristically: the local term suits LFIM, while TFIM and GHZ call for a second-order term.The passage attributes the different choices to the models’ ground-state and excitation structure.Source: §III · p. 4
- Adding CD raises the parameter count from 2p to 3p; its per-layer depth cost depends on the operator, and its advantage is specific to low p.The reported depth increments are d_cd = 1 for LFIM and d_cd = 4 for TFIM; at fixed system size, QAOA and DC-QAOA become comparable at large p.Source: §III · p. 4
IV. CLASSICAL OPTIMIZATION PROBLEMS
For MaxCut and the SK model, the section compares DC-QAOA with QAOA and reports stronger approximation ratios in the studied small-graph or low-layer regimes, with the methods converging as layers increase for SK.
IV. CLASSICAL OPTIMIZATION PROBLEMS
- The MaxCut study uses unweighted 3-regular graphs and a CD operator pool of {σzσy, σyσz}; its p > 1 analysis is left for future work.The authors expect the 3p-parameter landscape to become complicated and potentially exhibit vanishing gradients.Source: §IV · p. 4
- For unweighted 3-regular MaxCut at p = 1, DC-QAOA reaches unit approximation ratio on small graphs and exceeds QAOA as graph size grows, though its ratio declines.The comparison covers graph sizes up to 14 vertices.Source: §IV · p. 4, Figure 3 · p. 5
- For six-spin SK instances, DC-QAOA has a higher approximation ratio than QAOA at low layer counts, and their values converge as p increases.The study considers ten randomly chosen sets of couplings.Source: Figure 3 · p. 5, §IV · p. 5
- The SK model is treated as a combinatorial search problem on a complete graph, with the same CD operator pool used for MaxCut.The simulations use L = 6 spins and ten coupling instances.Source: §IV · p. 5
V. P-SPIN MODEL
For the studied P-spin cases, DC-QAOA outperforms QAOA: it reaches unit approximation ratio for every tested P = 4, h = 0 initialization and approaches unity for P = 3, even at p = 1.
V. P-SPIN MODEL
- The P-spin benchmark is a long-range, exactly solvable, fully connected model with a quantum phase transition that makes ground-state preparation challenging by quantum annealing.For P ≥ 3, the transition is first-order and the energy gap closes exponentially with increasing system size.Source: §V · p. 5
- For P = 3, the ground state is a product state, favoring the local CD operator; for the degenerate P = 4 case, local CD driving steers the trial state to one of two ground states.The authors attribute the P = 3 result to the product-state ground state and the P = 4 result to convergence to one of the two degenerate states.Source: §V · p. 5
- For P = 4, DC-QAOA reaches unit R for every tested h = 0 initialization; for P = 3, it approaches unity even at p = 1, while QAOA misses the target at p = 1.The P = 4 comparison uses 10 initializations at p = 1; the P = 3 comparison covers p = 1, 2, 3.Source: §V · pp. 5–6, Figure 4 · p. 6, Figure 5 · p. 6
VI. DISCUSSION AND CONCLUSION
The paper introduces DC-QAOA, a QAOA variant using counterdiabatic driving, and reports improved performance over QAOA across the models studied. The authors identify short-depth circuits as its preferred setting and suggest possible extensions to high-depth optimization and hardware experiments.
VI. DISCUSSION AND CONCLUSION
- Adding a CD gate chosen from a predefined set as a variational parameter enhances QAOA performance at shorter circuit depths.The authors conclude that DC-QAOA is preferable for shorter-depth circuits.Source: §VI · p. 6
- Across the models studied, DC-QAOA outperforms QAOA and converges to the ground state faster for low-layer circuits.The benchmarks include Ising models, entangled-state preparation, MaxCut, the SK model, and the P-spin model.Source: §VI · p. 6
- For high-depth circuits, the authors suggest applying DC-QAOA only in the initial layers and propose using its low-depth optimal parameters to initialize high-depth QAOA.Experimental realization on real hardware is identified as a prospect for further progress.Source: §VI · p. 6