Fetching the paper…
Reading the bibliography…
I offer a case that quantum query complexity still has loads of enticing and fundamental open problems -- from relativized QMA versus QCMA and BQP versus IP, to time/space tradeoffs for collision and element distinctness, to polynomial degree versus quantum query complexity for partial functions, to the Unitary Synthesis Problem and more.
Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture
H. Huang · 1907
Earlier work this paper cites.
Quantum supremacy using a programmable superconducting processor
F. Arute et al · 1910
Earlier work this paper cites.
Towards optimal separations between quantum and randomized query complexities
A. Tal · 1912
Earlier work this paper cites.
Are there interactive protocols for co-NP languages?
L. Fortnow and M. Sipser · 1988
Earlier work this paper cites.
On the power of interaction
W. Aiello, S. Goldwasser, and J. Håstad · 1990
Earlier work this paper cites.
IP=PSPACE
A. Shamir · 1990
Earlier work this paper cites.
Rapid solution of problems by quantum computation
D. Deutsch and R. Jozsa · 1992
Earlier work this paper cites.
Quantum complexity theory
E. Bernstein and U. Vazirani · 1993
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.
A fast quantum mechanical algorithm for database search
L. K. Grover · 1996
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.
Quantum algorithm for the collision problem
G. Brassard, P. Høyer, and A. Tapp · 1997
Earlier work this paper cites.
Quantum lower bounds by polynomials
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf · 1998
Earlier work this paper cites.
Quantum lower bound for the collision problem
S. Aaronson · 2002
Earlier work this paper cites.
Quantum NP - a survey
D. Aharonov and T. Naveh · 2002
Earlier work this paper cites.
Complexity measures and decision tree complexity: a survey
H. Buhrman and R. de Wolf · 2002
Earlier work this paper cites.
Polynomial degree vs. quantum query complexity
A. Ambainis · 2003
Cited alongside, same era.
Exponential algorithmic speedup by a quantum walk
A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman · 2003
Cited alongside, same era.
A note on the classical lower bound for a quantum walk algorithm
S. Fenner and Y. Zhang · 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.
Quantum walk algorithm for element distinctness
A. Ambainis · 2004
Cited alongside, same era.
The quantum query complexity of the hidden subgroup problem is polynomial
M. Ettinger, P. Høyer, and E. Knill · 2004
Cited alongside, same era.
Component mixers and a hardness result for counterfeiting quantum money
A. Lutomirski · 2011
Later among the works it cites.
Reflections for quantum query algorithms
B. Reichardt · 2011
Later among the works it cites.
D. Aharonov, I. Arad, and T. Vidick · 2013
Later among the works it cites.
Quantum computation vs. firewalls
D. Harlow and P. Hayden · 2013
Later among the works it cites.
A super-Grover separation between randomized and quantum query complexities
S. Ben-David · 2015
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Quantum and classical strong direct product theorems and optimal time-space tradeoffs
H. Klauck, R. Špalek, and R. de Wolf · 2004
Cited alongside, same era.
Quantum versus classical proofs and advice
S. Aaronson and G. Kuperberg · 2007
Cited alongside, same era.
S. Aaronson, S. Beigi, A. Drucker, B. Fefferman, and P. Shor · 2008
Cited alongside, same era.
k-forrelation optimally separates quantum and classical query complexity
N. Bansal and M. Sinha · 2008
Cited alongside, same era.
The quantum supremacy Tsirelson inequality
W. Kretschmer · 2008
Cited alongside, same era.
An optimal separation of randomized and query complexity
A. A. Sherstov, A. A. Storozhenko, and P. Wu · 2008
Cited alongside, same era.
Later among the works it cites.
The complexity of quantum states and transformations: From quantum money to black holes, February 2016
S. Aaronson · 2016
Later among the works it cites.
Separations in query complexity using cheat sheets
S. Aaronson, S. Ben-David, and R. Kothari · 2016
Later among the works it cites.
Separations in query complexity based on pointer functions
A. Ambainis, K. Balodis, A. Belovs, T. Lee, M. Santha, and J. Smotrovs · 2016
Later among the works it cites.
Interactive proofs for quantum computations
D. Aharonov, M. Ben-Or, E. Eban, and U. Mahadev · 2017
Later among the works it cites.
Quantum sampling problems, BosonSampling, and quantum supremacy
A. P. Lund, M. J. Bremner, and T. C. Ralph · 2017
Later among the works it cites.
Quantum vs. classical proofs and subset verification
B. Fefferman and S. Kimmel · 2018
Later among the works it cites.
Classical verification of quantum computations
U. Mahadev · 2018
Later among the works it cites.
Quantum computing in the NISQ era and beyond, 2018
J. Preskill · 2018
Later among the works it cites.
Limitations of semidefinite programs for separable states and entangled games
A. W. Harrow, A. Natarajan, and X. Wu · 2019
Later among the works it cites.
Oracle separation of BQP and PH
R. Raz and A. Tal · 2019
Later among the works it cites.
Strong quantum computational advantage using a superconducting quantum processor, 2021
Y. Wu et al · 2021
Closest in time.