4 ms·

Hasn’t the path to quantum computing with that many qubits always been full of unknown unknowns? I’m happy that researchers are preparing but it seems like defe

by klabb3 3y ago

Hasn’t the path to quantum computing with that many qubits always been full of unknown unknowns? I’m happy that researchers are preparing but it seems like defending against a threat of unknown shape that doesn’t exist is kind of futile. First, do we even have high confidence that QC is the thing that will break current algorithms? Secondly, how much time from “the writing is on the wall” until bad actors can deploy them for financial gain? Unless it’s short, why not wait and migrate later? Because like the xkcd with the $5 hammer, crypto primitives has to be the weakest link in the chain to really be a threat so big it warrants throwing it on top of everything just in case. I mean our security for even critical infrastructure is so bad that ransomware groups are rampant without any need to ever care about primitives. Also assuming that if you’re high value target for state actors, you’re not gonna use default TLS anyway. Extra assumption: most harvest-now-decrypt-later seem completely worthless? Anyway, rambling aside: is this just naive skepticism from a mortal non-enlightened engineer with a short sighted YAGNI mindset? Or have the purist academics been selling parachutes to workers in skyscrapers - ie a solution to a problem that wont materialize anytime soon? Please, forgive my ignorance.

juitpykyk 3y ago
> First, do we even have high confidence that QC is the thing that will break current algorithms? If it doesn't it means our physics theories are fundamentally wrong.
- tromp 3y ago
  Not necessarily. It could be that ECDLP (Elliptic Curve Discrete Log Problem) is not as hard as we thought. It's not inconceivable that it's in P (Polynomial time). In fact, if we were to see current algorithms being broken right now, I think it's more likely to be due to a classical algorithm breakthrough than by quantum algorithms running on an actual large scale quantum computer with hundreds or thousands of logical (i.e. practically error-free) qubits.
- sesm 3y ago
  We don’t have any mainstream physical theory that describes the process of quantum decoherence aka wave function collapse. We know it happens, but don’t know when exactly or how quickly. So if QCs fail, Quantum Mechanics won’t be proven wrong, but rather we’ll have more data on wave function collapse which has been an open question for more than a century. I personally like Penrose Objective Collapse theory, because it also connects gravity and QM in an unusual way.
  - juitpykyk 3y ago
    QM predicts that QCs will work. If QCs don't work, QM has a big problem. Wave collapse interpretation is an orthogonal topic.
    - lukan 3y ago
      Not being able to build something, is not the same as proofing it is impossible. (Unless one has a very high ego.) It might as well require some unknown tech, or material or rather a real understanding of the domain.
      - juitpykyk 3y ago
        Sure, but parent was saying what if we manage to build QC as we envision them and then they don't work.
    - sesm 3y ago
      QM doesn’t say anything about how long a system can stay in quantum entangled state, so it doesn’t say what is the limit to computations that can be performed on a quantum computer. Some computations were successfully performed, as QM predicts, but now it seems that researchers are hitting a limit.
      - juitpykyk 3y ago
        QM says QC as we envision them will work. QM says a quantum entangled state will remain like that until disturbed/measured. If there is some limit as you suggest, that means QM is at least partially broken.
bawolff 3y ago
> First, do we even have high confidence that QC is the thing that will break current algorithms? Yes? I mean nothing is certain, but it is the most viable known threat by a wide margin. > Secondly, how much time from “the writing is on the wall” until bad actors can deploy them for financial gain? Unless it’s short, why not wait and migrate later? Nobody knows, but its difficult to coordinate changes, and it is difficult to know which quantum algs actually work. It can take decades to have confidence a new crypto promitive actually works. As far as actually changing things, look how long it took to change out md5. People started warning it was insecure in 1996, it was totally broken in 2005, and in 2012 the flame malware used it to hack computers.
JanisErdmanis 3y ago
It is! Taking into account that only the Schor algorithm is proven to be exponentially faster in factorising numbers and looking into current progress on using it, the threat for RSA 2048 will become real in ridiculous 2^2048 years. This can be estimated by taking three events in factorisation: 2002: factorisation of 15 [1] 2012: factorisation of 21 [2] 2022: factorisation of 35 by IBM (although the article is about number 21, but let’s give them credit) [3] In a plot, the tendency is somewhat linear, with the factorised number increasing by one every year. A sceptic immediately replies to this thread, saying we already have 100-1000 qubit quantum computers and are on the path to getting a million qubits in the foreseeable future. That may as well be true. The issue is that the Schoor algorithm requires that the error rate of the qubit operations scale exponentially with the number of qubits. This is why IBM only uses five qubits in [3], although they already had a hundred qubit QCs at that time. It just produces meaningless results when used with more qubits. This is also why the line for factorisation is about to be linear. If the error rate of the qubit operations decreases by 20% every year and we have exponential progress, the usefulness of the Schor algorithm taken on a log scale would be linear. The error correction is not a panacea either. It does not reduce errors to zero for logical qubits but rather reduces them after the error threshold is reached. It would require repeated application to get the necessary error threshold to run the Schor algorithm for a desired number, which would require an unreasonable number of qubits. [1]: https://www.nature.com/articles/414883a https://www.nature.com/articles/414883a [2]: https://www.nature.com/articles/nphoton.2012.259 https://www.nature.com/articles/nphoton.2012.259 [3]: https://arxiv.org/pdf/2103.13855v1.pdf https://arxiv.org/pdf/2103.13855v1.pdf
- klabb3 3y ago
  > The issue is that the Schoor algorithm requires that the error rate of the qubit operations scale exponentially with the number of qubits. So… traditional silicon computing scales exponentially in time, but QC computes in constant time(!) with the minor detail that it scales exponentially in error. > If the error rate of the qubit operations decreases by 20% every year and we have exponential progress, the usefulness of the Schor algorithm taken on a log scale would be linear. Right, which is exactly the type of leeway you need, no? 1-2 qubits per year will take many decades to break ECC or RSA. It’s the same Moores law-style assumptions baked into traditional computing getting faster. > This is why IBM only uses five qubits in [3], although they already had a hundred qubit QCs at that time. It just produces meaningless results when used with more qubits. So IBM has this really cool gf, but she’s at a different school so you won’t know her. Half joking, but putting error propagation in the footnotes seems very off to me as a complete layman. Like thinking we can accurately predict the weather 5 months out with a bit more compute.
bradleyjg 3y ago
I don’t expect commercially viable fusion, room temperature superconductors, or useful quantum computers in my lifetime. The jury is still out on real self driving cars, but I’m less optimistic than I was five years ago.
- xhkkffbf 3y ago
  A friend of mine uses a self-driving taxi service in SF all of the time.
  - bradleyjg 3y ago
    How come you and all your other friends and family don’t? When do you think the rest of you will?
    - grayhatter 3y ago
      I'd say in half the amount of time it took for us to go from the first internal combustion engine to the Model T? Or if you think that's a bad comparison: The Model T to the honda civic?
      - bradleyjg 3y ago
        If that’s my odds are pretty good of living to see it. I hope you’re right.
    - xhkkffbf 3y ago
      Because I don't live in SF. So ask the companies when they'll deploy elsewhere.

by klabb3 3y ago

juitpykyk 3y ago

> First, do we even have high confidence that QC is the thing that will break current algorithms? If it doesn't it means our physics theories are fundamentally wrong.

tromp 3y ago
Not necessarily. It could be that ECDLP (Elliptic Curve Discrete Log Problem) is not as hard as we thought. It's not inconceivable that it's in P (Polynomial time). In fact, if we were to see current algorithms being broken right now, I think it's more likely to be due to a classical algorithm breakthrough than by quantum algorithms running on an actual large scale quantum computer with hundreds or thousands of logical (i.e. practically error-free) qubits.
sesm 3y ago
We don’t have any mainstream physical theory that describes the process of quantum decoherence aka wave function collapse. We know it happens, but don’t know when exactly or how quickly. So if QCs fail, Quantum Mechanics won’t be proven wrong, but rather we’ll have more data on wave function collapse which has been an open question for more than a century. I personally like Penrose Objective Collapse theory, because it also connects gravity and QM in an unusual way.
- juitpykyk 3y ago
  QM predicts that QCs will work. If QCs don't work, QM has a big problem. Wave collapse interpretation is an orthogonal topic.
  - lukan 3y ago
    Not being able to build something, is not the same as proofing it is impossible. (Unless one has a very high ego.) It might as well require some unknown tech, or material or rather a real understanding of the domain.
    - juitpykyk 3y ago
      Sure, but parent was saying what if we manage to build QC as we envision them and then they don't work.
  - sesm 3y ago
    QM doesn’t say anything about how long a system can stay in quantum entangled state, so it doesn’t say what is the limit to computations that can be performed on a quantum computer. Some computations were successfully performed, as QM predicts, but now it seems that researchers are hitting a limit.
    - juitpykyk 3y ago
      QM says QC as we envision them will work. QM says a quantum entangled state will remain like that until disturbed/measured. If there is some limit as you suggest, that means QM is at least partially broken.

bawolff 3y ago

> First, do we even have high confidence that QC is the thing that will break current algorithms? Yes? I mean nothing is certain, but it is the most viable known threat by a wide margin. > Secondly, how much time from “the writing is on the wall” until bad actors can deploy them for financial gain? Unless it’s short, why not wait and migrate later? Nobody knows, but its difficult to coordinate changes, and it is difficult to know which quantum algs actually work. It can take decades to have confidence a new crypto promitive actually works. As far as actually changing things, look how long it took to change out md5. People started warning it was insecure in 1996, it was totally broken in 2005, and in 2012 the flame malware used it to hack computers.

JanisErdmanis 3y ago

It is! Taking into account that only the Schor algorithm is proven to be exponentially faster in factorising numbers and looking into current progress on using it, the threat for RSA 2048 will become real in ridiculous 2^2048 years. This can be estimated by taking three events in factorisation: 2002: factorisation of 15 [1] 2012: factorisation of 21 [2] 2022: factorisation of 35 by IBM (although the article is about number 21, but let’s give them credit) [3] In a plot, the tendency is somewhat linear, with the factorised number increasing by one every year. A sceptic immediately replies to this thread, saying we already have 100-1000 qubit quantum computers and are on the path to getting a million qubits in the foreseeable future. That may as well be true. The issue is that the Schoor algorithm requires that the error rate of the qubit operations scale exponentially with the number of qubits. This is why IBM only uses five qubits in [3], although they already had a hundred qubit QCs at that time. It just produces meaningless results when used with more qubits. This is also why the line for factorisation is about to be linear. If the error rate of the qubit operations decreases by 20% every year and we have exponential progress, the usefulness of the Schor algorithm taken on a log scale would be linear. The error correction is not a panacea either. It does not reduce errors to zero for logical qubits but rather reduces them after the error threshold is reached. It would require repeated application to get the necessary error threshold to run the Schor algorithm for a desired number, which would require an unreasonable number of qubits. [1]: https://www.nature.com/articles/414883a https://www.nature.com/articles/414883a [2]: https://www.nature.com/articles/nphoton.2012.259 https://www.nature.com/articles/nphoton.2012.259 [3]: https://arxiv.org/pdf/2103.13855v1.pdf https://arxiv.org/pdf/2103.13855v1.pdf

klabb3 3y ago
> The issue is that the Schoor algorithm requires that the error rate of the qubit operations scale exponentially with the number of qubits. So… traditional silicon computing scales exponentially in time, but QC computes in constant time(!) with the minor detail that it scales exponentially in error. > If the error rate of the qubit operations decreases by 20% every year and we have exponential progress, the usefulness of the Schor algorithm taken on a log scale would be linear. Right, which is exactly the type of leeway you need, no? 1-2 qubits per year will take many decades to break ECC or RSA. It’s the same Moores law-style assumptions baked into traditional computing getting faster. > This is why IBM only uses five qubits in [3], although they already had a hundred qubit QCs at that time. It just produces meaningless results when used with more qubits. So IBM has this really cool gf, but she’s at a different school so you won’t know her. Half joking, but putting error propagation in the footnotes seems very off to me as a complete layman. Like thinking we can accurately predict the weather 5 months out with a bit more compute.

bradleyjg 3y ago

I don’t expect commercially viable fusion, room temperature superconductors, or useful quantum computers in my lifetime. The jury is still out on real self driving cars, but I’m less optimistic than I was five years ago.

xhkkffbf 3y ago
A friend of mine uses a self-driving taxi service in SF all of the time.
- bradleyjg 3y ago
  How come you and all your other friends and family don’t? When do you think the rest of you will?
  - grayhatter 3y ago
    I'd say in half the amount of time it took for us to go from the first internal combustion engine to the Model T? Or if you think that's a bad comparison: The Model T to the honda civic?
    - bradleyjg 3y ago
      If that’s my odds are pretty good of living to see it. I hope you’re right.
  - xhkkffbf 3y ago
    Because I don't live in SF. So ask the companies when they'll deploy elsewhere.