Quantum advantage for computations with limited space

Abstract

Quantum computers promise the ability to solve problems that are intractable in the classical setting1, but in many cases this is not rigorously proven. It is often possible to establish a provable theoretical advantage for quantum computations by restricting the computational power2–8. In multiple cases, quantum advantage over these restricted models was demonstrated experimentally9–12. Here we consider space-restricted computations that use only one computational classical or quantum bit with a read-only memory as input. We show that n-bit symmetric Boolean functions can be implemented exactly in this framework through the use of quantum signal processing13 and O(n2) gates, but in the analogous classical computations some of the functions may only be evaluated with probability 1/2+On/2n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/2 + O\left(n/{\sqrt{2}}^n\right)$$\end{document}. We experimentally demonstrate computations of three-bit to six-bit symmetric Boolean functions by quantum circuits with an algorithmic success probability that exceeds the classical limit. This shows that in computations, quantum scrap space offers an advantage over analogous classical space, and calls for an in-depth exploration of space–time trade-offs in quantum circuits. In general, it isn’t known when a quantum computer will have an advantage over a classical device. Now it’s proven that computers with limited working memory are more powerful if they are quantum.