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