Counterdiabaticity and the quantum approximate optimization algorithm

Abstract

The quantum approximate optimization algorithm (QAOA) is a near-term hybrid algorithm intended to solve combinatorial optimization problems, such as MaxCut. QAOA can be made to mimic an adiabatic schedule, and in the $p\to \infty$ limit the final state is an exact maximal eigenstate in accordance with the adiabatic theorem. In this work, the connection between QAOA and adiabaticity is made explicit by inspecting the regime of $p$ large but finite. By connecting QAOA to counterdiabatic (CD) evolution, we construct CD-QAOA angles which mimic a counterdiabatic schedule by matching Trotter "error" terms to approximate adiabatic gauge potentials which suppress diabatic excitations arising from finite ramp speed. In our construction, these "error" terms are helpful, not detrimental, to QAOA. Using this matching to link QAOA with quantum adiabatic algorithms (QAA), we show that the approximation ratio converges to one at least as $1-C(p)\sim 1/p^{\mu }$. We show that transfer of parameters between graphs, and interpolating angles for $p+1$ given $p$ are both natural byproducts of CD-QAOA matching. Optimization of CD-QAOA angles is equivalent to optimizing a continuous adiabatic schedule. Finally, we show that, using a property of variational adiabatic gauge potentials, QAOA is at least counterdiabatic, not just adiabatic, and has better performance than finite time adiabatic evolution. We demonstrate the method on three examples: a 2 level system, an Ising chain, and the MaxCut problem.

27 pages, 6 figures

References in corpus (10)

• The Magnus expansion and some of its applications
• Shortcut to adiabatic passage in two and three level atoms
• Warm-starting quantum optimization
• Quantum Adiabatic Brachistochrone
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Optimal non-linear passage through a quantum critical point
• MAXCUT QAOA performance guarantees for p >1
• Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
• Engineering adiabaticity at an avoided crossing with optimal control
• Behavior of Analog Quantum Algorithms

Cited by in corpus (68)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• Digitized-counterdiabatic quantum approximate optimization algorithm
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Reinforcement Learning for Many-Body Ground-State Preparation Inspired by Counterdiabatic Driving
• Counterdiabatic Optimised Local Driving
• Digitized-Counterdiabatic Quantum Algorithm for Protein Folding
• Avoiding barren plateaus via transferability of smooth solutions in Hamiltonian Variational Ansatz
• Portfolio Optimization with Digitized-Counterdiabatic Quantum Algorithms
• Shortcuts to Adiabaticity in Krylov Space
• Digitized-Counterdiabatic Quantum Optimization
• Comparative study of variations in quantum approximate optimization algorithms for the Traveling Salesman Problem
• Scaling Quantum Approximate Optimization on Near-term Hardware
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
• Self-healing of Trotter error in digital adiabatic state preparation
• Shortcuts to adiabaticity: theoretical framework, relations between different methods, and versatile approximations
• Analytical Framework for Quantum Alternating Operator Ansätze
• Variational counterdiabatic driving of the Hubbard model for ground-state preparation
• Shortcuts to Quantum Approximate Optimization Algorithm
• Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement
• An introduction to variational quantum algorithms for combinatorial optimization problems
• Extending relax-and-round combinatorial optimization solvers with quantum correlations
• Efficient Paths for Local Counterdiabatic Driving
• Squeezing and quantum approximate optimization
• Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
• Optimizing Counterdiabaticity by Variational Quantum Circuits
• Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm
• The Quantum Alternating Operator Ansatz for Satisfiability Problems
• Taming quantum systems: A tutorial for using shortcuts-to-adiabaticity, quantum optimal control, and reinforcement learning
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Counterdiabatic optimized driving in quantum phase sensitive models
• Success of digital adiabatic simulation with large Trotter step
• A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters
• Shortcut-to-Adiabatic Controlled-Phase Gate in Rydberg Atoms
• Improving the performance of quantum approximate optimization for preparing non-trivial quantum states without translational symmetry
• Non-Adiabatic Quantum Optimization for Crossing Quantum Phase Transitions
• Towards Optimizations of Quantum Circuit Simulation for Solving Max-Cut Problems with QAOA
• Beyond Quantum Annealing: Optimal control solutions to MaxCut problems
• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
• Efficient DCQO Algorithm within the Impulse Regime for Portfolio Optimization
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• Improving the Performance of Digitized Counterdiabatic Quantum Optimization via Algorithm-Oriented Qubit Mapping
• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
• A numerical approach for calculating exact non-adiabatic terms in quantum dynamics
• Modelling noise in global Molmer-Sorensen interactions applied to quantum approximate optimization
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• Counterdiabatic driving for long-lived singlet state preparation
• High-dimensional counterdiabatic quantum computing
• Imaginary Hamiltonian variational ansatz for combinatorial optimization problems
• Bang-bang preparation of quantum many-body ground states in two dimensions: optimization of the algorithm with a two-dimensional tensor network
• Constraint-Aware Quantum Optimization via Hamming Weight Operators
• Fighting Exponentially Small Gaps by Counterdiabatic Driving
• Path Matters: Industrial Data Meet Quantum Optimization
• Walsh-Floquet Theory of Periodic Kick Drives
• Improving Variational Counterdiabatic Driving with Weighted Actions and Computer Algebra
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
• Noise Effects on Diabatic Quantum Annealing Protocols
• Optimized fermionic SWAP networks with equivalent circuit averaging for QAOA
• Role of overparametrization in quantum approximate optimization
• Ancillary entangling Floquet kicks for accelerating quantum algorithms
• Evidence for effectively constant shot complexity in the quantum approximate optimization algorithm without per-instance optimization
• Shortcuts to Analog Preparation of Non-Equilibrium Quantum Lakes
• Digital controllability of transverse field Ising chains
• Hidden local adiabatic ramp in the modulated time evolution and the quantum approximate optimization algorithm