Fetching the paper…
Reading the bibliography…
Quantum computational supremacy arguments, which describe a way for a quantum computer to perform a task that cannot also be done by a classical computer, typically require some sort of computational assumption related to the limitations of classical computation.
Additive-error fine-grained quantum supremacy
T. Morimae and S. Tamaki · 1912
Earlier work this paper cites.
Combinatorial mathematics , volume 14
H. J. Ryser · 1963
Earlier work this paper cites.
The complexity of computing the permanent
L. Valiant · 1979
Earlier work this paper cites.
Some exact complexity results for straight-line computations over semirings
M. Jerrum and M. Snir · 1982
Earlier work this paper cites.
The complexity of approximate counting
L. Stockmeyer · 1983
Earlier work this paper cites.
New directions in testing
R. J. Lipton · 1989
Earlier work this paper cites.
𝖯𝖯 \mathsf{PP} is as hard as the polynomial-time hierarchy
S. Toda · 1991
Earlier work this paper cites.
Counting classes are at least as hard as the polynomial-time hierarchy
S. Toda and M. Ogiwara · 1992
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.
Threshold computation and cryptographic security
Y. Han, L. A. Hemaspaandra, and T. Thierauf · 1997
Earlier work this paper cites.
Unsatisfiable systems of equations, over a finite field
A. R. Woods · 1998
Earlier work this paper cites.
Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy
S. Fenner, F. Green, S. Homer, and R. Pruim · 1999
Earlier work this paper cites.
A lower bound for DLL algorithms for k k -SAT (preliminary version)
P. Pudlák and R. Impagliazzo · 2000
Earlier work this paper cites.
Which problems have strongly exponential complexity?
R. Impagliazzo, R. Paturi, and F. Zane · 2001
Earlier work this paper cites.
𝖰𝖬𝖠 {\mathsf{QMA}} = = 𝖯𝖯 {\mathsf{PP}} implies that 𝖯𝖯 {\mathsf{PP}} contains 𝖯𝖧 {\mathsf{PH}}
M. Vyalyi · 2003
Earlier work this paper cites.
Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games
B. M. Terhal and D. P. DiVincenzo · 2004
Earlier work this paper cites.
Quantum computing, postselection, and probabilistic polynomial-time
S. Aaronson · 2005
Earlier work this paper cites.
A new algorithm for optimal 2-constraint satisfaction and its implications
R. Williams · 2005
Earlier work this paper cites.
Error-bounded probabilistic computations between 𝖬𝖠 \mathsf{MA} and 𝖠𝖬 \mathsf{AM}
E. Böhler, C. Glaßer, and D. Meister · 2006
Earlier work this paper cites.
Temporally unstructured quantum computation
D. Shepherd and M. J. Bremner · 2008
Earlier work this paper cites.
Computational complexity: a modern approach
S. Arora and B. Barak · 2009
Earlier work this paper cites.
The complexity of satisfiability of small depth circuits
C. Calabro, R. Impagliazzo, and R. Paturi · 2009
Earlier work this paper cites.
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
M. J. Bremner, R. Jozsa, and D. J. Shepherd · 2010
Cited alongside, same era.
A linear-optical proof that the permanent is # 𝖯 \#{\mathsf{P}} -hard
S. Aaronson · 2011
Cited alongside, same era.
The computational complexity of linear optics
S. Aaronson and A. Arkhipov · 2011
Cited alongside, same era.
Quantum computing and the entanglement frontier
J. Preskill · 2012
Cited alongside, same era.
Strong ETH holds for regular resolution
C. Beck and R. Impagliazzo · 2013
Cited alongside, same era.
Exponential time complexity of the permanent and the Tutte polynomial
H. Dell, T. Husfeldt, D. Marx, N. Taslaman, and M. Wahlén · 2014
Lower bounds on the classical simulation of quantum circuits for quantum supremacy
A. M. Dalzell · 2017
Later among the works it cites.
Quantum computational supremacy
A. W. Harrow and A. Montanaro · 2017
Later among the works it cites.
Further extensions of Clifford circuits and their classical simulation complexities
D. E. Koh · 2017
Later among the works it cites.
Beating brute force for systems of polynomial equations over finite fields
D. Lokshtanov, R. Paturi, S. Tamaki, R. Williams, and H. Yu · 2017
Later among the works it cites.
Quantum circuits and low-degree polynomials over 𝔽 2 \mathbb{F}_{2}
A. Montanaro · 2017
Later among the works it cites.
Classical boson sampling algorithms with superior performance to near-term experiments
A. Neville, C. Sparrow, R. Clifford, E. Johnston, P. M. Birchall, A. Montanaro, and A. Laing · 2017
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
A quantum approximate optimization algorithm
E. Farhi, J. Goldstone, and S. Gutmann · 2014
Cited alongside, same era.
Classical simulation complexity of extended Clifford circuits
R. Jozsa and M. Van Den Nest · 2014
Cited alongside, same era.
Hardness of classically simulating the one-clean-qubit model
T. Morimae, K. Fujii, and J. F. Fitzsimons · 2014
Cited alongside, same era.
Finding orthogonal vectors in discrete structures
R. Williams and H. Yu · 2014
Cited alongside, same era.
Local reductions
H. Jahanjou, E. Miles, and E. Viola · 2015
Cited alongside, same era.
How hard is it to approximate the Jones polynomial?
G. Kuperberg · 2015
Cited alongside, same era.
Later among the works it cites.
Quantum resource estimates for computing elliptic curve discrete logarithms
M. Roetteler, M. Naehrig, K. M. Svore, and K. Lauter · 2017
Later among the works it cites.
Architectures for quantum simulation showing a quantum speedup
J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert · 2018
Closest in time.
Complexity classification of conjugated Clifford circuits
A. Bouland, J. F. Fitzsimons, and D. E. Koh · 2018
Closest in time.
The classical complexity of boson sampling
P. Clifford and R. Clifford · 2018
Closest in time.
Impossibility of classically simulating one-clean-qubit model with multiplicative error
K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Tamate, and S. Tani · 2018
Closest in time.
Anticoncentration theorems for schemes showing a quantum speedup
D. Hangleiter, J. Bermejo-Vega, M. Schwarz, and J. Eisert · 2018
Closest in time.
Explicit lower bounds on strong quantum simulation
C. Huang, M. Newman, and M. Szegedy · 2018
Closest in time.
Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
T. Morimae, Y. Takeuchi, and H. Nishimura · 2018
Closest in time.
R. Movassagh · 2018
Closest in time.
Quantum supremacy using a programmable superconducting processor
F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, et al · 2019
Closest in time.
Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
A. Björklund, P. Kaski, and R. Williams · 2019
Closest in time.
On the complexity and verification of quantum random circuit sampling
A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani · 2019
Closest in time.
Fine-grained quantum supremacy based on orthogonal vectors, 3-sum and all-pairs shortest paths
R. Hayakawa, T. Morimae, and S. Tamaki · 2019
Closest in time.
R. Movassagh · 2019
Closest in time.
Worst-case to average-case reductions for subclasses of 𝖯 {\mathsf{P}}
O. Goldreich and G. N. Rothblum · 2020
Closest in time.