Simulating Quantum Circuits with Sparse Output Distributions
arXiv:1310.6749
Abstract
We show that several quantum circuit families can be simulated efficiently classically if it is promised that their output distribution is approximately sparse i.e. the distribution is close to one where only a polynomially small, a priori unknown subset of the measurement probabilities are nonzero. Classical simulations are thereby obtained for quantum circuits which---without the additional sparsity promise---are considered hard to simulate. Our results apply in particular to a family of Fourier sampling circuits (which have structural similarities to Shor's factoring algorithm) but also to several other circuit families, such as IQP circuits. Our results provide examples of quantum circuits that cannot achieve exponential speed-ups due to the presence of too much destructive interference i.e. too many cancelations of amplitudes. The crux of our classical simulation is an efficient algorithm for approximating the significant Fourier coefficients of a class of states called computationally tractable states. The latter result may have applications beyond the scope of this work. In the proof we employ and extend sparse approximation techniques, in particular the Kushilevitz-Mansour algorithm, in combination with probabilistic simulation methods for quantum circuits.
arXiv comment21 pages, 1 figure
References in corpus (8)
- Instantaneous Quantum Computation
- Efficient classical simulation of the semi-classical Quantum Fourier Transform
- Efficient classical simulation of the approximate quantum Fourier transform
- Quantum boolean functions
- Quantum interference as a resource for quantum speedup
- The quantum FFT can be classically simulated
- Nearly Optimal Sparse Fourier Transform
- Classical simulations of Abelian-group normalizer circuits with intermediate measurements
Cited by in corpus (6)
- Achieving quantum supremacy with sparse and noisy commuting quantum computations
- Efficient Quantum Walk on a Quantum Processor
- From estimation of quantum probabilities to simulation of quantum circuits
- Quantum computing for chemistry and physics applications from a Monte Carlo perspective
- Approximating outcome probabilities of linear optical circuits
- Sampling and the complexity of nature