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


1 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 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

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$
    – N J
    Commented Dec 10, 2012 at 17:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.