Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 7 down vote accepted

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].
share|cite|improve this answer
Thank you, I couldn't seem to find that info anywhere. I suppose Complexity Zoo would have been a good start. – Nathan Jordan Dec 10 '12 at 17:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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