Digitized-Counterdiabatic Quantum Optimization

Abstract

We propose digitized-counterdiabatic quantum optimization (DCQO) to achieve polynomial enhancement over adiabatic quantum optimization for the general Ising spin-glass model, which includes the whole class of combinatorial optimization problems. This is accomplished via the digitization of adiabatic quantum algorithms that are catalysed by the addition of non-stoquastic counterdiabatic terms. The latter are suitably chosen, not only for escaping classical simulability, but also for speeding up the performance. Finding the ground state of a general Ising spin-glass Hamiltonian is used to illustrate that the inclusion of k-local non-stoquastic counterdiabatic terms can always outperform the traditional adiabatic quantum optimization with stoquastic Hamiltonians. In particular, we show that a polynomial enhancement in the ground-state success probability can be achieved for a finite-time evolution, even with the simplest 2-local counterdiabatic terms. Furthermore, the considered digitization process, within the gate-based quantum computing paradigm, provides the flexibility to introduce arbitrary non-stoquastic interactions. Along these lines, using our proposed paradigm on current NISQ computers, quantum speed-up may be reached to find approximate solutions for NP-complete and NP-hard optimization problems. We expect DCQO to become a fast-lane paradigm towards quantum advantage in the NISQ era.

5 pages, 4 figures

References in corpus (16)

• Surface codes: Towards practical large-scale quantum computation
• Shortcut to adiabatic passage in two and three level atoms
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• Quantum annealing with antiferromagnetic fluctuations
• Digitized-counterdiabatic quantum approximate optimization algorithm
• Counterdiabaticity and the quantum approximate optimization algorithm
• Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
• Shortcuts to adiabaticity for quantum annealing
• Scaling overhead of embedding optimization problems in quantum annealing
• Two-parameter counter-diabatic driving in quantum annealing
• Genetic optimization of quantum annealing
• Digitized Adiabatic Quantum Factorization
• Efficient Product Formulas for Commutators and Applications to Quantum Simulation
• Success of digital adiabatic simulation with large Trotter step
• Polynomial scaling enhancement in ground-state preparation of Ising spin models via counter-diabatic driving
• Experimental Determination of Electronic States via Digitized Shortcut-to-Adiabaticity and Sequential Digitized Adiabaticity

Cited by in corpus (30)

• Quantum Dynamics in Krylov Space: Methods and Applications
• Towards adiabatic quantum computing using compressed quantum circuits
• Portfolio Optimization with Digitized-Counterdiabatic Quantum Algorithms
• Shortcuts to Adiabaticity in Krylov Space
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Shortcuts to adiabaticity: theoretical framework, relations between different methods, and versatile approximations
• Variational counterdiabatic driving of the Hubbard model for ground-state preparation
• Optimizing Counterdiabaticity by Variational Quantum Circuits
• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
• Counterdiabatic Formalism of Shortcuts to Adiabaticity
• Digitized Counterdiabatic Quantum Algorithms for Logistics Scheduling
• Bias-field digitized counterdiabatic quantum optimization
• Scaling of errors in digitized counterdiabatic driving
• Photonic counterdiabatic quantum optimization algorithm
• Practicality of quantum adiabatic algorithm for chemistry applications
• Digital-Analog Counterdiabatic Quantum Optimization with Trapped Ions
• Single-Layer Digitized-Counterdiabatic Quantum Optimization for $p$-spin Models
• Quantum Shortcut to Adiabaticity for State Preparation in a Finite-Sized Jaynes-Cummings Lattice
• Ising Hamiltonians for Constrained Combinatorial Optimization Problems and the Metropolis-Hastings Warm-Starting Algorithm
• Fighting Exponentially Small Gaps by Counterdiabatic Driving
• Shortcuts to adiabaticity in open quantum critical systems
• Quantum Hopfield Model with Dilute Memories
• Experimental factoring integers using fixed-point-QAOA with a trapped-ion quantum processor
• Improving Variational Counterdiabatic Driving with Weighted Actions and Computer Algebra
• Counterdiabatic ADAPT-VQE for molecular simulation
• Digitized counterdiabatic quantum critical dynamics
• Energy-saving fast-forward scaling
• Quantum coherence and counterdiabatic quantum computing
• A Quantum Constraint Generation Framework for Binary Linear Programs
• Quantum circuit evolutionary framework applied on set partitioning problem