Abstract: 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 based on the single-shot Bernstein-Vazirani algorithm which efficiently solves the problem of identifying a hidden bitstring that changes after every oracle query. 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. In contrast with recent quantum supremacy demonstrations, the quantum speedup reported here does not rely on complexity-theoretic conjectures.

Watch Dr. Lidar’s talk here: https://youtu.be/QDNn-qYwUqQ