About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Nature Physics
Paper
Proving the advantage of quantum scratch space over classical scratch space
Abstract
Quantum computers promise the ability to solve problems that are intractable in the classical setting, 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 power. In multiple cases, quantum advantage over these restricted models was demonstrated experimentally. 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 processing and O(n2) gates, but in the analogous classical computations some of the functions may only be evaluated with probability 1/2+𝑂(𝑛/2‾√𝑛). 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.