Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. Join them; it only takes a minute:

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

BQP is the set of problems solvable in polynomial time for a given error tolerance, and it is suspected to be larger than P (and BPP, which is probably equal to P). However, inability for the gates to act perfectly, etc would require error-checking overhead. What is the overhead cost in the algorithm? In particular, does either the time or the number of q-bits overhead grow more than polynomially in the problem size (if it did then BQP would be altered)?

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

The threshold theorem says that if the error rate is below the threshold, a quantum algorithm with T locations (breadth times depth) can be made fault-tolerant with a blow-up (in both number of qubits and circuit size) by a factor which is a polynomial in the log of T. This is not enough to change BQP.

share|cite|improve this answer
Reference:Level Reduction and the Quantum Threshold Theorem. Also it also requires "weak correlation", personally I think that physical systems in practice will have this property. – Kevin Kostlan Nov 5 '12 at 22:38

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.