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)



Jan 25 2023


1:00 pm - 2:00 pm
C520 Physics and Astronomy Building


C520 Physics and Astronomy Building
UW, 15th and Pacific, Seattle