121–127 of 127 posts
Earlier quoted context omitted.
But have they factored anything bigger?
They have reportedly made it to proving that 31 is prime, as I said earlier, using their 1000-qubit chips.
Earlier quoted context omitted.
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 concl…
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…
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).
Earlier quoted context omitted.
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…
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 operatio…
https://news.ycombinator.com/item?id=40086515
"Update on April 18: Step 9 of the algorithm contains a bug, which I don’t know how to fix."
...
"Now the claim of showing a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold."
"Note: Update on April 18: Step 9 of the algorithm contains a bug, which I don’t know how to fix. See Section 3.5.9 (Page 37) for details. I sincerely thank Hongxun Wu and (independently) Thomas Vidick for finding the bug today. Now the claim of showing a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold. I leave the rest of the paper as it is (added a clarification of an operation in Step 8) as a hope that ideas like Complex Gaussian and windowed QFT may find other applications in quantum computation, or tackle LWE in other ways."
There was an update of the paper 2024-04-18: "Note: Update on April 18: Step 9 of the algorithm contains a bug, which I don’t know how to fix. See Section 3.5.9 (Page 37) for details. I sincerely thank Hongxun Wu and (independently) Thomas Vidick for finding the bug today. Now the claim of showing a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold. I leave the rest…
Earlier quoted context omitted.
There was a previous one removed a few months ago for malware called HBO Max Watch Party. Was that it? If you have a specific extension id I can file a bug on your behalf. And after reading about the situation internally, I can confirm there are dozens of people working on this problem, and that you have no idea what you're talking about. So please try to be a bit more humble.
https://chrome.google.com/webstore/detail/hbo-watch-party/dn... This is the link to the malicious extension.