undefined | Better HN

0 pointseigenket1y ago0 comments

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

0 comments

sgt1011y ago

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.

ziofill1y ago

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

sgt1011y ago

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.

eigenketOP1y ago

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.

1 more reply

sgt1011y ago

thank you

j / k navigate · click thread line to collapse

0 comments

sgt1011y ago

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.

ziofill1y ago

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

sgt1011y ago

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

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.

eigenketOP1y ago

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.

1 more reply

sgt1011y ago

thank you

j / k navigate · click thread line to collapse