4 ms·

I thought the error rate has stayed pretty exponential in terms of the number of physical qubits needed to express a logical qubit and it’s not actually known i

I thought the error rate has stayed pretty exponential in terms of the number of physical qubits needed to express a logical qubit and it’s not actually known if we’re any closer on that metric vs other more easily achieved metrics. Additionally, I was under the impression that not all QCs being built are able of executing Shor’s algorithm which added additional challenges that aren’t solved. My final impression is that having the QC algorithm run faster than a classical computer doing the same operation has also not necessarily gotten better so we don’t even know if we are actually closer to Quantum supremacy in terms of actually useful more general computation instead of the limited supremacy that Google achieved in 2019 on specific problems, similar to the (still ongoing?) controversy whether DWave built a QC or a quantum annealer capable of accelerating simulations of very specific physical properties. Is this impression outdated and/or misinformed? Would love to update my priors.

cwillu 2y ago
A QC that can't run Shor's algorithm is not a QC, as much as D-Wave screams and stamps their feet that it's not fair.
- jessriedel 2y ago
  In principle it can be a QC, just not a general purpose (“Q-Turing complete”) QC. There were useful classical computing machines before there were general purpose Turing-complete classical computers. In practice, the first useful QCs will probably be Q-Turing complete.
- NickC25 2y ago
  I'm a complete layman when it comes to Quantum Computing, but I thought Shor's algorithm is effectively the most basic usecase example of Quantum Computers? I'm confused here.
  - dumbo-octopus 2y ago
    Yes, but it doesn't work on modern hardware. Too much noise. Everyone in the industry is basically fully occupied with coming up with a mechanism for active error correction. But based on what I've heard from the folks on the front lines, it's still 10+ years away at minimum.
  - jessriedel 2y ago
    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
jessriedel 2y ago
> I thought the error rate has stayed pretty exponential in terms of the number of physical qubits needed to express a logical qubit There is finite a threshold error rate (roughly 0.1-1%) at which you can produce a single logical qubit with an unbounded number of physical qubits (infinite overhead). For error rates below the threshold, the overhead becomes much less. People expect overheads in the thousands. See Fig. 1 in our paper. https://arxiv.org/pdf/2009.05045 https://arxiv.org/pdf/2009.05045 > and it’s not actually known if we’re any closer on that metric vs other more easily achieved metrics. We are getting lower error rates. But until we cross the error threshold, the overhead for a logical qubit is infinity. > I was under the impression that not all QCs being built are able of executing Shor’s algorithm Correct. > which added additional challenges that aren’t solved. Logical qubits enable general purpose quantum computing, which includes Shor's algorithm. As mentioned, we don't have logical qubits yet, and some people are trying to build less general devices to solve certain math problems in the meantime. But the overall goal for the field is still logical qubits, and there's steady progress on that. > My final impression is that having the QC algorithm run faster than a classical computer doing the same operation has also not necessarily gotten better I can't really parse the claim, but I think your impression is wrong. Supremacy has always been a fuzzy bound, since it's defined in terms of the best known classical algorithms. But the supremacy results have gotten more unambiguous over time.
- vlovich123 2y ago
  > I can't really parse the claim, but I think your impression is wrong. Supremacy has always been a fuzzy bound, since it's defined in terms of the best known classical algorithms. But the supremacy results have gotten more unambiguous over time. By that I mean that integer factorization is still slower than classical machines even though the numbers that can be factored have gotten larger. Similarly, with the exception of very specific toy problems specifically constructed to demonstrate quantum supremacy, we haven't achieved supremacy on any interesting and useful problems (not sure if DWave's quantum annealing machine really has any useful applications but presumably it must, but also not clear that it's a meaningful step on the path to a QC).
  - 2y ago

cwillu 2y ago

A QC that can't run Shor's algorithm is not a QC, as much as D-Wave screams and stamps their feet that it's not fair.

jessriedel 2y ago
In principle it can be a QC, just not a general purpose (“Q-Turing complete”) QC. There were useful classical computing machines before there were general purpose Turing-complete classical computers. In practice, the first useful QCs will probably be Q-Turing complete.
NickC25 2y ago
I'm a complete layman when it comes to Quantum Computing, but I thought Shor's algorithm is effectively the most basic usecase example of Quantum Computers? I'm confused here.
- dumbo-octopus 2y ago
  Yes, but it doesn't work on modern hardware. Too much noise. Everyone in the industry is basically fully occupied with coming up with a mechanism for active error correction. But based on what I've heard from the folks on the front lines, it's still 10+ years away at minimum.
- jessriedel 2y ago
  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

jessriedel 2y ago

> I thought the error rate has stayed pretty exponential in terms of the number of physical qubits needed to express a logical qubit There is finite a threshold error rate (roughly 0.1-1%) at which you can produce a single logical qubit with an unbounded number of physical qubits (infinite overhead). For error rates below the threshold, the overhead becomes much less. People expect overheads in the thousands. See Fig. 1 in our paper. https://arxiv.org/pdf/2009.05045 https://arxiv.org/pdf/2009.05045 > and it’s not actually known if we’re any closer on that metric vs other more easily achieved metrics. We are getting lower error rates. But until we cross the error threshold, the overhead for a logical qubit is infinity. > I was under the impression that not all QCs being built are able of executing Shor’s algorithm Correct. > which added additional challenges that aren’t solved. Logical qubits enable general purpose quantum computing, which includes Shor's algorithm. As mentioned, we don't have logical qubits yet, and some people are trying to build less general devices to solve certain math problems in the meantime. But the overall goal for the field is still logical qubits, and there's steady progress on that. > My final impression is that having the QC algorithm run faster than a classical computer doing the same operation has also not necessarily gotten better I can't really parse the claim, but I think your impression is wrong. Supremacy has always been a fuzzy bound, since it's defined in terms of the best known classical algorithms. But the supremacy results have gotten more unambiguous over time.

vlovich123 2y ago
> I can't really parse the claim, but I think your impression is wrong. Supremacy has always been a fuzzy bound, since it's defined in terms of the best known classical algorithms. But the supremacy results have gotten more unambiguous over time. By that I mean that integer factorization is still slower than classical machines even though the numbers that can be factored have gotten larger. Similarly, with the exception of very specific toy problems specifically constructed to demonstrate quantum supremacy, we haven't achieved supremacy on any interesting and useful problems (not sure if DWave's quantum annealing machine really has any useful applications but presumably it must, but also not clear that it's a meaningful step on the path to a QC).
- 2y ago