[eigenket]

Yeah, for Shor's algorithm to factor an integer of order 2^k you need controlled phase gates with phases roughly order 2^{-k} (very roughly, with some caveats, but lets just say you need some small ones) these very small phase gates are susceptible to even very small errors.

This is a gross oversimplification. For the true version see here

https://arxiv.org/abs/2306.10072

[sgt101]

Took me a while to read it - seems to be a pretty significant take down of anything that uses a QFT - basically reality won't permit it.

[ziofill]

This is a minority point of view on quantum computing, as I understand.

[sgt101]

Wot? Science isn't a democracy! The parent refs a preprint from a very reputable author, which has been somewhat peer-reviewed already *

Now, I got to the bottom of page 6 and my maths failed me: I can't follow the expansion, but I expect that the reviewers of Physica A or where ever the gentleman who wrote this sends it off to will be able to check. I do follow the principle of the proof though and it's pretty intuitive to me, for what that's worth.

Anyway, I can't say I give a hoot what the majority or minority think - and nor should anyone else. Read the paper for yourself and make up your mind.

* The author thanks Al Aho, Dan Boneh, P ́eter Ga ́cs, Zvi Galil, Fred Green, Steve Homer, Leonid Levin, Dick Lipton, Ashwin Maran, Albert Meyer, Ken Regan, Ron Rivest, Peter Shor, Mike Sipser, Les Valiant, and Ben Young for insightful comments. He also thanks Eric Bach for inspiring discus- sions on some of the number theoretic estimates, and we hope to report some further improvements soon [7]. A similar result can be proved for Shor’s algorithm computing Discrete Logarithm, and will be reported later.

[eigenket]

To be clear: there are two related but ultimately separate claims here.

1. Shor's algorithm won't work on the very noisy quantum computer we have for the near and intermediate future.

2. Shor's algorithm won't work on a hypothetical error corrected future quantum computer.

Claim 1 is pretty convincing proved in the paper. Claim 2 is not. The author puts forward some arguments for claim 2 in the introduction and conclusions but explicitly states that he does not prove it.

I think the point of view that the person you're replying to is talking about is claim 2. There are pretty good reasons to believe that claim 2 is false in my opinion, in particular we have threshold theorems for quantum error correction which should "save the day" for quantum computing.

[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.

[sgt101]

thank you