Quantum advantage for computations with limited space

Abstract

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.

12 pages, 6 figures; improved theory and experiments

References in corpus (6)

• Robust randomized benchmarking of quantum processes
• Qiskit Pulse: Programming Quantum Computers Through the Cloud with Pulses
• Reducing unitary and spectator errors in cross resonance with optimized rotary echoes
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
• Experimental implementation of non-Clifford interleaved randomized benchmarking with a controlled-S gate
• Efficient ancilla-free reversible and quantum circuits for the Hidden Weighted Bit function

Cited by in corpus (17)

• Scalable mitigation of measurement errors on quantum computers
• Demonstration of algorithmic quantum speedup
• Work extraction from unknown quantum sources
• Quantum Neural Network Classifiers: A Tutorial
• Single-qubit universal classifier implemented on an ion-trap quantum device
• Adaptive variational simulation for open quantum systems
• Modeling low- and high-frequency noise in transmon qubits with resource-efficient measurement
• Quantum verification of NP problems with single photons and linear optics
• Modeling Short-Range Microwave Networks to Scale Superconducting Quantum Computation
• A quantum computing concept for 1-D elastic wave simulation with exponential speedup
• Benchmarking Quantum Computers: Towards a Standard Performance Evaluation Approach
• Estimating Gibbs partition function with quantumClifford sampling
• Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem
• Connecting XOR and XOR* games
• Dynamics of single-mode nonclassicalities and quantum correlations in the Jaynes-Cummings model
• Quantum advantage in temporally flat measurement-based quantum computation
• Demonstration of sequential processors with quantum advantage and analysis of classical performance limits