Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Quantum Algorithms for Lattice Problems

eprint.iacr.org

Post reply on HN
Print view View original

111–120 of 127 posts

Re: Quantum Algorithms for Lattice Problems

#111

Post by eigenket »

sgt101 wrote: post #110
ziofill wrote: post #108

Earlier quoted context omitted.

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

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 intui…

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.

Re: Quantum Algorithms for Lattice Problems

#112

Post by adgjlsfhk1 »

tsimionescu wrote: post #104
eigenket wrote: post #84

Earlier quoted context omitted.

Significantly larger numbers than 15 have been factored [1] but not using Shor's algorithm. Shor's algorithm is particularly sensitive to noise/errors in your quantum computer and isn't going to be useful unless we get a properly error corrected machine working. The algorithms used in [1] are considerably less fancy (with worse asymptomatic performance) but are more resilient to noise. [1] https://arxiv.org/abs/2012.…

I couldn't quickly find any info, but does this algorithm show the kind of exponential quantum speed up needed to break RSA? Because if it's just slightly faster than the best known classical algorithms, then it's enitely irrelevant to the question of when we need to switch our encryption schemes (even though it may be a significant advancement in the area of quantum algorithms research).

it's generally believed that the algorithm is somewhere in between ecm and quadratic sieve (so slower by a super-polynomial factor than NFS which is the best classical algorithm)

Re: Quantum Algorithms for Lattice Problems

#113

Post by adgjlsfhk1 »

less_less wrote: post #90
adastra22 wrote: post #67

Earlier quoted context omitted.

Their deployment is additive. You would need to break both the PCQ and classical schemes, so they’d be unaffected here.

They wouldn't be immediately hacked, especially as this is a quantum algorithm anyway. But if it turns out that the current PQC schemes are not quantum-resistant, then that work will need to be redone (unless the progress in quantum computing stalls out, I guess). The current result does not break Kyber / Dilithium / NTRU variants / Falcon / FrodoKEM even assuming it's correct, but obviously there's some concern that…

there's always post quantum rsa https://eprint.iacr.org/2017/351.pdf. yes it sucks, but at least for the quantum computers we're likely to have 20 years from now, you could probably get away with a 1gb key...

Re: Quantum Algorithms for Lattice Problems

#114

Post by adastra22 »

adgjlsfhk1 wrote: post #113
less_less wrote: post #90

Earlier quoted context omitted.

They wouldn't be immediately hacked, especially as this is a quantum algorithm anyway. But if it turns out that the current PQC schemes are not quantum-resistant, then that work will need to be redone (unless the progress in quantum computing stalls out, I guess). The current result does not break Kyber / Dilithium / NTRU variants / Falcon / FrodoKEM even assuming it's correct, but obviously there's some concern that…

there's always post quantum rsa https://eprint.iacr.org/2017/351.pdf . yes it sucks, but at least for the quantum computers we're likely to have 20 years from now, you could probably get away with a 1gb key...

Lamport signatures work and are PQC. There are solutions that are practical to use (1gb rsa keys are not). Just not drop in replacements without large tradeoffs.

Re: Quantum Algorithms for Lattice Problems

#115

Post by adastra22 »

sgt101 wrote: post #105
adastra22 wrote: post #93

Earlier quoted context omitted.

Application of Shor's algorithm is currently limited by available error correction. Long-lived qubits would eliminate that need and drastically increase capabilities.

I'm not sure that you are correct. I've tried to read https://arxiv.org/abs/2306.10072 in the last day and if my reading is right (I am very stretched by this stuff so I am very happy to be corrected) then no amount of error correction will rescue Shor's - only zero error phase gates. I suspect that a similar story is true for native QML, as quantum memory scales it's just going to get exponentially harder to maintai…

That’s what I’m saying, effectively zero error phase gates are on the horizon. My company is working on the tech that would make them possible, for example, and we have competitors working on other paths to the same thing.

Re: Quantum Algorithms for Lattice Problems

#116

Post by baby »

pclmulqdq wrote: post #109
adastra22 wrote: post #93

Earlier quoted context omitted.

Application of Shor's algorithm is currently limited by available error correction. Long-lived qubits would eliminate that need and drastically increase capabilities.

I believe the current record using Shor's algorithm is 31, done by IBM recently.

we need sources in this thread

Re: Quantum Algorithms for Lattice Problems

#117

Post by pclmulqdq »

baby wrote: post #116
pclmulqdq wrote: post #109

Earlier quoted context omitted.

I believe the current record using Shor's algorithm is 31, done by IBM recently.

we need sources in this thread

If you want a number accompanied by a scientific publication, the best you get is 21: https://www.nature.com/articles/s41598-021-95973-w

IBM has gone through 2 generations of chips since then.

Re: Quantum Algorithms for Lattice Problems

#118

Post by sgt101 »

eigenket wrote: post #111
sgt101 wrote: post #110

Earlier quoted context omitted.

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 intui…

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 n>nc as n is 1?

Re: Quantum Algorithms for Lattice Problems

#119

Post by sgt101 »

pclmulqdq wrote: post #117
baby wrote: post #116

Earlier quoted context omitted.

we need sources in this thread

If you want a number accompanied by a scientific publication, the best you get is 21: https://www.nature.com/articles/s41598-021-95973-w IBM has gone through 2 generations of chips since then.

But have they factored anything bigger?

Re: Quantum Algorithms for Lattice Problems

#120

Post by pclmulqdq »

sgt101 wrote: post #119
pclmulqdq wrote: post #117

Earlier quoted context omitted.

If you want a number accompanied by a scientific publication, the best you get is 21: https://www.nature.com/articles/s41598-021-95973-w IBM has gone through 2 generations of chips since then.

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.
Post reply on HN