Origin of quantum complexity theory

Question

Who was/were the first person/people to introduce the topic of quantum complexity theory and problem classes like BQP and QMA?

Answer 1

The class BQP (see also Complexity Zoo: BQP) was defined by

• E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal on Computing 26, pp. 1411-1473 (1997).

The class QMA (see also Complexity Zoo: QMA) was defined by

• A. Kitaev. Quantum NP. Talk at AQIP’99: Second Workshop on Algorithms in Quantum Information Processing, DePaul University (January 1999).

which apparently built on the idea of a "quantum proof" suggested by

• E. Knill. Quantum randomness and nondeterminism. Technical Report LAUR-96-2186, Los Alamos National Laboratory (1996). [arXiv:quant-ph/9610012].

An important relative to QMA, which is perhaps more delicate but which in a certain respect is a more exact analogue of NP for quantum computation, is the class QMA₁ (Complexity Zoo), in which the completeness constraint is perfect (i.e. for YES instances, there is a "quantum proof" with acceptance probability 1, albeit for a noiseless quantum computer). This was defined in

• S. Bravyi. Efficient algorithm for a quantum analogue of 2-SAT (2006). [arXiv:quant-ph/0602108]

There are other interesting quantum classes, of course. If you want an introduction to the subject, a good start would be

• John Watrous. Quantum Computational Complexity. Encyclopedia of Complexity and System Science, Springer (2009). [arXiv:0804.3401].