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.
 A: 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.)
This means that the overhead cost for very large computations is not much worse than the cost for merely large computations.  Unfortunately, in existing protocols, the constants are large enough that the overhead for typical computations is pretty large.  I can't give you the numbers for your particular example off the top of my head, but even the best protocols have overhead on the order of thousands.  Possibly there exist as-yet undiscovered fault-tolerant protocols that could do much better.
When you can perform one logical CNOT gate which is more reliable than your best physical gate, I wouldn't go so far as to say you have "won" the fight against decoherence, but you've certainly gotten past one of the most difficult steps.
