Runtime Quantum Advantage with Digital Quantum Optimization
Preprint
Abstract
We demonstrate experimentally that the bias-field digitized counterdiabatic quantum optimization (BF-DCQO) algorithm on IBM's 156-qubit devices can outperform simulated annealing (SA) and CPLEX in time-to-approximate solutions for specific higher-order unconstrained binary optimization (HUBO) problems. We suitably select problem instances that are challenging for classical methods, running in fractions of minutes even with multicore processors. On the other hand, our counterdiabatic quantum algorithms obtain similar or better results in at most a few seconds on quantum hardware, achieving runtime quantum advantage. Our analysis reveals that the performance improvement becomes increasingly evident as the system size grows. Given the rapid progress in quantum hardware, we expect that this improvement will become even more pronounced, potentially leading to a quantum advantage of several orders of magnitude. Our results indicate that available digital quantum processors, when combined with specific-purpose quantum algorithms, exhibit a runtime quantum advantage even in the absence of quantum error correction.Keywords
All Related Versions
This publication has 40 references indexed in Scilit:
- Short-depth QAOA circuits and quantum annealing on higher-order ising modelsnpj Quantum Information, 2024
- Evidence for the utility of quantum computing before fault toleranceNature, 2023
- Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers2023
- Computational complexity continuum within Ising formulation of NP problemsCommunications Physics, 2022
- Modelling impulsive noise in indoor powerline communication systemsSignal, Image and Video Processing, 2020
- Total variation with overlapping group sparsity for deblurring images under Cauchy noiseApplied Mathematics and Computation, 2019
- Tail risk premia and return predictabilityJournal of Financial Economics, 2015
- Fat tails and asymmetry in financial volatility modelsMathematics and Computers in Simulation, 2004
- Adiabatic Population Transfer with Control FieldsThe Journal of Physical Chemistry A, 2003
- Spin glasses with p-spin interactionsNuclear Physics B, 1985