Who was/were the first person/people to introduce the topic of quantum complexity theory and problem classes like BQP and QMA?
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 QMA1 (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].
-
$\begingroup$ Thank you, I couldn't seem to find that info anywhere. I suppose Complexity Zoo would have been a good start. $\endgroup$ – Nathan Jordan Dec 10 '12 at 17:44