Fetching the paper…
Reading the bibliography…
The relationship between BQP and PH has been an open problem since the earliest days of quantum computing.
Relative to a random oracle A, P A ≠ N P A ≠ c o N P A P^{A}\neq NP^{A}\neq coNP^{A} with probability 1
C. H. Bennett and J. Gill · 1981
Earlier work this paper cites.
Parity, circuits, and the polynomial time hierarchy
M. Furst, J. B. Saxe, and M. Sipser · 1984
Earlier work this paper cites.
Separating the polynomial-time hierarchy by oracles (preliminary version)
A. C-C. Yao · 1985
Earlier work this paper cites.
Does co-NP have short interactive proofs?
R. B. Boppana, J. Håstad, and S. Zachos · 1987
Earlier work this paper cites.
Lower bounds for the size of circuits of bounded depth with basis { & , ⊕ } \left\{\&,\oplus\right\}
A. A. Razborov · 1987
Earlier work this paper cites.
Algebraic methods in the theory of lower bounds for Boolean circuit complexity
R. Smolensky · 1987
Earlier work this paper cites.
Computational Limitations for Small Depth Circuits
J. Håstad · 1987
Earlier work this paper cites.
Private coins versus public coins in interactive proof systems
S. Goldwasser and M. Sipser · 1989
Earlier work this paper cites.
Approximate inclusion-exclusion
N. Linial and N. Nisan · 1990
Earlier work this paper cites.
IP=PSPACE
A. Shamir · 1992
Earlier work this paper cites.
Quantum complexity theory
E. Bernstein and U. Vazirani · 1993
Earlier work this paper cites.
Constant depth circuits, Fourier transform, and learnability
N. Linial, Y. Mansour, and N. Nisan · 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
Cited alongside, same era.
Quantum computability
L. Adleman, J. DeMarrais, and M.-D. Huang · 1997
Cited alongside, same era.
Strengths and weaknesses of quantum computing
C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani · 1997
Cited alongside, same era.
Threshold computation and cryptographic security
Y. Han, L. Hemaspaandra, and T. Thierauf · 1997
Cited alongside, same era.
A complete promise problem for statistical zero-knowledge
A. Sahai and S. Vadhan · 1997
Cited alongside, same era.
Quantum lower bounds by polynomials
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf · 1998
Cited alongside, same era.
The complexity of computing a Nash equilibrium
C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou · 2006
Later among the works it cites.
Bounded-error quantum state identification and exponential separations in communication complexity
D. Gavinsky, J. Kempe, O. Regev, and R. de Wolf · 2006
Later among the works it cites.
Polylogarithmic independence can fool DNF formulas
L. Bazzi · 2007
Later among the works it cites.
Exponential separation for one-way quantum communication complexity, with applications to cryptography
D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz, and R. de Wolf · 2007
Later among the works it cites.
On approximate majority and probabilistic time
E. Viola · 2007
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A. Klivans and D. van Melkebeek · 1999
Cited alongside, same era.
Succinct quantum proofs for properties of finite groups
J. Watrous · 2000
Cited alongside, same era.
Relativized separation of E Q P EQP from P N P P^{NP}
F. Green and R. Pruim · 2001
Cited alongside, same era.
Quantum lower bound for the collision problem
S. Aaronson · 2002
Cited alongside, same era.
Quantum lower bound for recursive Fourier sampling
S. Aaronson · 2003
Cited alongside, same era.
Exponential separation of quantum and classical one-way communication complexity
Z. Bar-Yossef, T. S. Jayram, and I. Kerenidis · 2004
Cited alongside, same era.
D. Aharonov, M. Ben-Or, and E. Eban · 2008
Later among the works it cites.
Universal blind quantum computation
A. Broadbent, J. Fitzsimons, and E. Kashefi · 2008
Later among the works it cites.
Classical interaction cannot replace a quantum message
D. Gavinsky · 2008
Later among the works it cites.
On the role of shared entanglement
D. Gavinsky · 2008
Later among the works it cites.
Exponential separation of quantum and classical non-interactive multi-party communication complexity
D. Gavinsky and P. Pudlák · 2008
Later among the works it cites.
Poly-logarithmic independence fools A C 0 AC^{0} circuits
M. Braverman · 2009
Closest in time.
D. Gavinsky · 2009
Closest in time.
A simple proof of Bazzi’s theorem
A. A. Razborov · 2009
Closest in time.