Demonstration of algorithmic quantum speedup

Understand

Quantum algorithms theoretically outperform classical algorithms in solving problems of increasing size, but computational errors must be kept to a minimum to realize this potential.

• Despite the development of increasingly capable quantum computers (QCs), an experimental demonstration of a provable algorithmic quantum speedup employing today's non-fault-tolerant, noisy intermediate-scale quantum (NISQ) devices has remained elusive.
• Here, we unequivocally demonstrate such a speedup, quantified in terms of the scaling with the problem size of the time-to-solution metric.
• We implement the single-shot Bernstein-Vazirani algorithm, which solves the problem of identifying a hidden bitstring that changes after every oracle query, utilizing two different 27-qubit IBM Quantum (IBMQ) superconducting processors.