4 ms·

TLDR; They have knocked the Shors algorithm complexity to n^1.5 in time and space. (Correct me if I'm wrong)

josalhor 3y ago
What are the constant factors here? Could this be dropped in everywhere they are already using Shor's algorithm and just get a speed up? If so, this results seems incredibly influential.
- deleted 3y ago
  [deleted]
- Pazzaz 3y ago
  No one is "already using Shor's algorithm". Wikipedia lists the largest numbers factored using Shor's algorithm on a real quantum computer as follows: - The number 15 (5*3) was factored in 2001 - The number 21 (7*3) was factored in 2012 - An attempt to factor 35 (5*7) was made in 2019 but they didn't succeed because of accumulation of errors in the quantum computer. Quantum computers today are very bad, so changing the algorithm probably won't change much.
  - upofadown 3y ago
    There is an argument out there that the 15 and 21 factorizations involved built in knowledge of the answer. If you accept that then there has been zero progress demonstrated so far for factoring numbers using quantum effects, not just a ridiculously small amount of progress.
    - oldgradstudent 3y ago
      On the positive side, they haven't factored 17 and 19.
      - firejake308 3y ago
        Is this a joke? Or...
  - AnimalMuppet 3y ago
    So, less than one bit of progress per decade? That's not exactly huge progress...
    - daveguy 3y ago
      At this rate, just 2510*1.5 years and we will crack all current AES. Hopefully we will be using 512 bit keys by then. 512 bits should be enough for anyone.
      - foobiekr 3y ago
        Shoes does not attack symmetric ciphers like AES. Grover’s algorithm applies and will never be used against even AES 128.
control-k 3y ago
You are wrong, but close. They show that you can split up the factoring problem so you may solve sqrt(n) smaller problems, all requiring n^1.5 quantum operations, instead of a single run taking n^2 operations. This reduction can be implemented on a classical computer in polynomial time. They also require more qubits per run, n^1.5 instead of n but it is unclear to me whether this comes from n*sqrt(n), i.e., sqrt(n) paralel runs on n qubits, or that each run requires n^1.5 qubits. I would expect the first. So, the quantum part of the algorithm still requires n^2 gates, but the improvement is that it is split up (and non-adaptability). This means that it can be run in parallel, and that the individual runs will have less problems with errors stacking due to circuit depth. Note that the classical overhead for the reduction might be relatively high. Original paper: https://arxiv.org/pdf/2308.06572.pdf https://arxiv.org/pdf/2308.06572.pdf
spott 3y ago
N in space. There are two combined results in the article. The first was n^1.5 in space and time, the second reduced that to n in space. The original was n^2 in time and n in space.

What are the constant factors here? Could this be dropped in everywhere they are already using Shor's algorithm and just get a speed up? If so, this results seems incredibly influential.

deleted 3y ago
[deleted]
Pazzaz 3y ago
No one is "already using Shor's algorithm". Wikipedia lists the largest numbers factored using Shor's algorithm on a real quantum computer as follows: - The number 15 (5*3) was factored in 2001 - The number 21 (7*3) was factored in 2012 - An attempt to factor 35 (5*7) was made in 2019 but they didn't succeed because of accumulation of errors in the quantum computer. Quantum computers today are very bad, so changing the algorithm probably won't change much.
- upofadown 3y ago
  There is an argument out there that the 15 and 21 factorizations involved built in knowledge of the answer. If you accept that then there has been zero progress demonstrated so far for factoring numbers using quantum effects, not just a ridiculously small amount of progress.
  - oldgradstudent 3y ago
    On the positive side, they haven't factored 17 and 19.
    - firejake308 3y ago
      Is this a joke? Or...
- AnimalMuppet 3y ago
  So, less than one bit of progress per decade? That's not exactly huge progress...
  - daveguy 3y ago
    At this rate, just 2510*1.5 years and we will crack all current AES. Hopefully we will be using 512 bit keys by then. 512 bits should be enough for anyone.
    - foobiekr 3y ago
      Shoes does not attack symmetric ciphers like AES. Grover’s algorithm applies and will never be used against even AES 128.

control-k 3y ago

You are wrong, but close. They show that you can split up the factoring problem so you may solve sqrt(n) smaller problems, all requiring n^1.5 quantum operations, instead of a single run taking n^2 operations. This reduction can be implemented on a classical computer in polynomial time. They also require more qubits per run, n^1.5 instead of n but it is unclear to me whether this comes from n*sqrt(n), i.e., sqrt(n) paralel runs on n qubits, or that each run requires n^1.5 qubits. I would expect the first. So, the quantum part of the algorithm still requires n^2 gates, but the improvement is that it is split up (and non-adaptability). This means that it can be run in parallel, and that the individual runs will have less problems with errors stacking due to circuit depth. Note that the classical overhead for the reduction might be relatively high. Original paper: https://arxiv.org/pdf/2308.06572.pdf https://arxiv.org/pdf/2308.06572.pdf

spott 3y ago

N in space. There are two combined results in the article. The first was n^1.5 in space and time, the second reduced that to n in space. The original was n^2 in time and n in space.