Fetching the paper…
Reading the bibliography…
In the near future, there will likely be special-purpose quantum computers with 40-50 high-quality qubits.
Relationships between nondeterministic and deterministic tape complexities
W. J. Savitch · 1970
Earlier work this paper cites.
Relativizations of the P=?NP question
Theodore Baker, John Gill, and Robert Solovay · 1975
Earlier work this paper cites.
How to construct random functions
O. Goldreich, S. Goldwasser, and S. Micali · 1984
Earlier work this paper cites.
Separating the polynomial-time hierarchy by oracles
Andrew Chi-Chih Yao · 1985
Earlier work this paper cites.
Almost optimal lower bounds for small depth circuits
Johan Hastad · 1986
Earlier work this paper cites.
How to construct pseudorandom permutations from pseudorandom functions
Michael Luby and Charles Rackoff · 1988
Earlier work this paper cites.
A hard-core predicate for all one-way functions
Oded Goldreich and Leonid A Levin · 1989
Earlier work this paper cites.
PP is as hard as the polynomial-time hierarchy
S. Toda · 1989
Earlier work this paper cites.
IP=PSPACE
A. Shamir · 1990
Earlier work this paper cites.
Quantum complexity theory
E. Bernstein and U. Vazirani · 1993
Earlier work this paper cites.
Hardness vs randomness
Noam Nisan and Avi Wigderson · 1994
Earlier work this paper cites.
Natural proofs
A. A. Razborov and S. Rudich · 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.
Quantum cryptanalysis of hidden linear functions
Dan Boneh and Richard J Lipton · 1995
Earlier work this paper cites.
Fault-tolerant quantum computation with constant error
D. Aharonov and M. Ben-Or · 1997
Earlier work this paper cites.
Strengths and weaknesses of quantum computing
C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani · 1997
Earlier work this paper cites.
P=BPP unless E has subexponential circuits: derandomizing the XOR Lemma
R. Impagliazzo and A. Wigderson · 1997
Earlier work this paper cites.
Statistical learning theory
Vladimir Naumovich Vapnik · 1998
Earlier work this paper cites.
Complexity limitations on quantum computation
L. Fortnow and J. Rogers · 1999
Earlier work this paper cites.
A pseudorandom generator from any one-way function
J. Håstad, R. Impagliazzo, L. A. Levin, and M. Luby · 1999
Earlier work this paper cites.
An oracle builder’s toolkit
Stephen Fenner, Lance Fortnow, Stuart A Kurtz, and Lide Li · 2003
Earlier work this paper cites.
The tale of one-way functions
Leonid A Levin · 2003
Cited alongside, same era.
A complete problem for statistical zero knowledge
Amit Sahai and Salil Vadhan · 2003
Cited alongside, same era.
Quantum lower bounds for the collision and the element distinctness problems
S. Aaronson and Y. Shi · 2004
Cited alongside, same era.
Equivalences and separations between quantum and classical learnability
Rocco A Servedio and Steven J Gortler · 2004
Cited alongside, same era.
Adaptive quantum computation, constant-depth circuits and Arthur-Merlin games
B. M. Terhal and D. P. DiVincenzo · 2004
Cited alongside, same era.
Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range
Andris Ambainis · 2005
Cited alongside, same era.
Hardness of classically simulating the one-clean-qubit model
Tomoyuki Morimae, Keisuke Fujii, and Joseph F Fitzsimons · 2014
Later among the works it cites.
Asymptopia
Joel Spencer · 2014
Later among the works it cites.
Forrelation: A problem that optimally separates quantum from classical computing
Scott Aaronson and Andris Ambainis · 2015
Later among the works it cites.
Google, D-wave, and the case of the factor-10ˆ8 speedup for WHAT?, 2015
S. Aaronson · 2015
Later among the works it cites.
Separations in query complexity using cheat sheets
Scott Aaronson, Shalev Ben-David, and Robin Kothari · 2015
Later among the works it cites.
Average-case complexity versus approximate simulation of commuting quantum computations
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Quantum lower bound for the collision problem with small range
Samuel Kutin · 2005
Cited alongside, same era.
Interactive proofs for quantum computations
D. Aharonov, M. Ben-Or, and E. Eban · 2008
Cited alongside, same era.
Algebrization: a new barrier in complexity theory
S. Aaronson and A. Wigderson · 2008
Cited alongside, same era.
Simulating quantum computation by contracting tensor networks
Igor L Markov and Yaoyun Shi · 2008
Cited alongside, same era.
Computational complexity: a modern approach
Sanjeev Arora and Boaz Barak · 2009
Cited alongside, same era.
Universal blind quantum computation
A. Broadbent, J. Fitzsimons, and E. Kashefi · 2009
Cited alongside, same era.
Michael J Bremner, Ashley Montanaro, and Dan J Shepherd · 2015
Later among the works it cites.
Universal linear optics
Jacques Carolan, Christopher Harrold, Chris Sparrow, Enrique Martín-López, Nicholas J Russell, Joshua W Silverstone, Peter J Shadbolt, Nobuyuki Matsuda, Manabu Oguma, Mikitaka Itoh, Graham D Marshall, Mark G Thompson, Jonathan C F Matthews, Toshikazu Hashimoto, Jeremy L O’Brien, and Anthony Laing · 2015
Later among the works it cites.
State preservation by repetitive error detection in a superconducting quantum circuit
J Kelly, R Barends, AG Fowler, A Megrant, E Jeffrey, TC White, D Sank, JY Mutus, B Campbell, Yu Chen, et al · 2015
Later among the works it cites.
Borja Peropadre, Gian Giacomo Guerreschi, Joonsuk Huh, and Alán Aspuru-Guzik · 2015
Later among the works it cites.
An average-case depth hierarchy theorem for boolean circuits
Benjamin Rossman, Rocco A Servedio, and Li-Yang Tan · 2015
Later among the works it cites.
The computational complexity of ball permutations
Scott Aaronson, Adam Bouland, Greg Kuperberg, and Saeed Mehraban · 2016
Closest in time.
Improved classical simulation of quantum circuits dominated by clifford gates
Sergey Bravyi and David Gosset · 2016
Closest in time.
Local random quantum circuits are approximate polynomial-designs
Fernando GSL Brandão, Aram W Harrow, and Michał Horodecki · 2016
Closest in time.
Characterizing quantum supremacy in near-term devices
Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, John M Martinis, and Hartmut Neven · 2016
Closest in time.
Achieving quantum supremacy with sparse and noisy commuting quantum computations
Michael J Bremner, Ashley Montanaro, and Dan J Shepherd · 2016
Closest in time.
A note on oracle separations for BQP
Lijie Chen · 2016
Closest in time.
Quantum supremacy through the quantum approximate optimization algorithm
Edward Farhi and Aram W Harrow · 2016
Closest in time.
Noise threshold of quantum supremacy
Keisuke Fujii · 2016
Closest in time.
Why I am optimistic about the silicon-photonic route to quantum computing
Terry Rudolph · 2016
Closest in time.
Mark Zhandry · 2016
Closest in time.