Lecturer: Prof. Daniel Lidar, Viterbi Professorship of Engineering at the University of Southern California
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 two demonstrations of such a speedup, quantified in terms of the scaling of time-to-solution with problem size. The first 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 QPUs. The second demonstration, using 127-qubit IBM QPUs, is based on the restricted Hamming weight Simon’s problem, which likewise efficiently solves the problem of identifying a hidden bitstring encoded into an unknown periodic function. The speedups are 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 quantum supremacy demonstrations, the quantum speedup reported here does not rely on complexity-theoretic conjectures. Time permitting, I will report on the first demonstrated speedup in quantum optimization using D-Wave's quantum annealers, where custom quantum error-detecting codes prove essential for maintaining the quantum advantage.

References:
PRL 130, 210602 (2023)
arXiv:2401.07934
arXiv:2401.07184