RECORD
Simulating Quantum Circuits with Sparse Output Distributions
Quantum Physics · Submitted 24 Oct 2013
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | result 0.76 | 0.92 | 0.91 | asserted 1.00 |
| s1 | Classical simulations are thereby obtained for quantum circuits which---without the additional sparsity promise---are considered hard to simulate. | result 0.49 | 0.84 | 0.28 | asserted 1.00 |
| s2 | 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. | result 0.73 | 0.83 | 0.10 | asserted 1.00 |
| s3 | 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. | interpretation 0.92 | 0.84 | 0.15 | asserted 0.99 |
| s4 | 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. | method 0.92 | 0.90 | 0.13 | asserted 1.00 |
| s5 | The latter result may have applications beyond the scope of this work. | interpretation 0.50 | 0.35 | 0.02 | hedged possibility 1.00 |
| s6 | 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. | method 1.00 | 0.80 | 0.03 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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.
Human review
References
How the literature uses it
24 arXiv papers cite this in 46 sentences
Papers citing it · 25 sentences without a confident label
Builds on it 1 paper
-
Thus, it proves that any boson sampling can be classically simulated if the output probability distribution is polynomially sparse [ref] , extending previous results that applied only to restricted cases [ref] .
Classical algorithms for estimating expectation values in linear-optical circuits · Introduction · 0.98
Uses its method or tool 2 papers
-
Using the method in Theorem 10 in Ref. [ref] , the quantum server can efficiently obtain the list $ℒ'$ with $|ℒ'|≤⌊2t/ϵ⌋$ such that with probability at least $1-ϵδ/(2t+ϵ)$, every $n$-bit string $z$ satisfying $q_z≥ϵ/t$ belongs to the list $ℒ'$.
Sumcheck-based delegation of quantum computing to rational server · Estimating output probabilities of approximately sparse quantum circuits with a polynomial number of output qubits · 1.00
-
For the IQP model, $f(x,y)$ is a complex-valued function, but we can use the Chernoff-Hoeffding bound for complex random variables introduced in Ref. [ref] .
Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy · Generalizations to other circuits · 1.00
Compares with it 4 papers
-
The list in Ref. [ref] satisfies the property such that for all elements $z$ in the list, $q_z≥ϵ/(2t)$ holds, while this property is not required for our list.
Sumcheck-based delegation of quantum computing to rational server · Estimating output probabilities of approximately sparse quantum circuits with a polynomial number of output qubits · 0.97
-
However, in [ref] it was sufficient to show that, given a probability distribution $p$ with at most $(n)$ nonzero probabilities, each determined up to additive error $O(1/(n))$, we can approximately sample from $p$.
Achieving quantum supremacy with sparse and noisy commuting quantum computations · Sampling from an approximate probability distribution · 0.92
-
A key difference to our work is that their runtime scales polynomially in the sparsity and Frobenius norm of the Hamiltonian, whereas our runtime is independent of the Frobenius norm (and thus of the rank).] [ref] , we consider two ways to access vectors and matrices.
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture · Main results · 0.92
Cites it as background 6 papers
-
In Ref. [ref] , they define the following property of discrete probability distributions:
From estimation of quantum probabilities to simulation of quantum circuits · Sparsity and sampling · 0.85
-
The efficient classical simulatability of approximately sparse quantum circuits was explored in Ref. [ref] .
Sumcheck-based delegation of quantum computing to rational server · Estimating output probabilities of approximately sparse quantum circuits with a polynomial number of output qubits · 0.97
-
Despite the computational limitations of classical simulation, surprisingly powerful classical simulators have since been discovered including simulators of stabilizer circuits [ref] , fermionic linear optics/matchgates [ref] and others [ref] .
Quantifying quantum speedups: improved classical simulation from tighter magic monotones · Introduction · 0.82
What it cites · 3 sentences without a confident label
Cites as background 2 papers
-
In the latter context, see also [ref] for classical simulations of a class of circuits involving QFTs over finite abelian groups supplemented with a particular family of group-theoretic operations (Normalizer circuits).
Efficient classical simulations of quantum Fourier transforms and normalizer circuits over Abelian groups · Introduction · 0.95
-
In the latter context, see also [ref] for classical simulations of a class of circuits involving QFTs over finite abelian groups supplemented with a particular family of group-theoretic operations (Normalizer circuits).
Classical simulations of Abelian-group normalizer circuits with intermediate measurements · Introduction · 0.95
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.