5
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your answer. So if I understand correctly, the qubit space is not a relevant parameter, just the number of gates is ? $\endgroup$
    – Oli
    Mar 8, 2013 at 1:48
  • $\begingroup$ Technically, the right parameter is the number of "locations" in the circuit, since errors can occur on qubits even when they are sitting around doing nothing. To a first approximation, the number of locations is number of qubits times the depth of the circuit. (The depth is the number of time steps needed when the circuit is parallelized.) If you ignore storage errors, then the number of gates is the right parameter. Note that the number of gates will typically be much larger than the number of qubits, except for the shortest computations. $\endgroup$
    – Daniel Gottesman
    Mar 8, 2013 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.