5 ms·

We need PQC about 20 years before practical, scalable gate quantum computers appear (if they can do all the right gates). I think that this will be signaled wh

• adastra22 3y ago
  We are within 20 years of scalable quantum computers already.
  • adrianN 3y ago
    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.
    • 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.