Fetching the paper…
Reading the bibliography…
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.
Random generation of combinatorial structures from a uniform distribution
Mark R Jerrum, Leslie G Valiant, and Vijay V Vazirani · 1986
Earlier work this paper cites.
A hard-core predicate for all one-way functions
O. Goldreich and LA Levin · 1989
Earlier work this paper cites.
Learning decision trees using the Fourier spectrum
E. Kushilevitz and Y. Mansour · 1991
Earlier work this paper cites.
Randomized interpolation and approximation of sparse polynomials
Y. Mansour · 1995
Earlier work this paper cites.
Fault-tolerant quantum computation with higher-dimensional systems
Daniel Gottesman · 1999
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
P.W. Shor · 1999
Earlier work this paper cites.
Near-optimal sparse fourier representations via sampling
A.C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, and M. Strauss · 2002
Earlier work this paper cites.
Quantum circuits that can be simulated classically in polynomial time
Leslie G Valiant · 2002
Earlier work this paper cites.
Proving hard-core predicates using list decoding
A. Akavia, S. Goldwasser, and S. Safra · 2003
Earlier work this paper cites.
The hidden subgroup problem-review and open problems
Chris Lomont · 2004
Earlier work this paper cites.
Adptive quantum computation, constant depth quantum circuits and arthur-merlin games
Barbara M Terhal and David P DiVincenzo · 2004
Earlier work this paper cites.
Number-theoretical turbulence in fermat–euler arithmetics and large young diagrams geometry statistics
V Arnold · 2005
Earlier work this paper cites.
Approximate counting and quantum computation
M Bordewich, M Freedman, L Lovász, and D Welsh · 2005
Cited alongside, same era.
Improved time bounds for near-optimal sparse fourier representations
A. Gilbert, S. Muthukrishnan, and M. Strauss · 2005
Cited alongside, same era.
On basing one-way functions on NP-hardness
A. Akavia, O. Goldreich, S. Goldwasser, and D. Moshkovitz · 2006
Cited alongside, same era.
The quantum fft can be classically simulated
D. Aharonov, Z. Landau, and J. Makowsky · 2006
Cited alongside, same era.
Generic quantum fourier transforms
Cristopher Moore, Daniel Rockmore, and Alexander Russell · 2006
Cited alongside, same era.
Quantum algorithms for simon’s problem over general groups
Gorjan Alagic, Cristopher Moore, and Alexander Russell · 2007
Cited alongside, same era.
Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond
Maarten Van den Nest · 2010
Later among the works it cites.
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
Michael J Bremner, Richard Jozsa, and Dan J Shepherd · 2011
Later among the works it cites.
Classical simulations of non-abelian quantum fourier transforms
Juan Bermejo-Vega · 2011
Later among the works it cites.
Lower bounds on the period in integer factorization?
Peter Shor · 2011
Later among the works it cites.
Simulating quantum computers with probabilistic methods
Maarten Van den Nest · 2011
Later among the works it cites.
Classical simulations of Abelian-group normalizer circuits with intermediate measurements
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Efficient classical simulation of the quantum fourier transform
Daniel E Browne · 2007
Cited alongside, same era.
Efficient classical simulation of the approximate quantum fourier transform
Nadav Yoran and Anthony J. Short · 2007
Cited alongside, same era.
Temporally unstructured quantum computation
Dan Shepherd and Michael J Bremner · 2009
Cited alongside, same era.
Deterministic sparse fourier approximation via fooling arithmetic progressions
A. Akavia · 2010
Cited alongside, same era.
Combinatorial sublinear-time fourier algorithms
MA Iwen · 2010
Cited alongside, same era.
Quantum boolean functions
Ashley Montanaro and Tobias J Osborne · 2010
Cited alongside, same era.
Juan Bermejo-Vega and Maarten Van den Nest · 2012
Later among the works it cites.
Nearly optimal sparse fourier transform
H. Hassanieh, P. Indyk, D. Katabi, and E. Price · 2012
Later among the works it cites.
Simple and practical algorithm for sparse fourier transform
H. Hassanieh, P. Indyk, D. Katabi, and E. Price · 2012
Later among the works it cites.
Maarten Van den Nest · 2012
Later among the works it cites.
Exponential Quantum Speed-ups are Generic
Fernando G.S.L. Brandao and Michal Horodecki · 2013
Closest in time.
On a problem of Arnold: The average multiplicative order of a given integer
Pär Kurlberg and Carl Pomerance · 2013
Closest in time.
Quantum interference as a resource for quantum speedup
Dan Stahlke · 2013
Closest in time.