QIP 2021

Quantum advantage for computations with limited space

Watch video


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 advantage by quantum computations, and later demonstrate it experimentally. In this paper, we consider space-restricted computations, where input is a read-only memory and only one (qu)bit can be computed on. We show that n-bit symmetric Boolean functions can be implemented exactly through the use of quantum signal processing as restricted space quantum computations using O(n^2) gates, but some of them may only be evaluated with probability 1/2+O(n/sqrt{2}^n) by analogously defined classical computations. We experimentally demonstrate computations of 3-, 4-, 5-, and 6-bit symmetric Boolean functions by quantum circuits, leveraging custom two-qubit gates, with algorithmic success probability exceeding the best possible classically. This establishes and experimentally verifies a different kind of quantum advantage---one where quantum scrap space is more valuable than analogous classical space---and calls for an in-depth exploration of space-time tradeoffs in quantum circuits.


01 Feb 2021


QIP 2021