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)?
Tell me more
×
Physics Stack Exchange is a question and answer site for
active researchers, academics and students of physics. It's 100% free, no registration required.
|
|
|
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. |
|||
|
