4 ms·

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 q

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.07825 https://arxiv.org/abs/2012.07825

adastra22 2y ago
And to extend off this comment, there are methods being worked on for building qubits that are intrinsically noise-free and don’t need the exponential number of error correcting operations. When those are available, you’ll see a step function increase in capabilities.
- andrepd 2y ago
  >When those are available Pretty big if
  - adastra22 2y ago
    We’re working on it.
- s1dev 2y ago
  For a circuit of size C, the size of a fault tolerant circuit to compute the same thing is O(C polylog C) https://arxiv.org/abs/quant-ph/9906129 https://arxiv.org/abs/quant-ph/9906129
  - adastra22 2y ago
    Technically correct is the best kind of correct.
adgjlsfhk1 2y ago
that paper is factoring with an algorithm that almost certainly isn't polynomial time. That paper is only slightly better than the quantum factoring algorithm of making a quantum computer perform trial division.
- eigenket 2y ago
  I agree
sgt101 2y ago
Interesting - why is Shor's sensitive to noise? Is that the Rphase gates?
- eigenket 2y ago
  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 https://arxiv.org/abs/2306.10072
  - sgt101 2y ago
    thank you
  - sgt101 2y 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.
  - ziofill 2y ago
    This is a minority point of view on quantum computing, as I understand.
    - sgt101 2y 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.
tsimionescu 2y ago
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).
- eigenket 2y ago
  I think its unknown, but my feeling is that the answer is almost certainly no. 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.
- adgjlsfhk1 2y ago
  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)

adastra22 2y ago

And to extend off this comment, there are methods being worked on for building qubits that are intrinsically noise-free and don’t need the exponential number of error correcting operations. When those are available, you’ll see a step function increase in capabilities.

andrepd 2y ago
>When those are available Pretty big if
- adastra22 2y ago
  We’re working on it.
s1dev 2y ago
For a circuit of size C, the size of a fault tolerant circuit to compute the same thing is O(C polylog C) https://arxiv.org/abs/quant-ph/9906129 https://arxiv.org/abs/quant-ph/9906129
- adastra22 2y ago
  Technically correct is the best kind of correct.

adgjlsfhk1 2y ago

that paper is factoring with an algorithm that almost certainly isn't polynomial time. That paper is only slightly better than the quantum factoring algorithm of making a quantum computer perform trial division.

eigenket 2y ago
I agree

sgt101 2y ago

Interesting - why is Shor's sensitive to noise? Is that the Rphase gates?

eigenket 2y ago
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 https://arxiv.org/abs/2306.10072
- sgt101 2y ago
  thank you
- sgt101 2y 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.
- ziofill 2y ago
  This is a minority point of view on quantum computing, as I understand.
  - sgt101 2y 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.

tsimionescu 2y ago

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

eigenket 2y ago
I think its unknown, but my feeling is that the answer is almost certainly no. 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.
adgjlsfhk1 2y ago
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)