Pauli-Sparse regularised Counterdiabatic Shortcuts for Linear-Ramp QAOA

Technical Summary: Pauli-Sparse Regularised Counterdiabatic Shortcuts for Linear-Ramp QAOA

Problem Statement
Combinatorial optimization via the Quantum Approximate Optimization Algorithm (QAOA) faces a critical trade-off between parameter efficiency and dynamical accuracy. Linear-ramp QAOA (LR-QAOA) reduces the classical optimization burden by constraining layer angles to follow an adiabatic-inspired schedule with few parameters. However, for Hamiltonians with small or exponentially small spectral gaps, finite-time adiabatic evolution suffers from strong diabatic transitions, causing the system to leak out of the desired low-energy solution manifold. While counterdiabatic (CD) driving offers a principled method to suppress these transitions by adding a correction term derived from the Adiabatic Gauge Potential (AGP), standard approaches often require dense operators or pre-specified ansatzes that are infeasible under finite gate budgets. Furthermore, exact AGPs for hard optimization problems often involve resolving microscopic, exponentially small energy splittings within a low-energy manifold, which is computationally expensive and potentially unnecessary for finding a high-quality solution.

Methodology
The authors propose a framework for constructing a Pauli-sparse, regularised counterdiabatic extension of LR-QAOA. The core methodology involves solving the regularised AGP equation directly in the Pauli basis without forming the full dense Liouvillian matrix.

1. Regularised AGP Equation: The method solves the linear system $(\mathcal{L}_H^2 + \eta I) A_\lambda^{(\eta)} = -i \mathcal{L}_H(G)$, where $\mathcal{L}_H(X) = [H, X]$ is the commutator superoperator, $G = \partial_\lambda H$, and $\eta > 0$ is a regularization parameter. This equation is derived from minimizing a regularised functional that balances the cancellation of diabatic transitions against the norm of the potential.
2. Energy-Resolution Mechanism: The parameter $\eta$ acts as an energy-resolution scale. It suppresses transitions associated with energy differences $|\omega| \ll \sqrt{\eta}$ while retaining those with $|\omega| \gg \sqrt{\eta}$. This allows the method to ignore exponentially small splittings within a target low-energy manifold (avoiding the need for exact adiabatic following) while still preventing leakage to higher-energy excited states.
3. Inexact Conjugate Gradient (CG) Solver: Instead of computing a dense AGP and compressing it, the authors employ an inexact conjugate-gradient method in Pauli coordinates.
   • Matrix-Free Application: The operator $(\mathcal{L}_H^2 + \eta I)$ is applied symbolically using Pauli commutators, avoiding the construction of the $4^n$-dimensional matrix.
   • Truncation: During the CG iterations, the Pauli expansion is truncated to retain only the $m$ largest coefficients (magnitude truncation). This transforms the linear solver into a support-discovery procedure, identifying a gate-budget-aware set of implementable Pauli rotations.
   • Residual Recomputation: To prevent error accumulation from truncation, the residual is recomputed exactly at each step rather than updated recursively.
4. Galerkin Refit and Certification: Once a sparse support is discovered, a Galerkin refit is performed to optimize the coefficients on this specific support. The quality of the approximation is certified a posteriori using a residual bound: $\|A - A_\lambda^{(\eta)}\|_{HS} \leq \|R\|_{HS} / \eta$, where $R$ is the residual of the linear system. This provides a computable error bound without requiring knowledge of the exact solution.
5. Circuit Integration: The resulting sparse Pauli generator is inserted into the LR-QAOA circuit as a counterdiabatic layer. The variational optimization is performed over a reduced set of parameters: the ramp amplitudes $(\Delta\beta, \Delta\gamma)$ and the counterdiabatic amplitude $\Delta_{CD}$.

Key Contributions

• Direct Pauli-Coordinate Solution: Unlike prior CD-QAOA works that prescribe ansatzes (e.g., local terms, nested commutators) or compute dense AGPs, this work solves the regularised AGP equation directly in Pauli coordinates, simultaneously approximating the potential and selecting a sparse set of implementable rotations.
• Regularisation as a Physical Filter: The paper reframes the regularization parameter $\eta$ not merely as a numerical stabilizer but as a physical filter that suppresses transitions below a specific energy scale. This is particularly effective for optimization problems where the goal is to stay within a low-energy manifold rather than track a single eigenstate through exponentially small gaps.
• Sparse Linear Algebra Pipeline: The authors develop a complete pipeline combining matrix-free symbolic commutators, truncated CG for support discovery, Galerkin refitting for coefficient optimization, and residual-based error certification. This approach imports ideas from inexact Krylov methods to the quantum control context.
• Theoretical Guarantees: The paper provides rigorous bounds on the distance between the regularised and unregularised potentials, the condition number of the linear system, and the error of the sparse approximation relative to the exact regularised solution.

Results
Numerical experiments were conducted on Ferromagnetic Chain (FC) instances and perturbed FC–MaxCut/MarketSplit instances:

• FC Validation: On FC instances, standard LR-QAOA showed poor performance as system size increased, failing to reach the ordered manifold. The proposed LR-CD-QAOA with exact AGP achieved high ordered-manifold probabilities ($P_{ord} \approx 0.9$) even at low depth. Crucially, the method remained robust across a range of $\eta$ values, confirming that it does not need to resolve the exponentially small ground-state splitting to suppress leakage to excited states.
• Sparse CG Convergence: Experiments demonstrated that a small number of CG iterations ($K \approx 4$) and a moderate Pauli-support budget ($m=64$) were sufficient to recover most of the benefits of the dense AGP. The approximation ratio improved monotonically with both iteration count and support size.
• Blended Instances: On perturbed MaxCut and MarketSplit instances (where the Hamiltonian is dominated by the FC component), LR-CD-QAOA significantly outperformed uncorrected LR-QAOA. While LR-QAOA remained far from the optimum even at depth $p=8$, the CD-corrected version achieved approximation ratios close to the exact optimum at moderate depths.

Significance
The paper claims that this framework substantially broadens the practical applicability of QAOA to QUBO optimization. By improving robustness across heterogeneous problem landscapes—specifically those with near-degenerate low-energy structures and small spectral gaps—the method addresses a primary bottleneck in near-term quantum optimization. It offers a pathway to implement effective counterdiabatic driving on quantum hardware with limited gate budgets, moving beyond the limitations of parameter-efficient but dynamically inefficient linear ramps. The work establishes a hybrid optimization paradigm where classical sparse linear algebra techniques are used to construct quantum circuits that are dynamically adapted to the specific spectral properties of the problem Hamiltonian.