BARC Talk by John Kallaugher: Sublinear Algorithms and Quantum Computing

Title

Sublinear Algorithms and Quantum Computing

Abstract

While quantum devices are expected to be exponentially faster than classical ones for some applications, the resources they use are also inherently more costly. Even under the most optimistic estimates, the cost of implementing a qubit is many orders of magnitude more than a classical bit. Understanding quantum states and processes is also more difficult than their classical counterparts—fully characterizing a quantum state requires, in general, exponentially many copies thereof, while understanding an unknown quantum process involves considering much larger families of errors than for classical ones.

I will talk about addressing these problems with ideas from the classical field of sublinear algorithms: algorithms designed to use very little of some resource relative to the size of the inputs they handle.