Sublinear Algorithms and Quantum Computing

Zoom link for remote attendees

Meeting ID: 999 4631 3276 Passcode: 123123

Abstract: Quantum computers have been the subject of extensive research and investment due to their potential to dramatically outperform classical computers for certain tasks. However, despite exciting technical progress in recent years, the resources needed for quantum computing will be very expensive for the foreseeable future: qubits are far more expensive than their classical counterparts, while quantum processes and devices are much more challenging to characterize and test.

I will discuss my work on addressing these challenges with tools from the domain of sublinear algorithms, algorithms that use very little of some resource relative to the size of the input they process. This includes the first known examples of quantum advantage for natural problems in the streaming model, a core model for big data analytics.

Bio: John is a Senior Member of Technical Staff at Sandia National Laboratories in Albuquerque, New Mexico, where he works on problems in quantum algorithms. He earned his PhD in Computer Science from the University of Texas at Austin, advised by Eric Price.