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 catalyzed by the addition of nonstoquastic counterdiabatic terms. The latter is 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 nonstoquastic 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 two-local counterdiabatic terms. Furthermore, the considered digitization process within the gate-based quantum computing paradigm, provides the flexibility to introduce arbitrary nonstoquastic interactions. As an experimental test, we study the performance of the DCQO algorithm on cloud-based IBM's superconducting and Quantinuum's ion-trap quantum processors with up to 8 qubits. Along these lines, using our proposed paradigm on current noisy intermediate-scale quantum (NISQ) computers, quantum speedup may be reached to find approximate solutions for NP-complete and NP-hard optimization problems. We expect DCQO to become a fast-lane paradigm toward quantum advantage in the NISQ era.