Fetching the paper…
Reading the bibliography…
We give new evidence that quantum computers -- moreover, rudimentary quantum computers built entirely out of linear-optical elements -- cannot be efficiently simulated by classical computers.
On quantum field theory, 1: explicit solution of Dyson’s equation in electrodynamics without use of Feynman graphs
E. R. Caianiello · 1953
Earlier work this paper cites.
The complexity of computing the permanent
L. G. Valiant · 1979
Earlier work this paper cites.
Proof of the van der Waerden conjecture for permanents
G. P. Egorychev · 1981
Earlier work this paper cites.
Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
D. I. Falikman · 1981
Earlier work this paper cites.
On the matching polynomial of a graph
C. D. Godsil and I. Gutman · 1981
Earlier work this paper cites.
Simulating physics with computers
R. P. Feynman · 1982
Earlier work this paper cites.
The complexity of approximate counting
L. J. Stockmeyer · 1983
Earlier work this paper cites.
Measurement of subpicosecond time intervals between two photons by interference
C. K. Hong, Z. Y. Ou, and L. Mandel · 1987
Earlier work this paper cites.
Computational Limitations for Small Depth Circuits
J. Håstad · 1987
Earlier work this paper cites.
Self-testing/correcting for polynomials and for approximate functions
P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson · 1991
Earlier work this paper cites.
New directions in testing
R. J. Lipton · 1991
Earlier work this paper cites.
PP is as hard as the polynomial-time hierarchy
S. Toda · 1991
Earlier work this paper cites.
Highly resilient correctors for polynomials
P. Gemmell and M. Sudan · 1992
Earlier work this paper cites.
On the degree of polynomials that approximate symmetric Boolean functions
R. Paturi · 1992
Earlier work this paper cites.
Quantum complexity theory
E. Bernstein and U. Vazirani · 1993
Earlier work this paper cites.
Experimental realization of any discrete unitary operator
M. Reck, A. Zeilinger, H. J. Bernstein, and P. Bertani · 1994
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
P. W. Shor · 1994
Earlier work this paper cites.
On the power of quantum computation
D. Simon · 1994
Earlier work this paper cites.
Maximum likelihood decoding of Reed-Solomon codes
M. Sudan · 1996
Earlier work this paper cites.
Permanent uncertainty: On the quantum evaluation of the determinant and the permanent of a matrix
L. Troyansky and N. Tishby · 1996
Earlier work this paper cites.
Simulation of many-body Fermi systems on a universal quantum computer
D. S. Abrams and S. Lloyd · 1997
Earlier work this paper cites.
Fault-tolerant quantum computation with constant error
D. Aharonov and M. Ben-Or · 1997
Cited alongside, same era.
Threshold computation and cryptographic security
Y. Han, L. Hemaspaandra, and T. Thierauf · 1997
Cited alongside, same era.
A refinement of the Central Limit Theorem for random determinants
V. L. Girko · 1998
Cited alongside, same era.
Power of one bit of quantum information
E. Knill and R. Laflamme · 1998
Cited alongside, same era.
Resilient quantum computation
E. Knill, R. Laflamme, and W. Zurek · 1998
Cited alongside, same era.
Bounds for small-error and zero-error quantum algorithms
H. Buhrman, R. Cleve, R. de Wolf, and Ch. Zalka · 1999
Cited alongside, same era.
On the hardness of permanent
On asymptotics of large Haar distributed unitary matrices
D. Petz and J. Réffy · 2004
Later among the works it cites.
Permanents in linear optical networks
S. Scheel · 2004
Later among the works it cites.
Adaptive quantum computation, constant-depth circuits and Arthur-Merlin games
B. M. Terhal and D. P. DiVincenzo · 2004
Later among the works it cites.
Quantum computing, postselection, and probabilistic polynomial-time
S. Aaronson · 2005
Later among the works it cites.
On the complexity of mixed discriminants and related problems
L. Gurvits · 2005
Later among the works it cites.
Generalized Hong-Ou-Mandel experiments with bosons and fermions
Y. L. Lim and A. Beige · 2005
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
J.-Y. Cai, A. Pavan, and D. Sivakumar · 1999
Cited alongside, same era.
Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy
S. Fenner, F. Green, S. Homer, and R. Pruim · 1999
Cited alongside, same era.
Fast parallel circuits for the quantum Fourier transform
R. Cleve and J. Watrous · 2000
Cited alongside, same era.
Quantum Computation and Quantum Information
M. Nielsen and I. Chuang · 2000
Cited alongside, same era.
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
M. Jerrum, A. Sinclair, and E. Vigoda · 2001
Cited alongside, same era.
Fermionic linear optics and matchgates
E. Knill · 2001
Cited alongside, same era.
Single-photon sources
B. Lounis and M. Orrit · 2005
Later among the works it cites.
Large deviation theorem for empirical eigenvalue distribution of truncated Haar unitary matrices
D. Petz and J. Réffy · 2005
Later among the works it cites.
Asymptotics of random unitaries
J. Réffy · 2005
Later among the works it cites.
The complexity of computing a Nash equilibrium
C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou · 2006
Later among the works it cites.
Elementary proof for asymptotics of large Haar-distributed unitary matrices
C. Mastrodonato and R. Tumulka · 2007
Later among the works it cites.
A simple encoding of a quantum circuit amplitude as a matrix permanent
T. Rudolph · 2009
Later among the works it cites.
Temporally unstructured quantum computation
D. Shepherd and M. J. Bremner · 2009
Later among the works it cites.
On the permanent of random Bernoulli matrices
T. Tao and V. Vu · 2009
Later among the works it cites.
BQP and the polynomial hierarchy
S. Aaronson · 2010
Closest in time.
The equivalence of sampling and searching
S. Aaronson · 2010
Closest in time.
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
M. Bremner, R. Jozsa, and D. Shepherd · 2010
Closest in time.
An overview of quantum Monte Carlo methods
D. M. Ceperley · 2010
Closest in time.
Pseudorandom generators and the BQP vs. PH problem
B. Fefferman and C. Umans · 2010
Closest in time.
Permutational quantum computing
S. P. Jordan · 2010
Closest in time.
On the Unique Games Conjecture
S. Khot · 2010
Closest in time.