Efficient Large-Scale Quantum Optimization via Counterdiabatic Ansatz
arXiv:2409.15055 · doi:10.1103/PhysRevA.111.052628
Abstract
Quantum Approximate Optimization Algorithm (QAOA) is one of the fundamental variational quantum algorithms, while a version of QAOA that includes counterdiabatic driving, termed Digitized Counterdiabatic QAOA (DC-QAOA), is generally considered to outperform QAOA for all system sizes when the circuit depth for the two algorithms are held equal. Nevertheless, DC-QAOA introduces more CNOT gates per layer, so the overall circuit complexity is a tradeoff between the number of CNOT gates per layer and the circuit depth and must be carefully assessed. In this paper, we conduct a comprehensive comparison of DC-QAOA and QAOA on MaxCut problem with the total number of CNOT gates held equal, and we focus on one implementation of counterdiabatic terms using nested commutators in DC-QAOA, termed as DC-QAOA(NC). We have found that DC-QAOA(NC) reduces the overall circuit complexity as compared to QAOA only for sufficiently large problems, and for MaxCut problem the number of qubits must exceed 16 for DC-QAOA(NC) to outperform QAOA. Additionally, we benchmark DC-QAOA(NC) against QAOA on the Sherrington-Kirkpatrick model under realistic noise conditions, finding that DC-QAOA(NC) exhibits significantly improved robustness compared to QAOA, maintaining higher fidelity as the problem size scales. Notably, in a direct comparison between one-layer DC-QAOA(NC) and three-layer QAOA where both use the same number of CNOT gates, we identify an exponential performance advantage for DC-QAOA(NC), further signifying its suitability for large-scale quantum optimization tasks. Moreover, based on our finding, we have devised an instance-sequential training method for DC-QAOA(NC) circuits, which, compared to traditional methods, offers performance improvement while using even fewer quantum resources.
arXiv comment15 pages, 12 figures
References in corpus (26)
- A variational eigenvalue solver on a quantum processor
- Variational Quantum Algorithms
- Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
- The theory of variational hybrid quantum-classical algorithms
- Quantum Circuit Learning
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Fast optimal frictionless atom cooling in harmonic traps
- Digitized adiabatic quantum computing with a superconducting circuit
- Obstacles to State Preparation and Variational Optimization from Symmetry Protection
- Minimizing irreversible losses in quantum systems by local counter-diabatic driving
- New Inference Rules for Max-SAT
- Variational Quantum Eigensolver with Fewer Qubits
- Shortcuts to Adiabaticity in Digitized Adiabatic Quantum Computing
- Digitized-counterdiabatic quantum approximate optimization algorithm
- Parameter Concentration in Quantum Approximate Optimization
- Superadiabatic dynamics in open quantum systems
- Counterdiabatic Optimised Local Driving
- Digitized-Counterdiabatic Quantum Algorithm for Protein Folding
- Portfolio Optimization with Digitized-Counterdiabatic Quantum Algorithms
- Rapid counter-diabatic sweeps in lattice gauge adiabatic quantum computing
- An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
- On Circuit Depth Scaling For Quantum Approximate Optimization
- Shortcuts to Quantum Approximate Optimization Algorithm
- Performance Analysis of Multi-Angle QAOA for p > 1
- Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer