Threshold theorem assumes that the error rate is bounded above by a constant. However, quantum decoherence is characterized by $$\langle E_{i}(t)|E_{j}(t) \rangle \propto e^{-t/\tau _{d}}$$ see here, here and here.

So the error rate is not bounded above by a constant and the quantum threshold theorem does not hold with such a decoherence rate or error rate. How can the scalable quantum computer be built with such a contradiction between quantum threshold theorem and the error rate? The error tolerant code can solve the problem?


1 Answer 1


There is no contradiction.

The threshold theorem requires that the error rate, i.e. error probability per gate (or per unit of time), be below a threshold. On the other hand, the exponential decay characterizes the absolute success probability, i.e. success probability in a computation involving a given number of gates (or of a given duration).

A little more formally, we can recognize the consistency between the two by estimating the absolute success probability $p$ of a computation consisting of $k$ gates under the assumption of constant per gate error probability $q$. A computation succeeds when every gate succeeds, so assuming errors are independent, we have$^1$

$$ p = (1-q)^k = e^{-\alpha k}\tag1 $$

where $\alpha=\ln\left(\frac{1}{1-q}\right)$. Thus, the assumption of constant per gate error probability makes the absolute success probability decay exponentially in the overall number of gates. Comparing to the equation in the question we see that, in this respect, decoherence behaves just like any source of error of constant per gate probability.

Now, the reason this exponential decay is not believed to stand in the way of practical large-scale quantum computers is that quantum error correction (QEC) provides the means of exponentially suppressing per (logical) gate error probability. In other words, QEC enables us to make $q$ as close to zero as we need for $p$ to be as close to $1$ as we desire. See this other answer of mine for a little more details.

$^1$ We're neglecting the highly remote possibility of multiple errors cancelling each other out.

  • 1
    $\begingroup$ Is “the assumption of constant per gate error probability $q$.” proved or valid? $\endgroup$ Commented Sep 15, 2022 at 5:07

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.