The space "just above" BQP

Relativizations of the 𝒫 = ? ​ 𝒩 ​ 𝒫 \mathcal{P}=?\mathcal{NP} question

T. Baker, J. Gill, and R. Solovay · 1975

Earlier work this paper cites.

Two simple proofs of the Kochen-Specker theorem

A Peres · 1991

Earlier work this paper cites.

Quantum complexity theory

Ethan Bernstein and Umesh Vazirani · 1993

Earlier work this paper cites.

A fast quantum mechanical algorithm for database search

Lov K. Grover · 1996

Earlier work this paper cites.

Quantum computability

Leonard M. Adleman, Jonathan Demarrais, Ming-deh, and A. Huang · 1997

Earlier work this paper cites.

Strengths and weaknesses of quantum computing

Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani · 1997

Earlier work this paper cites.

A complete promise problem for statistical zero-knowledge

A. Sahai and S.P. Vadhan · 1997

Cited alongside, same era.

Daniel S. Abrams and Seth Lloyd. Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems. Phys. Rev. Lett., 81, 3992–3995, 1998

1998

Cited alongside, same era.

Quantum lower bound for the collision problem

Scott Aaronson · 2002

Cited alongside, same era.

Both Toffoli and controlled-NOT need little help to do universal quantum computing

Y. Shi · 2003

Cited alongside, same era.

The quantum query complexity of the hidden subgroup problem is polynomial

Mark Ettinger, Peter Høyer, and Emanuel Knill · 2004

Cited alongside, same era.

Quantum Computation and Quantum Information (Cambridge Series on Information and the Natural Sciences)

Michael A. Nielsen and Isaac L. Chuang · 2004

Later among the works it cites.

Quantum computing and hidden variables

Scott Aaronson · 2005

Later among the works it cites.

Quantum computing, postselection, and probabilistic polynomial-time

Scott Aaronson · 2005

Later among the works it cites.

The Solovay-Kitaev algorithm

Christopher M. Dawson and Michael A. Nielsen · 2006

Later among the works it cites.

Computational Complexity: A Modern Approach

Sanjeev Arora and Boaz Barak · 2009

Later among the works it cites.