2020/08/31 by Dmitri Maslov, Jin-Sung Kim, Sergey Bravyi +2 · 2 citations
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #Computation #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum algorithm #Quantum capacity #Quantum computer #Quantum error correction #Quantum information #Quantum process #Quantum sort #cs.ET #quant-ph
paper · pdf · doi:10.1038/s41567-021-01271-7
published as Nature Physics 17, 894-897 (2021) · 12 pages, 6 figures; improved theory and experiments
openalex created_date 2020/08/21 · arxiv created 2020/12/18 · crossref issued 2021/06/28 · crossref published 2021/06/28 · crossref published-online 2021/06/28 · openalex publication_date 2021/06/28 · crossref created 2021/06/28 · crossref published-print 2021/08/01 · arxiv updated 2021/11/19 · crossref deposited 2023/01/01 · crossref indexed 2026/02/21 · openalex updated_date 2026/08/05
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(n2) gates, but some of them may only be evaluated with probability 1/2 + O(n/√(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.