# Scaling of quantum error correction

I'm having a question regarding quantum error correction.

Using a large number of imperfect (but already very good) quantum gates, it is in theory possible to build an equivalent, error-corrected gate. What I don't understand, however, is how it precisely scales when I want to do computation using algorithms with a large input space.

To give a precise question:

Let's say I can create many individual CNOT gates with an individual probability of success of $\eta=99.99\%$. How many of them do I need to implement Shor's algorithm to factor a $1024$ bits integer with an overall probability of success of $50\%.$ ?

Once I reach the point where I can build a single error-corrected gate between two qubits, have I won the fight against decoherence or will it just be harder and harder to correct the errors as the input space scales up ?

Thanks.

-

The threshold theorem states that if you can perform gates with error rates below the threshold value, then you can do arbitrarily long quantum computations with overhead that is polynomial in the log of the length of the computation. The overhead is the ratio between the actual number of gates in the computation protected by fault-tolerance (the "physical" gates) and the number of gates that would be in the ideal computation you want to do (the "logical" gates). I.e., if you want to do a computation with T logical gates with overall error rate $\epsilon$, you need a total of $C T (\log (T/\epsilon))^n$ physical gates for some constants $C$ and $n$. (The constants depend on the details of the fault-tolerant protocol.)