Demonstration of algorithmic quantum speedup
Daniel Lidar, University of Southern California
Despite the development of increasingly capable quantum computers, an experimental demonstration of a provable algorithmic quantum speedup employing today’s non-fault-tolerant devices has remained elusive. In this talk I will report on the first demonstration of such a speedup, quantified in terms of the scaling of time-to-solution with problem size. The demonstration is for a bitstring guessing game, where the players have access to either a quantum or a classical oracle that returns the inner product of the secret string with the guess. The secret string changes after every guess, so the classical time to solution scales exponentially. For an ideal quantum computer the problem is solved efficiently using the Bernstein-Vazirani algorithm. We implemented this algorithm utilizing two different 27-qubit IBM Quantum superconducting processors. The speedup is observed when the computation is protected by dynamical decoupling — an open-loop quantum control protocol designed to suppress noise due to the environment — but not without decoupling. This quantum speedup result does not rely on complexity-theoretic conjectures.
Background: arXiv:2207.03670, arXiv:2108.04530, PRL 121, 220502 (2018)