5 ms·

Looking at some claims that quantum computers won't work

68 points by gjvc 2y ago

johnea 2y ago
Great to see DJB work posted here!
peepeepoopoo101 2y ago
There's an awful lot of handwaving in this blog post. I'm sorry, but I'm not convinced. The author mentions how some devices that can seemingly solve exponential time complexity problems also require exponentially high precision, but there doesn't seem to be a strong argument for why that doesn't apply to quantum computers. We haven't experimentally demonstrated quantum computing at sufficient scales to prove that the required number of physical qubits to perform error correction doesn't scale exponentially.
- rq1 2y ago
  The author is DJB.
  - sebmellen 2y ago
    For those not familiar: https://en.m.wikipedia.org/wiki/Daniel_J._Bernstein https://en.m.wikipedia.org/wiki/Daniel_J._Bernstein
- plumthreads 2y ago
  I got the impression that DJB was criticizing the arguments for why quantum computers won't work. Not trying to demonstrate why they will work.
  - gjvc 2y ago
    yup
- Yoric 2y ago
  Note that you do not need error correction for quantum computing. You only need it for digital quantum computing. There's a separate branch, analog quantum computing, that is also very promising.
  - Yoric 2y ago
    Does anybody want to elaborate why I'm being downvoted? For context, there are several companies selling analog quantum computers, e.g. Pasqal, D-Wave.
    - abdullahkhalids 2y ago
      What D-Wave has is not a quantum computer, in the sense that it (the computer architecture) can't solve BQP problems efficiently. They are widely considered shills by the quantum computing community.
- wzeng 2y ago
  We don’t need exponentially more physical qubits because we have quantum error correction schemes that exponentially decrease the logical error rate with only a polynomial increase in the number of qubits. There are in fact many schemes for this (https://errorcorrectionzoo.org/ https://errorcorrectionzoo.org/) with the surface code mentioned in the blog being a leading approach. Details for how this could work for factoring are here: https://arxiv.org/abs/1905.09749 https://arxiv.org/abs/1905.09749 There will be engineering challenges to scale up these implementations but in principal you shouldn’t need exponential resources (unless there is something wrong with quantum mechanics). This sort of error correction scaling does not exist, for example, for analog computing.
- gjvc 2y ago
  I think you've missed the point of it then.
deleted 2y ago
[deleted]
upofadown 2y ago
>Everything disintegrates for physical error rates around 1% or above Last I heard we were 1-2 orders of magnitude away from the error correction break even point for noise performance; that point where it would take an infinite number of noisy qubits to break 2048 bit RSA. So does this mean that we are still at an error rate of something like 10%?
- wzeng 2y ago
  Several approaches are better than the break even point today, including the Google demonstration of error correction working to reduce logical errors: https://www.nature.com/articles/s41586-024-08449-y https://www.nature.com/articles/s41586-024-08449-y There’s more citations to gate fidelity progress here: https://metriq.info/Task/38 https://metriq.info/Task/38
  - upofadown 2y ago
    Did the Google experiment actually hit break even? I got that it had only demonstrated that surface codes did what they were predicted to do. Is it really only a matter of creating more hardware at this point?
    - Strilanc 2y ago
      Yes it exceeded break even, but no you can't just copy paste hardware yet. For example, some kind of chip-to-chip coupling is needed since chips can't be arbitrarily large.
woodruffw 2y ago
> Cloudflare, which hosts a considerable fraction of the Internet's web sites, reports that 33% of its connections are using post-quantum crypto as of January 2025. DJB's narrative is a little selective here: Cloudflare has done some incredibly impressive things with post-quantum key agreement, which is arguably the "easy"[1] part of moving the Web PKI/TLS to a PQ setting. But key agreement doesn't tell the parties why they should trust each other; you need signatures and certificates for that, and those will need to be PQ-ready too. That part is much harder, for both technical (larger certificates implied by most PQ signing schemes are much harder to reliably convey over packet networks) and political (the X.509 ecosystem moves very slowly, and penetration of new signature schemes takes years) reasons. [1]: Nothing about it is easy.
- Azerty9999 2y ago
  Are you indicating that Cloudflare's implementation isn't truly fully post quantum secure because of lagging certificate standards/technology? Wanted to provide the source for your posting about 33% of Cloudflare TLS traffic having Post-Quantum Encryption as of Jan 2025 [1] [1] https://radar.cloudflare.com/adoption-and-usage#post-quantum-encryption-adoption https://radar.cloudflare.com/adoption-and-usage#post-quantum...
  - woodruffw 2y ago
    > Are you indicating that Cloudflare's implementation isn't truly fully post quantum secure because of lagging certificate standards/technology? Yes, although I wouldn't say "truly" because they haven't intimated that it is. I'm not claiming any malfeasance on Cloudflare's part: they have been very explicit about the fact that the PQ components deployed so far are only in the key exchange. Bas Westerbaan has a great post on the Cloudflare blog about the state of PQ in 2024.
- adgjlsfhk1 2y ago
  Certificates don't need to worry about store now decrypt later. As such, IIUC Cloudflare has another decade at least before they need to start worrying about this.
aaron695 2y ago
[dead]
AlexCoventry 2y ago
In the Scott Aaronson talk he links at the bottom[1], Prof. Aaronson says > A fourth reason why people didn’t take QC seriously is that, a century after the discovery of QM, some people still harbor doubts about quantum mechanics itself... Or they say things like, “complex Hilbert space in 2^n dimensions is a nice mathematical formalism, but mathematical formalism is not reality”—the kind of thing you say when you want to doubt, but not take full intellectual responsibility for your doubts. How is that a failure to take intellectual responsibility? (Asking because it's basically what I think[2], but I promise not to argue with any explanation given here. :-) [1] https://scottaaronson.blog/?p=8329 https://scottaaronson.blog/?p=8329 [2] https://news.ycombinator.com/item?id=42374112 https://news.ycombinator.com/item?id=42374112
- deleted 2y ago
  [deleted]
- ano-ther 2y ago
  I am not Scott Aaronson, but probably because that statement is not making any effort to analyze how Hilbert is connected to reality and how where why that connection breaks down.
- didgeoridoo 2y ago
  Isn’t that kind of like saying “complex numbers are a nice formalism, but only the reals actually exist”? What does “reality” mean, in this context?
  - AlexCoventry 2y ago
    "Reality" in this case would be a cryptographically relevant Quantum Computer, as predicted by current Quantum Mechanical calculations which use these 2^n-dimensional Hilbert Spaces he mentions.
- cvoss 2y ago
  One should investigate closely the connection between (well-supported) theories of physics and "reality", which, I gather, in this case means something like "the ontology of the universe". Is the universe "actually made of" a flexible substance that moves according to the equations of GR? In one sense, it doesn't matter. It acts like it does, and so well that we can make very precise predictions about what will happen. Suppose a naysayer in 2010 said "Well, GR is a nice mathematical formalism, but mathematical formalism isn't reality. It's preposterous to think space is actually made of this mysterious flexible substance. You'll never see gravitational waves. It's a fiction of the math." The naysayer has conflated the claim "GR is ontologically true" with the claim "GR makes accurate predictions." The first is irrelevant, and may be freely denied without casting meaningful doubt on the second, which has been well-tested for a century. It would be a great surprise to conduct an experiment and learn that GR mispredicted the result. QM predicts QC. To doubt QC is to doubt that QM accurately predicts experiments we can conduct. In this case, once again, a century of experiments cuts the other direction. The failure of QC would be the surprise, not its success.
charlieyu1 2y ago
Afaik we still haven’t factorised 35 using Shor’s Algorithm, I really don’t understand the current hype
- Azerty9999 2y ago
  Maybe it's marketing, but there seem to be some advances [1] [1] https://blog.google/technology/research/google-willow-quantum-chip/ https://blog.google/technology/research/google-willow-quantu...
- didgeoridoo 2y ago
  Perhaps 35 is prime? We may never know.
  - Terr_ 2y ago
    "Whelllp, it turns out that quantum primes aren't the same as classical primes, who'da thunk it?"
- jncfhnb 2y ago
  4 should be enough for anybody.
- upofadown 2y ago
  There is some thought that we haven't factored anything yet via Shor's. The previous demonstrations assumed the results in their construction.
- __turbobrew__ 2y ago
  Yea that is a missing part from the argument. It is said that we should judge QC by the advances it has made and not if it can break the latest algos. Well what is the progress then? How has QC advanced in the past 20 years, what is the latest QC can do?
  - adgjlsfhk1 2y ago
    Qbits and error rates have both improved by a few orders of magnitude. Google's paper from August is the first demonstration of error correction. We're probably ~5 years away from doing toy examples of Shor's algorithm with error correction, and ~20 from being able to factor numbers as big as a classical computer.
liuliu 2y ago
What about the Bitcoin argument? If CRQC is built, given that you only needs ~1000 logic qubits (and probably fewer gates than RSA) for ECDSA, you would expect big financial incentive to just use the compute a little bit to crack a few cold wallets. (After all, leaking classified information to the press is much easier to be caught than cracking wallets). And we will notice this breakthrough almost immediately if not within a few weeks.
- benlivengood 2y ago
  Most cold wallet addresses with a balance have never signed a transaction. This keeps the public key secret behind sha256 hashes which don't fall to quantum computing (128 bits of security with quantum search).
teleforce 2y ago
> I coined the phrase "post-quantum cryptography" in 2003 It's interesting to note that according to DJB he's the first person to coin the term "post-quantum cryptography". It's also interesting to note that after several years of open evaluation processes by NIST (similar process to how AES was selected), 3 post-quantum cryptographic algorithms have been short-listed for potential post-quantum encryption standards [1]. What is more interesting to note that the link [1] had been submitted 8 times previously by 8 different persons without any comments from HN (all 0 comments), it's sadly obvious that the subject is not interesting enough for HN crowds. [1] NIST Releases First 3 Finalized Post-Quantum Encryption Standards (2024): https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards https://www.nist.gov/news-events/news/2024/08/nist-releases-...
nitwit005 2y ago
The unstated argument here seems to be that some secret government project might succeed, even as the public quantum computing efforts struggle. I suppose, but in that case it's almost certain it was based on some novel concept, in which case we have no idea how to defend against it.
1vuio0pswjnm7 2y ago
"If you're using Linux as a sysadmin or on the desktop, try our new easy-to-install PQConnect tool, which wraps end-to-end post-quantum cryptography around unmodified applications." Long before NaCl was adopted in popular software projects, at the end of one his talks, djb promised an stunnel-like program that used NaCl. Would be nice to have an stunnel-like program using libmcliece.
rstuart4133 2y ago
Quoting from TFA: > the normal mathematical description of the state of n qubits involves 2n variables. For example, for 4 qubits, there are 16 variables: v[0000], v[0001], v[0010], and so on through v[1111]. ... The variables always have these squares adding up to 1, so the total probability is 1 as you'd expect. ^blink^ Why did I not know this? I've read many explanations of quantum mechanics, qubits, entanglement and I've never twigged to this drop dead simple model of what is going on. It gets better. His linked description of how a quantum works [0] is so simple a 5 year could understand it. But it raises so many questions. A quantum computer is entangled group of qubits, right? So does that mean it gets it's speed because a time it takes gate to operate on N qubits doesn't depend on N? Is that somehow related to "spooky action at a distance" - meaning it doesn't matter how much distance separates two entangled particles, they instantaneously collapse to state consistent with the laws of the universe? Probably not, because that would make faster than light information exchange possible. Just separate break an entangled group of qubits into two, separate them, then push them though a few gates to put them in a state that favours one outcome over the other. So one puzzle solved, but it just reveals how much more I don't know.

68 points by gjvc 2y ago

Great to see DJB work posted here!

There's an awful lot of handwaving in this blog post. I'm sorry, but I'm not convinced. The author mentions how some devices that can seemingly solve exponential time complexity problems also require exponentially high precision, but there doesn't seem to be a strong argument for why that doesn't apply to quantum computers. We haven't experimentally demonstrated quantum computing at sufficient scales to prove that the required number of physical qubits to perform error correction doesn't scale exponentially.

rq1 2y ago
The author is DJB.
- sebmellen 2y ago
  For those not familiar: https://en.m.wikipedia.org/wiki/Daniel_J._Bernstein https://en.m.wikipedia.org/wiki/Daniel_J._Bernstein
plumthreads 2y ago
I got the impression that DJB was criticizing the arguments for why quantum computers won't work. Not trying to demonstrate why they will work.
- gjvc 2y ago
  yup
Yoric 2y ago
Note that you do not need error correction for quantum computing. You only need it for digital quantum computing. There's a separate branch, analog quantum computing, that is also very promising.
- Yoric 2y ago
  Does anybody want to elaborate why I'm being downvoted? For context, there are several companies selling analog quantum computers, e.g. Pasqal, D-Wave.
  - abdullahkhalids 2y ago
    What D-Wave has is not a quantum computer, in the sense that it (the computer architecture) can't solve BQP problems efficiently. They are widely considered shills by the quantum computing community.
wzeng 2y ago
We don’t need exponentially more physical qubits because we have quantum error correction schemes that exponentially decrease the logical error rate with only a polynomial increase in the number of qubits. There are in fact many schemes for this (https://errorcorrectionzoo.org/ https://errorcorrectionzoo.org/) with the surface code mentioned in the blog being a leading approach. Details for how this could work for factoring are here: https://arxiv.org/abs/1905.09749 https://arxiv.org/abs/1905.09749 There will be engineering challenges to scale up these implementations but in principal you shouldn’t need exponential resources (unless there is something wrong with quantum mechanics). This sort of error correction scaling does not exist, for example, for analog computing.
gjvc 2y ago
I think you've missed the point of it then.

deleted 2y ago

[deleted]

upofadown 2y ago

>Everything disintegrates for physical error rates around 1% or above Last I heard we were 1-2 orders of magnitude away from the error correction break even point for noise performance; that point where it would take an infinite number of noisy qubits to break 2048 bit RSA. So does this mean that we are still at an error rate of something like 10%?

wzeng 2y ago
Several approaches are better than the break even point today, including the Google demonstration of error correction working to reduce logical errors: https://www.nature.com/articles/s41586-024-08449-y https://www.nature.com/articles/s41586-024-08449-y There’s more citations to gate fidelity progress here: https://metriq.info/Task/38 https://metriq.info/Task/38
- upofadown 2y ago
  Did the Google experiment actually hit break even? I got that it had only demonstrated that surface codes did what they were predicted to do. Is it really only a matter of creating more hardware at this point?
  - Strilanc 2y ago
    Yes it exceeded break even, but no you can't just copy paste hardware yet. For example, some kind of chip-to-chip coupling is needed since chips can't be arbitrarily large.

woodruffw 2y ago

> Cloudflare, which hosts a considerable fraction of the Internet's web sites, reports that 33% of its connections are using post-quantum crypto as of January 2025. DJB's narrative is a little selective here: Cloudflare has done some incredibly impressive things with post-quantum key agreement, which is arguably the "easy"[1] part of moving the Web PKI/TLS to a PQ setting. But key agreement doesn't tell the parties why they should trust each other; you need signatures and certificates for that, and those will need to be PQ-ready too. That part is much harder, for both technical (larger certificates implied by most PQ signing schemes are much harder to reliably convey over packet networks) and political (the X.509 ecosystem moves very slowly, and penetration of new signature schemes takes years) reasons. [1]: Nothing about it is easy.

Azerty9999 2y ago
Are you indicating that Cloudflare's implementation isn't truly fully post quantum secure because of lagging certificate standards/technology? Wanted to provide the source for your posting about 33% of Cloudflare TLS traffic having Post-Quantum Encryption as of Jan 2025 [1] [1] https://radar.cloudflare.com/adoption-and-usage#post-quantum-encryption-adoption https://radar.cloudflare.com/adoption-and-usage#post-quantum...
- woodruffw 2y ago
  > Are you indicating that Cloudflare's implementation isn't truly fully post quantum secure because of lagging certificate standards/technology? Yes, although I wouldn't say "truly" because they haven't intimated that it is. I'm not claiming any malfeasance on Cloudflare's part: they have been very explicit about the fact that the PQ components deployed so far are only in the key exchange. Bas Westerbaan has a great post on the Cloudflare blog about the state of PQ in 2024.
adgjlsfhk1 2y ago
Certificates don't need to worry about store now decrypt later. As such, IIUC Cloudflare has another decade at least before they need to start worrying about this.

aaron695 2y ago

[dead]

AlexCoventry 2y ago

In the Scott Aaronson talk he links at the bottom[1], Prof. Aaronson says > A fourth reason why people didn’t take QC seriously is that, a century after the discovery of QM, some people still harbor doubts about quantum mechanics itself... Or they say things like, “complex Hilbert space in 2^n dimensions is a nice mathematical formalism, but mathematical formalism is not reality”—the kind of thing you say when you want to doubt, but not take full intellectual responsibility for your doubts. How is that a failure to take intellectual responsibility? (Asking because it's basically what I think[2], but I promise not to argue with any explanation given here. :-) [1] https://scottaaronson.blog/?p=8329 https://scottaaronson.blog/?p=8329 [2] https://news.ycombinator.com/item?id=42374112 https://news.ycombinator.com/item?id=42374112

deleted 2y ago
[deleted]
ano-ther 2y ago
I am not Scott Aaronson, but probably because that statement is not making any effort to analyze how Hilbert is connected to reality and how where why that connection breaks down.
didgeoridoo 2y ago
Isn’t that kind of like saying “complex numbers are a nice formalism, but only the reals actually exist”? What does “reality” mean, in this context?
- AlexCoventry 2y ago
  "Reality" in this case would be a cryptographically relevant Quantum Computer, as predicted by current Quantum Mechanical calculations which use these 2^n-dimensional Hilbert Spaces he mentions.
cvoss 2y ago
One should investigate closely the connection between (well-supported) theories of physics and "reality", which, I gather, in this case means something like "the ontology of the universe". Is the universe "actually made of" a flexible substance that moves according to the equations of GR? In one sense, it doesn't matter. It acts like it does, and so well that we can make very precise predictions about what will happen. Suppose a naysayer in 2010 said "Well, GR is a nice mathematical formalism, but mathematical formalism isn't reality. It's preposterous to think space is actually made of this mysterious flexible substance. You'll never see gravitational waves. It's a fiction of the math." The naysayer has conflated the claim "GR is ontologically true" with the claim "GR makes accurate predictions." The first is irrelevant, and may be freely denied without casting meaningful doubt on the second, which has been well-tested for a century. It would be a great surprise to conduct an experiment and learn that GR mispredicted the result. QM predicts QC. To doubt QC is to doubt that QM accurately predicts experiments we can conduct. In this case, once again, a century of experiments cuts the other direction. The failure of QC would be the surprise, not its success.

charlieyu1 2y ago

Afaik we still haven’t factorised 35 using Shor’s Algorithm, I really don’t understand the current hype

Azerty9999 2y ago
Maybe it's marketing, but there seem to be some advances [1] [1] https://blog.google/technology/research/google-willow-quantum-chip/ https://blog.google/technology/research/google-willow-quantu...
didgeoridoo 2y ago
Perhaps 35 is prime? We may never know.
- Terr_ 2y ago
  "Whelllp, it turns out that quantum primes aren't the same as classical primes, who'da thunk it?"
jncfhnb 2y ago
4 should be enough for anybody.
upofadown 2y ago
There is some thought that we haven't factored anything yet via Shor's. The previous demonstrations assumed the results in their construction.
__turbobrew__ 2y ago
Yea that is a missing part from the argument. It is said that we should judge QC by the advances it has made and not if it can break the latest algos. Well what is the progress then? How has QC advanced in the past 20 years, what is the latest QC can do?
- adgjlsfhk1 2y ago
  Qbits and error rates have both improved by a few orders of magnitude. Google's paper from August is the first demonstration of error correction. We're probably ~5 years away from doing toy examples of Shor's algorithm with error correction, and ~20 from being able to factor numbers as big as a classical computer.

liuliu 2y ago

What about the Bitcoin argument? If CRQC is built, given that you only needs ~1000 logic qubits (and probably fewer gates than RSA) for ECDSA, you would expect big financial incentive to just use the compute a little bit to crack a few cold wallets. (After all, leaking classified information to the press is much easier to be caught than cracking wallets). And we will notice this breakthrough almost immediately if not within a few weeks.

benlivengood 2y ago
Most cold wallet addresses with a balance have never signed a transaction. This keeps the public key secret behind sha256 hashes which don't fall to quantum computing (128 bits of security with quantum search).

teleforce 2y ago

> I coined the phrase "post-quantum cryptography" in 2003 It's interesting to note that according to DJB he's the first person to coin the term "post-quantum cryptography". It's also interesting to note that after several years of open evaluation processes by NIST (similar process to how AES was selected), 3 post-quantum cryptographic algorithms have been short-listed for potential post-quantum encryption standards [1]. What is more interesting to note that the link [1] had been submitted 8 times previously by 8 different persons without any comments from HN (all 0 comments), it's sadly obvious that the subject is not interesting enough for HN crowds. [1] NIST Releases First 3 Finalized Post-Quantum Encryption Standards (2024): https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards https://www.nist.gov/news-events/news/2024/08/nist-releases-...

nitwit005 2y ago

The unstated argument here seems to be that some secret government project might succeed, even as the public quantum computing efforts struggle. I suppose, but in that case it's almost certain it was based on some novel concept, in which case we have no idea how to defend against it.

1vuio0pswjnm7 2y ago

"If you're using Linux as a sysadmin or on the desktop, try our new easy-to-install PQConnect tool, which wraps end-to-end post-quantum cryptography around unmodified applications." Long before NaCl was adopted in popular software projects, at the end of one his talks, djb promised an stunnel-like program that used NaCl. Would be nice to have an stunnel-like program using libmcliece.

rstuart4133 2y ago

Quoting from TFA: > the normal mathematical description of the state of n qubits involves 2n variables. For example, for 4 qubits, there are 16 variables: v[0000], v[0001], v[0010], and so on through v[1111]. ... The variables always have these squares adding up to 1, so the total probability is 1 as you'd expect. ^blink^ Why did I not know this? I've read many explanations of quantum mechanics, qubits, entanglement and I've never twigged to this drop dead simple model of what is going on. It gets better. His linked description of how a quantum works [0] is so simple a 5 year could understand it. But it raises so many questions. A quantum computer is entangled group of qubits, right? So does that mean it gets it's speed because a time it takes gate to operate on N qubits doesn't depend on N? Is that somehow related to "spooky action at a distance" - meaning it doesn't matter how much distance separates two entangled particles, they instantaneously collapse to state consistent with the laws of the universe? Probably not, because that would make faster than light information exchange possible. Just separate break an entangled group of qubits into two, separate them, then push them though a few gates to put them in a state that favours one outcome over the other. So one puzzle solved, but it just reveals how much more I don't know.