I work on homomorphic encryption, and there are some rumors circulating that, if this checks out, it will break some of the leading FHE schemes like BFV, where the moduli used are quite large (in the hundreds of bits or even over a thousand bits).
Post quantum crypto is cryptography that cannot be broken by a quantum computer. This is rather nebulous, since we haven't yet discovered all possible algorithms that can run on quantum computers. Before you know it, someone comes along and finds a new efficient algorithm for quantum computers that breaks something thought to be post-quantum. Which is what is happening here - if the results stand up under scrutiny.
Sidenote: it may turn out that any crypto scheme which supports some operation on ciphertexts that translates into an operation on the plaintexts is quantum-resilient (or, vice versa, quantum-vulnerable). But tgat would require a fornal proof.
I think that this will be signaled when someone factors a 32 bit integer on one. At that point I guess it'll be about 20 years before someone can factor a 2048 bit integer, and I'll get twitchy about what I am sending over the wire with PKI. My feeling is that all my secrets from 20 years ago are irrelevant to life now so I feel 20 years of warning is quite sufficient.
IBM has gone through 2 generations of chips since then.
Pretty big if
This is a gross oversimplification. For the true version see here
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.
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.
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?
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).
These sort of variational algorithms are appealing (to some people) because they're potentially usable on the sort of noisy small quantum computers we have today and in the near term future, but they aren't very fancy. I think in general what you'd expect to get out of them is a sort of Grover's algorithm-like square root speedup.