Quantum advantage for computations with limited space

QuICS Seminar

Speaker: 
Sergey Bravyi (IBM)
Time: 
Wednesday, November 18, 2020 - 11:00am
Location: 
Virtual Via Zoom

Quantum computations promise the ability to solve problems intractable in the classical setting. Restricting the types of computations considered often allows to establish a provable theoretical quantum advantage, and later demonstrate it experimentally.  I will discuss space-restricted computations, where input is a read-only memory and only one (qu)bit can be computed on. We show that any n-bit symmetric Boolean function can be implemented exactly through the use of quantum signal processing as a space-restricted quantum computation using O(n^2) gates. Meanwhile, the analogously defined classical computation may only evaluate certain n-bit symmetric Boolean functions on a fraction of inputs approaching 50% for large n, no matter how long is the computation.  We experimentally demonstrate computations of few-bit symmetric Boolean functions by quantum circuits, leveraging custom two-qubit gates, with algorithmic success probability exceeding the best possible classically.

This is a joint work with Dmitri Maslov, Jin-Sung Kim, Ted Yoder, and Sarah Sheldon.  Preprint: arXiv:2008.06478