Simulating quantum computation: how many "bits" for "it"?
arXiv:2305.17287 · doi:10.1103/PRXQuantum.5.030343
Abstract
A recently introduced classical simulation method for universal quantum computation with magic states operates by repeated sampling from probability functions [M. Zurel et al. PRL 260404 (2020)]. This method is closely related to sampling algorithms based on Wigner functions, with the important distinction that Wigner functions can take negative values obstructing the sampling. Indeed, negativity in Wigner functions has been identified as a precondition for a quantum speed-up. However, in the present method of classical simulation, negativity of quasiprobability functions never arises. This model remains probabilistic for all quantum computations. In this paper, we analyze the amount of classical data that the simulation procedure must track. We find that this amount is small. Specifically, for any number of magic states, the number of bits that describe the quantum system at any given time is .
arXiv comment9 pages, 3 figures
References in corpus (16)
- Improved Simulation of Stabilizer Circuits
- Universal Quantum Computation with ideal Clifford gates and noisy ancillas
- Roads towards fault-tolerant universal quantum computation
- Negative Quasi-Probability as a Resource for Quantum Computation
- Hudson's Theorem for finite-dimensional quantum systems
- Trading classical and quantum computational resources
- Quantum Supremacy and the Complexity of Random Circuit Sampling
- Instantaneous Quantum Computation
- Wigner function negativity and contextuality in quantum computation on rebits
- Discrete Wigner functions and quantum computational speedup
- Phase space simulation method for quantum computation with magic states on qubits
- A hidden variable model for universal quantum computation with magic states on qubits
- Quantum circuit compilation and hybrid computation using Pauli-based computation
- Pauli-based model of quantum computation with higher-dimensional systems
- Counting stabiliser codes for arbitrary dimension
- Hidden variable model for quantum computation with magic states on qudits of any dimension