5 ms·

The record for integer factoring on quantum computers was on the order of factoring fifteen into three times five the last time I checked. Can we do three digit

The record for integer factoring on quantum computers was on the order of factoring fifteen into three times five the last time I checked. Can we do three digits now?

baby 3y ago
The last time I checked they even cheated to factor fifteen
- WJW 3y ago
  You should check again. Numbers like 1099551473989 have been factored successfully by now. The arxiv link in the sibling post is a good start.
  - adgjlsfhk1 3y ago
    biggest number factored by a quantum computer isn't the right question. the right question is biggest number factored using a polynomial time algorithm. the answer to that as far as I know of still 15 (although I would be interested in papers that show more progress)
    - adastra22 3y ago
      Application of Shor's algorithm is currently limited by available error correction. Long-lived qubits would eliminate that need and drastically increase capabilities.
      - sgt101 3y ago
        I'm not sure that you are correct. I've tried to read https://arxiv.org/abs/2306.10072 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 maintain it.
        adastra22 3y ago
        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.
      - pclmulqdq 3y ago
        I believe the current record using Shor's algorithm is 31, done by IBM recently.
        baby 3y ago
        we need sources in this thread
        pclmulqdq 3y ago
        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 https://www.nature.com/articles/s41598-021-95973-w IBM has gone through 2 generations of chips since then.
        sgt101 3y ago
        But have they factored anything bigger?
        pclmulqdq 3y ago
        They have reportedly made it to proving that 31 is prime, as I said earlier, using their 1000-qubit chips.
        adgjlsfhk1 3y ago
        proving primality is doable in polynomial time without a quantum computer, so that's hardly impressive.
    - sgt101 3y ago
      This is one of the things I really resent about QC as a field - there's so much chaff where one paper will say "we can do x" and the reality is that x does not mean what everyone thought that they meant. Number of Qbits is another thing - also what gates are implemented in the devices; how long they can run for etc etc etc.
eigenket 3y ago
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 3y 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 3y ago
    >When those are available Pretty big if
    - adastra22 3y ago
      We’re working on it.
  - s1dev 3y 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 3y ago
      Technically correct is the best kind of correct.
- adgjlsfhk1 3y 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.
vikramkr 3y ago
I'm not sure that's the right question. It's more, is there a chance at all of anyone figuring it out, and given the enormous scale of the security risk that poses, we should start proactively mitigating those threats. If fusion energy goes from perpetually 10 years away to suddenly here, that's pretty much just a white swan. If quantum computers happen, that's a global security risk before it's a civilizational upgrade.

The record for integer factoring on quantum computers was on the order of factoring fifteen into three times five the last time I checked. Can we do three digits now?

baby 3y ago

The last time I checked they even cheated to factor fifteen

WJW 3y ago
You should check again. Numbers like 1099551473989 have been factored successfully by now. The arxiv link in the sibling post is a good start.
- adgjlsfhk1 3y ago
  biggest number factored by a quantum computer isn't the right question. the right question is biggest number factored using a polynomial time algorithm. the answer to that as far as I know of still 15 (although I would be interested in papers that show more progress)
  - adastra22 3y ago
    Application of Shor's algorithm is currently limited by available error correction. Long-lived qubits would eliminate that need and drastically increase capabilities.
    - sgt101 3y ago
      I'm not sure that you are correct. I've tried to read https://arxiv.org/abs/2306.10072 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 maintain it.
      - adastra22 3y ago
        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.
    - pclmulqdq 3y ago
      I believe the current record using Shor's algorithm is 31, done by IBM recently.
      - baby 3y ago
        we need sources in this thread
        pclmulqdq 3y ago
        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 https://www.nature.com/articles/s41598-021-95973-w IBM has gone through 2 generations of chips since then.
        sgt101 3y ago
        But have they factored anything bigger?
        pclmulqdq 3y ago
        They have reportedly made it to proving that 31 is prime, as I said earlier, using their 1000-qubit chips.
        adgjlsfhk1 3y ago
        proving primality is doable in polynomial time without a quantum computer, so that's hardly impressive.
  - sgt101 3y ago
    This is one of the things I really resent about QC as a field - there's so much chaff where one paper will say "we can do x" and the reality is that x does not mean what everyone thought that they meant. Number of Qbits is another thing - also what gates are implemented in the devices; how long they can run for etc etc etc.

eigenket 3y ago

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 3y 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 3y ago
  >When those are available Pretty big if
  - adastra22 3y ago
    We’re working on it.
- s1dev 3y 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 3y ago
    Technically correct is the best kind of correct.
adgjlsfhk1 3y 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.

vikramkr 3y ago

I'm not sure that's the right question. It's more, is there a chance at all of anyone figuring it out, and given the enormous scale of the security risk that poses, we should start proactively mitigating those threats. If fusion energy goes from perpetually 10 years away to suddenly here, that's pretty much just a white swan. If quantum computers happen, that's a global security risk before it's a civilizational upgrade.