> 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.
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.
The update cycle for root trust programs is extremely long, especially if you care about anything older than the newest, most consistently up-to-date systems. So it's a "now" issue, insofar as it won't be a problem for at least another decade.
> 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.
DJB is not being "selective", instead you're nitpicking on something tangential to the point he's trying to make and creating the impression that what you wrote detracts from his point when that's definitely not the case.
His point in this section is that people are incorrectly or unreasonably claiming that PQC adoption in hard.
He uses Cloudflare's 33% number as counterevidence against it being hard, and I'm pointing out how this is a selective argument: it was "easy" because nobody, Cloudflare included, considers just PQ key exchange to be a full adoption of PQC. The full adoption requires asymmetric PQC and a corresponding re-imagining of how to encapsulate much larger public keys over the Internet, which is decidedly not easy.
(I don't have opinions on whether QC "won't work" or not; I think it's good to pursue PQC regardless, since we should have more "hard" primitives that don't decompose to the hidden subgroup problem.)
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. :-)
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.
I don't think what Aaronson says is fair and it's very easy (and kinda rude) way to dismiss an opinion you don't agree with, but also I don't think it applies to your post. You are questioning the implementation, it seems, he says that there are people who doubt the theory is correct in the first place. 17th century physics didn't predict the existence of that sphere of yours, and it's a very practical question if such sphere could be manufactured or not (and it could've turned out either way with given priors).
Instead, what Aaronson refers to is probably more like people saying "planets moving in epicycles are a nice mathematical formalism, but mathematical formalism is not reality" — you know, the kind of thing you say when you want to doubt, but not take full intellectual responsibility for your doubts...
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.
A very simple argument is that there's strong reasons to believe that energy is required to represent all information in the physical universe. You can't have "states" without mass/energy storing that state somewhere.
2^n is clearly super-linear in 'n', so as you scale to many particles, the equations suggest that you'd need a ludicrously huge state space, which requires a matching amount of energy to store. Clearly, this is not what happens, increasing the mass/energy of a system 10x doesn't result in 2^10 = 1024x as much mass/energy. You get 10x, plus or minus a correction for binding energy, GR, or whatever.
Quantum Computing is firmly based on pretending that this isn't how it is, that somehow you can squeeze 2^n bits of information out of a system with 'n' parts to it.
The ever increasing difficulties with noise, etc... indicate that no, there's no free lunch here, no matter how long we stand in the queue with an empty tray.
> there's strong reasons to believe that energy is required to represent all information in the physical universe
You simply do not need to believe this. The universe doesn't need to be "stored" somewhere.
> Quantum Computing is firmly based on pretending that this isn't how it is, that somehow you can squeeze 2^n bits of information out of a system with 'n' parts to it.
Quantum computing does not believe this. It is a theorem that you can only get n bits out of n qubits, and quantum computing speedups do not rely otherwise.
Noise is hard, but error correction is a mathematically sound response.
> The universe doesn't need to be "stored" somewhere.
Information that can have any effect on anything physical must have an energy associated with it, because that's basically the definition of energy: the property of physical systems that can cause change over time. No energy, no change in state. These are practically axioms.
Information that has zero energy can have only zero effect on observables in (our) universe.
> It is a theorem that you can only get n bits out of n qubits, and quantum computing speedups do not rely otherwise.
I'm pretty sure you've misunderstood something somewhere, because the 2^n states represented by n qubits is mentioned in practically all QC materials.
[2] is an awesome thought — that a nearly perfect sphere might be required for some calculation; it seems reasonable as a requirement — but isn’t, actually. And that Shor’s algorithm might have a similar impracticality we don’t presently appreciate.
Reminds me of this way in which laser interference patterns can be used to find primes. But, like many analog computing situations, it requires a degree of sensitivity to signal vs noise that is essentially impossible.
> How is that a failure to take intellectual responsibility?
The argument is metaphysical, it doesn't pose any concrete questions about the validity of QM, which would go like "does QM predicts reality correctly". All the physics is built upon a nice mathematical formalism of real numbers, and it doesn't make physics invalid, it can be used to build planes and computers, despite those pesky real numbers, that are unreal.
Intellectual responsibility means that you filled your metaphysics with some substance. I don't really know, how to do it for quantum mechanics, but if I wanted to, I might start with the inability of QM to explain gravity, I'd dig this topic to the point when I would be able to propose a specific way how research on quantum gravity could overturn QM and make it wrong. Or at least I'd try to make an argument that QM predictions about QC might become false.
But I cannot make such arguments, because I don't know QM, and I'm not going to dive into it, because I know better ways to spend my time, so I'll keep my mouth shut and will not voice vague statements about QM being not reality.
In any case from metaphysical standpoint, I'm sure that physics is not reality, physics is a mathematical description of reality. It doesn't matter if this description is incomplete or even wrong if it works for our case. Like Newton's gravity still works, while being proved wrong. We just need to bear in mind the limits of applicability. So I see the argument Scott Aaronson discusses as a very general truth "a map is not territory" which is used in an incorrect way. The correct (intellectually responsible) way is to point to the limits of applicability and to build an argument that they can bite.
> Asking because it's basically what I think[2]
I had followed your link after I wrote the first part, and I was delighted to see that you targeted the limits of applicability. Your argument is different from just saying "mathematical formalism is not reality".
I cannot verify your thoughts, because I don't know QM or how QC are supposed to work, but you are talking about the limits of applicability: "a theoretically-capable Quantum Computer will be testing the predictions of Quantum Mechanics to a degree of precision hundreds of orders of magnitude greater than any physics experiment to date". It doesn't seem to me as intellectual irresponsibility, it is not intellectual irresponsibility if you really know what you a talking about and can defend your statement when talking with PhD in QM.
> but I promise not to argue with any explanation given here.
Feel free to argue, I have nothing against it. :)
BTW, do you don't take QC seriously because of that? Do you expect QM (as a theory) to fail as a result or R&D work that is done on QC? I agree that there is a probability of QM failing, but my uneducated guess that the probability is low enough (maybe 0.1?) to take QC seriously.
"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.
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.
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/) with the surface code mentioned in the blog being a leading approach.
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.
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.
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.
I don't think this is useful distinction nowadays. If Willow demonstrated RCS within 100-qubit, I don't really think there are physical limitations for them to implement Shor for 50-bit integer numbers. It is just less impressive so they are probably saving that work until 1000-qubit achieved in a few years.
Shor requires very good qubits to work, with a very low error rate. When someone will have a QC good enough to actually run it, even for small numbers, they will be screaming from the rooftops about it.
Willow has only ~99.7% 2-qubit gate fidelity and poor connectivity. This is many orders of magnitude too low to run Shor's algorithm for a 50-bit number. The improvement has also stalled quite a bit over the last years (in 2019 they had 99.5% fidelities with similar qubit numbers).
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.
"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.
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.
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).
>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%?
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
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?
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.
> 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):
> 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.
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.
The update cycle for root trust programs is extremely long, especially if you care about anything older than the newest, most consistently up-to-date systems. So it's a "now" issue, insofar as it won't be a problem for at least another decade.
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...
> 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.
DJB is not being "selective", instead you're nitpicking on something tangential to the point he's trying to make and creating the impression that what you wrote detracts from his point when that's definitely not the case.
His point in this section is that people are incorrectly or unreasonably claiming that PQC adoption in hard.
He uses Cloudflare's 33% number as counterevidence against it being hard, and I'm pointing out how this is a selective argument: it was "easy" because nobody, Cloudflare included, considers just PQ key exchange to be a full adoption of PQC. The full adoption requires asymmetric PQC and a corresponding re-imagining of how to encapsulate much larger public keys over the Internet, which is decidedly not easy.
(I don't have opinions on whether QC "won't work" or not; I think it's good to pursue PQC regardless, since we should have more "hard" primitives that don't decompose to the hidden subgroup problem.)
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
[2] https://news.ycombinator.com/item?id=42374112
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.
So the GR guy would have been wrong, but how would he be failing to take intellectual responsibility?
GR guy reply sounds to me like hand-waving objections without offering any testable alternative.
I don't think what Aaronson says is fair and it's very easy (and kinda rude) way to dismiss an opinion you don't agree with, but also I don't think it applies to your post. You are questioning the implementation, it seems, he says that there are people who doubt the theory is correct in the first place. 17th century physics didn't predict the existence of that sphere of yours, and it's a very practical question if such sphere could be manufactured or not (and it could've turned out either way with given priors).
Instead, what Aaronson refers to is probably more like people saying "planets moving in epicycles are a nice mathematical formalism, but mathematical formalism is not reality" — you know, the kind of thing you say when you want to doubt, but not take full intellectual responsibility for your doubts...
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.
> complex Hilbert space in 2^n dimensions
A very simple argument is that there's strong reasons to believe that energy is required to represent all information in the physical universe. You can't have "states" without mass/energy storing that state somewhere.
2^n is clearly super-linear in 'n', so as you scale to many particles, the equations suggest that you'd need a ludicrously huge state space, which requires a matching amount of energy to store. Clearly, this is not what happens, increasing the mass/energy of a system 10x doesn't result in 2^10 = 1024x as much mass/energy. You get 10x, plus or minus a correction for binding energy, GR, or whatever.
Quantum Computing is firmly based on pretending that this isn't how it is, that somehow you can squeeze 2^n bits of information out of a system with 'n' parts to it.
The ever increasing difficulties with noise, etc... indicate that no, there's no free lunch here, no matter how long we stand in the queue with an empty tray.
> there's strong reasons to believe that energy is required to represent all information in the physical universe
You simply do not need to believe this. The universe doesn't need to be "stored" somewhere.
> Quantum Computing is firmly based on pretending that this isn't how it is, that somehow you can squeeze 2^n bits of information out of a system with 'n' parts to it.
Quantum computing does not believe this. It is a theorem that you can only get n bits out of n qubits, and quantum computing speedups do not rely otherwise.
Noise is hard, but error correction is a mathematically sound response.
> The universe doesn't need to be "stored" somewhere.
Information that can have any effect on anything physical must have an energy associated with it, because that's basically the definition of energy: the property of physical systems that can cause change over time. No energy, no change in state. These are practically axioms.
Information that has zero energy can have only zero effect on observables in (our) universe.
> It is a theorem that you can only get n bits out of n qubits, and quantum computing speedups do not rely otherwise.
I'm pretty sure you've misunderstood something somewhere, because the 2^n states represented by n qubits is mentioned in practically all QC materials.
[2] is an awesome thought — that a nearly perfect sphere might be required for some calculation; it seems reasonable as a requirement — but isn’t, actually. And that Shor’s algorithm might have a similar impracticality we don’t presently appreciate.
Reminds me of this way in which laser interference patterns can be used to find primes. But, like many analog computing situations, it requires a degree of sensitivity to signal vs noise that is essentially impossible.
> How is that a failure to take intellectual responsibility?
The argument is metaphysical, it doesn't pose any concrete questions about the validity of QM, which would go like "does QM predicts reality correctly". All the physics is built upon a nice mathematical formalism of real numbers, and it doesn't make physics invalid, it can be used to build planes and computers, despite those pesky real numbers, that are unreal.
Intellectual responsibility means that you filled your metaphysics with some substance. I don't really know, how to do it for quantum mechanics, but if I wanted to, I might start with the inability of QM to explain gravity, I'd dig this topic to the point when I would be able to propose a specific way how research on quantum gravity could overturn QM and make it wrong. Or at least I'd try to make an argument that QM predictions about QC might become false.
But I cannot make such arguments, because I don't know QM, and I'm not going to dive into it, because I know better ways to spend my time, so I'll keep my mouth shut and will not voice vague statements about QM being not reality.
In any case from metaphysical standpoint, I'm sure that physics is not reality, physics is a mathematical description of reality. It doesn't matter if this description is incomplete or even wrong if it works for our case. Like Newton's gravity still works, while being proved wrong. We just need to bear in mind the limits of applicability. So I see the argument Scott Aaronson discusses as a very general truth "a map is not territory" which is used in an incorrect way. The correct (intellectually responsible) way is to point to the limits of applicability and to build an argument that they can bite.
> Asking because it's basically what I think[2]
I had followed your link after I wrote the first part, and I was delighted to see that you targeted the limits of applicability. Your argument is different from just saying "mathematical formalism is not reality".
I cannot verify your thoughts, because I don't know QM or how QC are supposed to work, but you are talking about the limits of applicability: "a theoretically-capable Quantum Computer will be testing the predictions of Quantum Mechanics to a degree of precision hundreds of orders of magnitude greater than any physics experiment to date". It doesn't seem to me as intellectual irresponsibility, it is not intellectual irresponsibility if you really know what you a talking about and can defend your statement when talking with PhD in QM.
> but I promise not to argue with any explanation given here.
Feel free to argue, I have nothing against it. :)
BTW, do you don't take QC seriously because of that? Do you expect QM (as a theory) to fail as a result or R&D work that is done on QC? I agree that there is a probability of QM failing, but my uneducated guess that the probability is low enough (maybe 0.1?) to take QC seriously.
Thanks for your thoughtful and kind reply.
> BTW, do you don't take QC seriously because of that?
Not as a threat to real-world cryptography, but I do take it seriously as a scientific endeavor.
> Do you expect QM (as a theory) to fail as a result
Yes, similar to how Newtonian Mechanics fails at high precision or in extreme circumstances.
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?
"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.
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.
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.
yup
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/) 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
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.
The author is DJB.
For those not familiar: https://en.m.wikipedia.org/wiki/Daniel_J._Bernstein
I think you've missed the point of it then.
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.
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.
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.
Afaik we still haven’t factorised 35 using Shor’s Algorithm, I really don’t understand the current hype
Perhaps 35 is prime? We may never know.
"Whelllp, it turns out that quantum primes aren't the same as classical primes, who'da thunk it?"
There is some thought that we haven't factored anything yet via Shor's. The previous demonstrations assumed the results in their construction.
I don't think this is useful distinction nowadays. If Willow demonstrated RCS within 100-qubit, I don't really think there are physical limitations for them to implement Shor for 50-bit integer numbers. It is just less impressive so they are probably saving that work until 1000-qubit achieved in a few years.
Shor requires very good qubits to work, with a very low error rate. When someone will have a QC good enough to actually run it, even for small numbers, they will be screaming from the rooftops about it.
Willow has only ~99.7% 2-qubit gate fidelity and poor connectivity. This is many orders of magnitude too low to run Shor's algorithm for a 50-bit number. The improvement has also stalled quite a bit over the last years (in 2019 they had 99.5% fidelities with similar qubit numbers).
Maybe it's marketing, but there seem to be some advances [1]
[1] https://blog.google/technology/research/google-willow-quantu...
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?
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.
4 should be enough for anybody.
"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.
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.
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).
>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%?
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
There’s more citations to gate fidelity progress here: https://metriq.info/Task/38
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?
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.
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.
Great to see DJB work posted here!
> 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-...
[dead]