Strilanc

That is not true. A spanning tree of physical links is sufficient to make a network where anyone can talk to anyone else.

The key ingredient here is entanglement swapping [1]. Entanglement between routers A and B can be merged with entanglement between routers B and C to form entanglement between A and C. This accumulates noise, but purification can be used at each merging step to push the noise back down to 1%.

So what transmitting a message looks like is a path between the two endpoints is selected and then entanglement swapping+purification is used to turn 1-hop entanglement into 2-hop entanglement, then into 4-hop, then etc until the entire path is spanned. Then purification+teleportation are used by the endpoints to move the message.

[1] https://en.wikipedia.org/wiki/Entanglement_swapping

The recommendation is to not use QKD. This is the correct recommendation. QKD solves key agreement if you have an authenticated line. But authentication is the harder more crucial problem.

Here's an interesting related aside: the likely design of a practical quantum internet would make QKD totally trivial. What a quantum internet would do is deliver kinda-noisy entangled Bell pairs to endpoints that wanted to communicate. The endpoints would then purify [1] this kinda-noisy entanglement into actually-good entanglement (e.g. from 1% error to 0.0000000000001% error). The purified Bell pairs can then be consumed in order to transmit qubits [2]. However, because of the monogamy of entanglement [3], the purification process must detect and correct eavesdropping (or else fail to produce output). So, once you have a sufficiently purified Bell pair, it can be measured to get a bit that can be used as a one time pad. (That said, this does still assume you have an authenticated channel! Purification requires communication, because without authentication you can be man-in-the-middle'd.)

[1] https://en.wikipedia.org/wiki/Entanglement_distillation

[2] https://en.wikipedia.org/wiki/Quantum_teleportation

[3] https://en.wikipedia.org/wiki/Monogamy_of_entanglement

The dominant cost in Shor's algorithm is the elliptic curve point addition subroutine. That subroutine can be implemented using reversible classical gates. For that kind of implementation, approximate correctness can be verified by fuzz testing classical trajectories through the subroutine.

Note you could ask the same question about Shor's original paper: how did he show the algorithm works without running it? Running X just isn't the only way to analyze X.

This was exactly the premise of my sigbovik April Fool's paper in 2025 [1]: for small numbers, Shor's algorithm succeeds quickly when fed random samples. And when your circuit is too long (given the error rate of the quantum computer), the quantum computer imitates a random number generator. So it's trivial to "do the right thing" and succeed for the wrong reason. It's one of the many things that make small factoring/ecdlp cases bad benchmarks for progress in quantum computing.

I warned the project11 people that this would happen. That they'd be awarding the bitcoin to whoever best obfuscated that the quantum computer was not contributing (likely including the submitter fooling themselves). I guess they didn't take it to heart.

[1] https://sigbovik.org/2025/proceedings.pdf#page=146

Good post. Entirely correct, and well known amongst quantum researchers, but under appreciated in general.

Grover attacks are very blatantly impractical. When someone describes Grover-type attacks in the same breath as Shor-type attacks, without caveats, that's a red flag.

That graph suggests that even with the best error correction in the graph, it is impossible to factor RSA-4 with less then 10^4 qubits. Which seems very odd.

It's because the plot is assuming the use of error correction even for the smallest cases. Error correction has minimum quantity and quality bars that you must clear in order for it to work at all, and most of the cost of breaking RSA4 is just clearing those bars. (You happen to be able to do RSA4 without error correction, as was done in 2001 [0], but it's kind of irrelevant because you need error correction to scale so results without it are on the wrong trendline. That's even more true for the annealing stuff Scott mentioned, which has absolutely no chance of scaling.)

You say you don't see the uranium piling up. Okay. Consider the historically reported lifetimes of classical bits stored using repetition codes on the UCSB->Google machines [1]. In 2014 the stored bit lived less than a second. In 2015 it lived less than a second. 2016? Less than a second. 2017? 2018? 2019? 2020? 2021? 2022? Yeah, less than a second. And this may not surprise you but yes, in 2023, it also lived less than a second. Then, in 2024... kaboom! It's living for hours [4].

You don't see the decreasing gate error rates [2]? The increasing capabilities [3]? The ever larger error correcting code demonstrations [4]? The front-loaded costs and exponential returns inherent to fault tolerance? TFA is absolutely correct: the time to start transitioning to PQC is now.

[0] https://www.nature.com/articles/414883a

[1] https://algassert.com/assets/2025-12-24-qec-foom/plot-half-l... (from https://algassert.com/post/2503 )

[2] https://arxiv.org/abs/2510.17286

[3] https://www.nature.com/articles/s41586-025-09596-6

[4] https://www.nature.com/articles/s41586-024-08449-y

The newest transaction mechanism (taproot; P2TR) exposes the public key of the receiver as part of the transaction. If it becomes more commonly used, the supply of bitcoins with exposed public keys would start going up again. See figure 5 of https://arxiv.org/pdf/2603.28846#page=14 .

The DoS attack in this scenario is someone just submitting reasonable-looking but ultimately bad precommitments as fast as possible. The intuition is that precommitments must be hard to validate because, if there was an easy validation mechanism, you would have just used that mechanism as the transaction mechanism. And so all these junk random precommitments look potentially legitimate and end up being stored for later verification. So all you have to do to take down the system is fill up the available storage with junk, which (given the size of bot networks and the cost of storing something for a day) seems very doable.

Yes, that would be a concern. You could require a proof of work to submit a precommitment, so that DoSing was at least expensive to do. You could have some sort of deposit mechanism, where a precommitment would lock down 0.1 bitcoins (from a quantum-secure wallet) until the precommitment was used. I admit I'm glad I don't have to figure out those details.

Caution: that 10M estimate assumes gate error rates 10x lower than the ones assumed in the papers from TFA.

You are assuming that progress on factoring will be smooth, but this is unlikely to be true. The scaling challenges of quantum computers are very front-loaded. I know this sounds crazy, but there is a sense in which the step from 15 to 21 is larger than the step from 21 to 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 (the RSA100 challenge number).

Consider the neutral atom proposal from TFA. They say they need tens of thousands of qubits to attack 256 bit keys. Existing machines have demonstrated six thousand atom qubits [1]. Since the size is ~halfway there, why haven't the existing machines broken 128 bit keys yet? Basically: because they need to improve gate fidelity and do system integration to combine together various pieces that have so far only been demonstrated separately and solve some other problems. These dense block codes have minimum sizes and minimum qubit qualities you must satisfy in order for the code to function. In that kind of situation, gradual improvement can take you surprisingly suddenly from "the dense code isn't working yet so I can't factor 21" to "the dense code is working great now, so I can factor RSA100". Probably things won't play out quite like that... but if your job is to be prepared for quantum attacks then you really need to worry about those kinds of scenarios.

[1] https://www.nature.com/articles/s41586-025-09641-4

This is for rescue, not for payment. Once you've moved the coins to quantum-secure wallet, the delay would no longer be needed.

...probably some people would be very inconvenienced by this. But not as inconvenienced as having the coins stolen or declared forever inaccessible.

The best proposal I have heard for rescuing P2SH wallets after cryptographically relevant quantum computers exist is to require vulnerable wallets to precommit to transactions a day ahead of time. The precommitment doesn't reveal the public key. When the public key must be exposed as part of the actual transaction, an attacker cannot redirect the transaction for at least one day because they don't have a valid precommitment to point to yet.

[0.1% gate error rate] is still wildly out of reach

This is false. When Fowler et al assumed 0.1% gate error rates would be reached for his estimates in 2012 [0], that was ostentatious. Now it's frankly a bit overly conservative. All the big architectures are approaching or surpassing 0.1% gate error rates.

From 2022 to 2024, the google team improved mean two qubit gate error rate from 0.6% [1] to 0.4% [2]. Quantinuum's Helios has a two qubit gate error rate of 0.08% [3]. IBM has Heron processors available on their cloud service with two qubit gate error rates ranging from 0.2% to 0.7% [4]. Neutral atom machines have demonstrated 0.5% gate error rates [5].

[0] https://arxiv.org/abs/1208.0928

[1]: fig 1c of https://arxiv.org/pdf/2207.06431

[2]: fig 1b of https://arxiv.org/pdf/2408.13687

[3] https://arxiv.org/abs/2511.05465

[4] https://quantum.cloud.ibm.com/computers?processorType=Heron (numbers may vary as the website is not static)

[5] https://arxiv.org/abs/2304.05420

Minor update: Dominik condensed the blog posts into a pre-print: https://arxiv.org/abs/2603.09901

That slide deck is complaining that correct work on quantum attacks should be seen as negligible priority or as distractions. TFA is complaining that JVG isn't even correct. They are pretty different concerns.

To be clear, I think that slide deck will be looked back upon as naive. In particular, it makes the classic mistake of assuming the size of number factored should be growing smoothly. That's naive because 15 is such a huge cost outlier and because quantum error correction has frontloaded costs. See [1] and [2] for details.

[1] https://algassert.com/post/2500

[2] https://algassert.com/post/2503

No, 15 is unique in that all multiplications by a known constant coprime to 15 correspond to bit rotations and/or bit flips. For 2047 that only occurs for a teeny tiny fraction of the selectable multipliers.

Shor's algorithm specifies that you should pick the base (which determines the multipliers) at random. Somehow picking a rare base that is cheap to do really does start overlapping with knowing the factors as part of making the circuit. By far the biggest cheat you can do is to "somehow" pick a number g such that g^2=1 (mod n) but g isn't 1 or N-1. Because that's exactly the number that Shor's algorithm is looking for, and the whole thing collapses into triviality.

What do you mean? The original 2019 supremacy experiment was eventually simulated, as better classical methods were found, but the followups are still holding strong (for example [4] and [5]). There was recently a series of blog posts by Dominik Hangleiter summarizing the situation: [1][2][3].

[1] https://quantumfrontiers.com/2026/01/06/has-quantum-advantag...

[2] https://quantumfrontiers.com/2026/01/25/has-quantum-advantag...

[3] https://quantumfrontiers.com/2026/02/28/what-is-next-in-quan...

[4] https://arxiv.org/abs/2303.04792

[5] https://arxiv.org/abs/2406.02501

What reviewers? It's not a peer reviewed article.

Agree. Scott is exactly correct when he just straight calls it crap.

It's inaccurate to say it wins on small numbers because on small numbers you would use classical computers. By the time you get to numbers that take more than a minute to factor classically, and start dreaming of quantum computers, you're well beyond the size where you could tractably do the proposed state preparation.

The very first demonstration of factoring 15 with a quantum computer, back in 2001, used a valid modular exponentiation circuit [1].

The trickiest part of the circuit is they compile conditional multiplication by 4 (mod 15) into two controlled swaps. That's a very elegant way to do the multiplication, but most modular multiplication circuits are much more complex. 15 is a huge outlier on the difficulty of actually doing the modular exponentiation. Which is why so far 15 is the only number that's been factored by a quantum computer while meeting the bar of "yes you have to actually do the modular exponentiation required by Shor's algorithm".

[1] https://arxiv.org/pdf/quant-ph/0112176#page=15

For each chick they do 24 trials divided into 4 blocks with retraining on the ambiguous shape and actual rewards after each block. During the actual tests they didn't give rewards. In figure 1 they show the data bucketed by trial index. It's a bit surprising it doesn't show any apparent effect vs trial number, e.g. the first trial after retraining being slightly different.

I have to admit I'm super skeptical there's not some stupid mistake here. Definitely thought provoking. But I wish they'd kept iteratively removing elements until the correlation stopped happening, so they could nail down causation more precisely.

Wasn't this study immediately debunked due to bad statistical methods? See https://zenodo.org/records/18002186

Using simple simulations,we show that this pattern arises naturally from collider bias when selection into elitesamples depends on both early and adult performance. Consequently, associationsestimated within elite samples are descriptively accurate for the selected population,but causally misleading, and should not be used to infer developmental mechanisms

By late 2024 the biggest numbers that had been factored by an actual digital quantum computer had 35 bits (citing https://arxiv.org/pdf/2410.14397v1 )

This is incorrect. The cited reference says "N <= 35". That N is the number being factored, not the number of bits in the number. Also, footnote a of that paper points out (correctly) that the circuits that were used likely needed knowledge of the factors to create (e.g. as explained in https://arxiv.org/abs/1301.7007 ). As far as I know, only N=15 has been factored on a quantum computer in a no-shenanigans way.

It's conceivable that current ion trap machines could do a no-shenanigans N=21.... but anyone judging progress in quantum computing by largest-number-factored is looking at the wrong metric (for now). You won't see that metric move meaningfully until quantum error correction is done spinning up.

It's fame comes from the simplicity of its construction rather than its utility elsewhere in mathematics.

For example, Graham's number is pretty famous but it's more of a historical artifact rather than a foundational building block. Other examples of non-foundational fame would be the famous integers 42, 69, and 420.

Yes, speed matters. No, quantum computers can't do everything instantly even with unbounded qubits.

A well studied example is that it's impossible to parallelize the steps in Grover's algorithm. To find a preimage amongst N possibilities, with only black box access, you need Ω(sqrt(N)) sequential steps on the quantum computer [1].

Another well known case is that there's no known way to execute a fault tolerant quantum circuit faster than its reaction depth (other than finding a rewrite that reduces the depth, such as replacing a ripple carry adder with a carry lookahead adder) [2]. There's no known way to make the reaction depth small in general.

Another example is GCD (greatest common divisor). It's conjectured to be an inherently sequential problem (no polylog depth classical circuit) and there's no known quantum circuit for GCD with lower depth than the classical circuits.

[1] https://arxiv.org/abs/quant-ph/9711070

[2] https://arxiv.org/abs/1210.4626

Author here: yes that's all correct.

This is perhaps not clear enough, but the title refers to a pattern. For classical bits on a quantum computer this pattern is already playing out (as shown in the cited experiments), and for quantum bits I think it's about to play out.

Classical storage of classical bits is still far more reliable, of course. Hell, a rock chucked into one bucket or another is still more reliable. We'll never beat the classical computer at storing classical bits... but the rock in a bucket has some harsh competition coming.

I should maybe also mention that arbitrarily good qubits are a step on the road, not the end. I've seen a few twitter takes making that incorrect extrapolation. We'll still need hundreds of these logical qubits. It's conceivable that quantity also jumps suddenly... but that'd require even more complex block codes to start working (not just surface codes). I'm way less sure if that will happen in the next five years.

Factoring will be okay for tracking progress later; it's just a bad benchmark now. Factoring benchmarks have little visibility into fault tolerance spinning up, which is the important progress right now. Factoring becoming a reasonable benchmark is strongly related to quantum computing becoming useful.

This is a type that I would use a lot.

For example, I often write classes that do cacheable analysis that results in a dict (e.g. the class stores a list of tiles defined by points and users want a point-to-tiles mapping for convenience). It's worth caching those transformations, e.g. using @functools.cached_property, but this introduces a risk where any caller could ruin the returned cached value by editing it. Currently, I take the safety hit (cache a dict) instead of the performance hit (make a new copy for each caller). Caching a frozendict would be a better tradeoff.

Well, for example, consider this recent study that claimed developers using AI tools take 19% longer to finish tasks [1].

This was their methodology:

we recruited 16 experienced developers from large open-source repositories (averaging 22k+ stars and 1M+ lines of code) that they’ve contributed to for multiple years. Developers provide lists of real issues (246 total) that would be valuable to the repository—bug fixes, features, and refactors that would normally be part of their regular work. Then, we randomly assign each issue to either allow or disallow use of AI while working on the issue.

Now consider the question of whether you expect this research to generalize. Do you expect that if you / your friends / your coworkers started using AI tools (or stopped using AI tools) that the difference in productivity would also be 19%? Of course not! They didn't look at enough people or contexts to get two sig figs of precision on that average, nor enough to expect the conclusion to generalize. Plus the AI tools are constantly changing, so even if the study was nailing the average productivity change it would be wrong a few months later. Plus the time period wasn't long enough for the people to build expertise, and "if I spend time getting good at this will it be worth it" is probably the real question we want answered. The study is so weak that I don't even feel compelled to trust the sign of their result to be predictive. And I would be saying the same thing if it reported 19% higher instead of 19% lower.

I don't want to be too harsh on the study authors; I have a hard time imagining any way to do better given resource constraints and real world practicalities... but that's kind of the whole problem with such studies. They're too small and too specific and that's really hard to fix. Honestly I think I'd trust five anecdotes at lunch more than most software studies (mainly because the anecdotes have the huge advantage of being from the same context I work in). Contrast with medical studies where I'd trust the studies over the anecdotes, because for all their flaws at least they actually put in the necessary resources.

To be pithy: maybe we upvote Carmack quotes more than software studies because Carmack quotes are informed by more written code than most software studies.

[1] https://metr.org/blog/2025-07-10-early-2025-ai-experienced-o...