From estimation of quantum probabilities to simulation of quantum circuits

Abstract

Investigating the classical simulability of quantum circuits provides a promising avenue towards understanding the computational power of quantum systems. Whether a class of quantum circuits can be efficiently simulated with a probabilistic classical computer, or is provably hard to simulate, depends quite critically on the precise notion of "classical simulation" and in particular on the required accuracy. We argue that a notion of classical simulation, which we call epsilon-simulation, captures the essence of possessing "equivalent computational power" as the quantum system it simulates: It is statistically impossible to distinguish an agent with access to an epsilon-simulator from one possessing the simulated quantum system. We relate epsilon-simulation to various alternative notions of simulation predominantly focusing on a simulator we call a poly-box. A poly-box outputs 1/poly precision additive estimates of Born probabilities and marginals. This notion of simulation has gained prominence through a number of recent simulability results. Accepting some plausible computational theoretic assumptions, we show that epsilon-simulation is strictly stronger than a poly-box by showing that IQP circuits and unconditioned magic-state injected Clifford circuits are both hard to epsilon-simulate and yet admit a poly-box. In contrast, we also show that these two notions are equivalent under an additional assumption on the sparsity of the output distribution (poly-sparsity).

29 pages + appendix, 3 figures, comments welcome; v2 various improvements; v3 final version accepted to Quantum

References in corpus (9)

• Application of a resource theory for magic states to fault-tolerant quantum computing
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Matchgates and classical simulation of quantum circuits
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Efficient simulation scheme for a class of quantum optics experiments with non-negative Wigner representation
• Classical simulation of photonic linear optics with lost particles
• Binary Matroids and Quantum Probability Distributions
• Complexity Classification of Conjugated Clifford Circuits
• Quantum Complexity: restrictions on algorithms and architectures

Cited by in corpus (31)

• Simulating Large Quantum Circuits on a Small Quantum Computer
• Mitigation of readout noise in near-term quantum devices by classical post-processing based on detector tomography
• Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Quantifying magic for multi-qubit operations
• Phase space simulation method for quantum computation with magic states on qubits
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Classical simulation of Gaussian quantum circuits with non-Gaussian input states
• Fast estimation of outcome probabilities for quantum circuits
• Quantum machine learning with adaptive linear optics
• Dequantizing quantum machine learning models using tensor networks
• Improved simulation of quantum circuits dominated by free fermionic operations
• Protocols for classically training quantum generative models on probability distributions
• Classical simulation of non-Gaussian bosonic circuits
• Classical simulation of boson sampling with sparse output
• Faster Born probability estimation via gate merging and frame optimisation
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Quantum advantage from energy measurements of many-body quantum systems
• Possibilistic simulation of quantum circuits by classical circuits
• Approximating outcome probabilities of linear optical circuits
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• Gleipnir: Toward Practical Error Analysis for Quantum Programs (Extended Version)
• Wigner's Theorem for stabilizer states and quantum designs
• Continuous Variable Quantum Advantages and Applications in Quantum Optics
• Improved Strong Simulation of Universal Quantum Circuits
• Clifford-Dressed Variational Principles for Precise Loschmidt Echoes
• Simulating Electron Transfer on Noisy Quantum Computers
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
• The symplectic rank of non-Gaussian quantum states
• Classical algorithms for measurement-adaptive Gaussian circuits
• Efficient classical simulation of cluster state quantum circuits with alternative inputs