  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.
