4 ms·

There are extant non-general purpose quantum computers that solve super esoteric useless math problems specially designed to be easy on these primitive quantum

There are extant non-general purpose quantum computers that solve super esoteric useless math problems specially designed to be easy on these primitive quantum computers but infeasible on any classical computer. (This is “quantum supremacy” aka “quantum advantage”.) Furthermore, we expect to develop slightly less primitive quantum computers in the medium-term that can solve maybe-interesting quantum simulation questions without having the capability to run Shor’s algorithm (at least on an interestingly large integers). So no, Shor’s algorithm is not the most basic use case. It’s just one of the cleanest to understand.

vlovich123 2y ago
Is there any reason to believe a computer that can do Shor's algorithm is actually possible? There's a lot of freaking out trying to build QC-resistent assymetric encryption, but we don't actually know whether or not it's physically possible to build the requisite error corrections to make it feasible in the first place, right? Is there reason to believe that the physical reality of QM doesn't require exponentially more and more qbits for every logical qbit added to the system? Basically, is there any reason to believe that a QC capable of Shor's doesn't degrade to a space / time tradeoff for a classical computer when it comes to integer factorization?
- jessriedel 2y ago
  The strong expert consensus is that fault-tolerant quantum computation is physically possible and it’s just a challenging engineering problem. One key insight is the threshold theorems, which show that if you can build individual physical gates with error rate below a finite threshold (typically 0.1-1%), you can just stack these gates together and they simulate logical operations with logical error rates that can be made exponentially small. https://en.wikipedia.org/wiki/Threshold_theorem https://en.wikipedia.org/wiki/Threshold_theorem If it helps, there are plenty of historical analogies. Quantum-enhanced sensing took more than half a century between conception and practical use, but it is currently used daily at LIGO.
  - NohatCoder 2y ago
    The strong expert consensus has been reached between a lot of people who would be out of a job if their consensus was the opposite.
    - jessriedel 2y ago
      Not really accurate. There are tons of tenured profs who are well-positioned to reveal reasons why QCs are fundamentally infeasible (and those kind of stories play well in the media). You can read about Gil Kalai's arguments here: https://www.quantamagazine.org/the-argument-against-quantum-computers-20180207/ https://www.quantamagazine.org/the-argument-against-quantum-... In any case, I'm happy to bet on this.
      - JohnKemeny 2y ago
        What would be a statement that you would put, say, $100k on, that would be determined within 2040. And which odds would you need on that?
        jessriedel 2y ago
        The existence of a handful of logical qubits. Like I can initialize them, swap them, entangle them, measure them, etc., all performed with essentially perfect fidelity (say, 1e-10 error rate). I’d immediately bet $100k on that by 2040 at 50-50 odds, and probably 80-20 if I had a day or two to review the literature and confirm I wasn’t being adversely selected against. If you wanted a useful machine, say factoring RSA-2048, you would need to push the date to more like 2050 or 2060. Most of the uncertainty comes from the economy, engineering cost, public interest in QC, AI doom, etc. If we could somehow make a platonic bet on “is a large QC constructible if dedicated $10T/yr for 200 years”, then I am over 95-5.
        vlovich123 2y ago
        With that kind of statement, it seems fundamentally immature to be deploying PQC on the Internet today when we're 20+ years out a useful machine. Prognostication this far into the future should not be the basis of making changes today - we're not good at it.
- cwillu 2y ago
  The coordinated failures implied by a failure of QEC to scale would be new physics; the existing principles don't predict that anything like that should occur. Which isn't to say that it's impossible, but it would be quite exciting if it were the case.
  - vlovich123 2y ago
    May not require new physics but may be arbitrarily expensive / impractical to build in reality, no?
    - cwillu 2y ago
      Not really, no. If the breakpoint for fault tolerance is reached, then in the absence of new physics causing the noise that needs to be corrected to be adversarially coordinated, quantum computers are scaleable.

vlovich123 2y ago

Is there any reason to believe a computer that can do Shor's algorithm is actually possible? There's a lot of freaking out trying to build QC-resistent assymetric encryption, but we don't actually know whether or not it's physically possible to build the requisite error corrections to make it feasible in the first place, right? Is there reason to believe that the physical reality of QM doesn't require exponentially more and more qbits for every logical qbit added to the system? Basically, is there any reason to believe that a QC capable of Shor's doesn't degrade to a space / time tradeoff for a classical computer when it comes to integer factorization?

jessriedel 2y ago
The strong expert consensus is that fault-tolerant quantum computation is physically possible and it’s just a challenging engineering problem. One key insight is the threshold theorems, which show that if you can build individual physical gates with error rate below a finite threshold (typically 0.1-1%), you can just stack these gates together and they simulate logical operations with logical error rates that can be made exponentially small. https://en.wikipedia.org/wiki/Threshold_theorem https://en.wikipedia.org/wiki/Threshold_theorem If it helps, there are plenty of historical analogies. Quantum-enhanced sensing took more than half a century between conception and practical use, but it is currently used daily at LIGO.
- NohatCoder 2y ago
  The strong expert consensus has been reached between a lot of people who would be out of a job if their consensus was the opposite.
  - jessriedel 2y ago
    Not really accurate. There are tons of tenured profs who are well-positioned to reveal reasons why QCs are fundamentally infeasible (and those kind of stories play well in the media). You can read about Gil Kalai's arguments here: https://www.quantamagazine.org/the-argument-against-quantum-computers-20180207/ https://www.quantamagazine.org/the-argument-against-quantum-... In any case, I'm happy to bet on this.
    - JohnKemeny 2y ago
      What would be a statement that you would put, say, $100k on, that would be determined within 2040. And which odds would you need on that?
      - jessriedel 2y ago
        The existence of a handful of logical qubits. Like I can initialize them, swap them, entangle them, measure them, etc., all performed with essentially perfect fidelity (say, 1e-10 error rate). I’d immediately bet $100k on that by 2040 at 50-50 odds, and probably 80-20 if I had a day or two to review the literature and confirm I wasn’t being adversely selected against. If you wanted a useful machine, say factoring RSA-2048, you would need to push the date to more like 2050 or 2060. Most of the uncertainty comes from the economy, engineering cost, public interest in QC, AI doom, etc. If we could somehow make a platonic bet on “is a large QC constructible if dedicated $10T/yr for 200 years”, then I am over 95-5.
        vlovich123 2y ago
        With that kind of statement, it seems fundamentally immature to be deploying PQC on the Internet today when we're 20+ years out a useful machine. Prognostication this far into the future should not be the basis of making changes today - we're not good at it.
cwillu 2y ago
The coordinated failures implied by a failure of QEC to scale would be new physics; the existing principles don't predict that anything like that should occur. Which isn't to say that it's impossible, but it would be quite exciting if it were the case.
- vlovich123 2y ago
  May not require new physics but may be arbitrarily expensive / impractical to build in reality, no?
  - cwillu 2y ago
    Not really, no. If the breakpoint for fault tolerance is reached, then in the absence of new physics causing the noise that needs to be corrected to be adversarially coordinated, quantum computers are scaleable.