Quantum advantage for computations with limited space

Quantum computations have the potential to solve classically intractable problems. In this work, we theoretically prove and experimentally verify a new type of quantum advantage, where computational space is treated as a limited resource. We show that when the computational space is restricted to a single (qu)bit, in theory, a quantum computer outperforms the best classical computer over arbitrary number of input bits greater or equal than 3, and validate the advantage using 3-, 4-, 5-, and 6-input Boolean functions. We implement these experiments over a subset of qubits on ibmq_berlin, a 27-qubit quantum processor, and calibrate custom 2-qubit gates to execute the circuits efficiently. In each case, we demonstrate the algorithmic success probability (ASP) of our quantum computation in excess of the best possible classical ASP, confirming that our quantum experiment reaches beyond the classical means.

[1] arXiv:2008.06478