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
