[sgt101]

I am embarrassed because I looked up the quantum error correction paper and (guess what) I'm totally out of my depth on it!

So I could be being a complete plonker here, but what I can understand tells me that for quantum error correction there's an error rate which is the lowest bound on what can be corrected, but my reading of the Shor's Algorithm paper is that when there's noise the algorithm just doesn't work - so n>nc as n is 1?

[eigenket]

Ok so the relevant error rate you can think of as a quantity measuring (either on average or worst case) how far the state you produced in your quantum computer is from the state you wanted to create. I.e. if the error rate is small the states are close and if its large they're very different. You can also model the noisy system as something like reality rolls a dice and randomly chooses whether to apply the operation you wanted or do something different. If the error rate is small then most of the time it does what you wanted.

The point of the Shor's algorithm paper is that Shor's algorithm doesn't scale, that is you might be able to factor some numbers but if you have some fixed nonzero error then you can't factor bigger numbers just by adding more qubits.

On the other hand the point of the threshold theorem for quantum error correction is that as long as the error rate you have is less than some critical value, then you can make your error rate smaller by adding more qubits.

The way this works is that you can use a bigger quantum system to simulate a smaller one with a smaller error rate. Let's say (for example) you can use your bigger quantum system to simulate a smaller one with half the error rate. Then you could add another layer of simulation so now your physical system is simulating a smaller system, which is simulating a smaller system which has a quarter of the error rate. People have analysed how many extra qubits you need for this sort of error correction and it essentially adds a polylogarithmic overhead to your requirements. Polylog is very good scaling, but the constants are (as far as I know) pretty big right now and therefore impractical.

If you do this "properly", and someone manages to build a physical system you can scale like this with an error rate below the required threshold then this essentially circumvents the problem in the Shor's algorithm paper, you add more physical noisy qubits and reduce the error in your simulated "logical" qubits.

The author of the Shor's algorithm paper essentially doesn't believe this threshold theorem stuff is actually going to work in reality, partly because they think quantum mechanics is wrong (it is, but it's wildly unclear if its wrong in a way that would cause problems for the threshold theorem).

[adastra22]

Then there is the hypothetical quantum computer systems whose error rates are so slow as to be negligible and you don’t need error correction at all. Those may be on the horizon as well.