Strilanc

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...

> The precision in phase needed to perform an accurate QFT scales EXPONENTIALLY with the number of qubits you're trying to transform.

This is false.

The gates that appear in the textbook QFT circuit (such as the one shown on wikipedia [1]) do mention angles that are exponentially small in N (the number of qubits being operated upon). That may be what's confusing you. But it's well known that the tolerance on those rotations is high, meaning that simply skipping all the exponentially tiny rotations introduces negligible error [2][3].

Here's a simple model. Each time you get a rotation off by an angle of X, add X to the "total algorithm rotation error" R. The chance of an algorithm failing is at most R^2. For example, if R is less than 1 degree then the chance of algorithm failure will be less than 0.03%. That's an acceptable retry chance for Shor's algorithm. The QFT circuit on N qubits performs less than N^2 rotations. So, for R to be less than 1 degree, it's sufficient for each rotation's error X to be less than (1°)/N^2. Therefore the required precision only increases polynomially (like N^2) instead of exponentially (like 2^N). Note the required precision can be improved from O(1/N^2) to O(1/N) using techniques like the qubit recycling QFT [4].

Actually, even if the required precision scaled exponentially, that still wouldn't be an insurmountable problem. Quantum error correction achieves exponentially tighter tolerances from polynomially increasing resources. For example, Ross and Selinger proved that continuous rotations can be approximated to a target error of epsilon using O(log(1/epsilon)) gates from the discrete gate set Clifford+T [4]. And Clifford gates with error below epsilon can be achieved in the surface code using O(log(1/epsilon)^2) noisy qubits for O(log(1/epsilon)) time [5]. And T gates can be achieved by using those reliable Clifford gates to perform magic state distillation of log(1/epsilon)^O(1) T states [6]. Since everything scales polynomially in log(1/epsilon), making epsilon exponentially smaller adds polynomial resources.

There is no part of Shor's algorithm that requires resources growing exponentially in n (the number of digits of the number being factored). The practical scaling is more like n^3: factoring a number that's twice as large can be done with ~two times as many qubits running for ~four times as long. Even if the qubits are noisy [7].

[1]: https://en.wikipedia.org/wiki/Quantum_Fourier_transform#/med...

[2]: https://arxiv.org/abs/quant-ph/0306018

[3]: https://arxiv.org/abs/quant-ph/9601018

[4]: https://arxiv.org/pdf/quant-ph/9903071#page=12

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

[6]: https://arxiv.org/abs/1209.2426

[7]: https://arxiv.org/abs/1905.09749

I saw a commercial once where the joke was a guy asking a girl for her IP address instead of her phone number. They went with 127.0.0.1; the loopback address. So (at least in my eyes) there was the extra unspoken joke of her essentially telling the guy to go f*#$ himself.

> the people writing the standard are not exactly known for adding features “just because”

Ah yes, C++, the discerning language.

Iterating over optional does seem syntactically convenient. My main question would be if it guarantees no overhead. For example, is there an additional conditional branch due to the iterator hiding the statically know fact that there's at most one iteration? I don't use C++ for its beauty, I use it for speed.

Every one of these "performance tricks" is describing how to convince rust's borrow checker that you're allowed to do a thing. It's more like "performance permission slips".

No, the pre-shared states are never consumed. They are catalysts, not fuel.

Yes, the post is focusing on the overall effect of operations (unitaries) rather than their continuous trajectories (hamiltonians acting on system via Schrodinger equation) (analogous to working with impulses rather than forces).

To make the continuous case interesting as a compilation problem, you'd need some alternate formulation of the Schrodinger equation, e.g. based on the limit of small powers of unitaries rather than on the matrix exponential, so that deleting i didn't delete literally all processes. Or you could arbitrarily declare real-only hamiltonians are permitted, despite the Schrodinger equation saying "i". But that'd be kinda lame, imo.

(Note: am author of post)

Realistic Shor circuits have depth polynomial in n, but you can easily construct ones whose depth is polylogarithmic in n. Just do the multiplications as a binary tree instead of in a linear order, using log depth multiplication circuits, and then do the frequency basis measurement using a low depth QFT [1]. The only part that isn't known to be doable in polylog depth is the classical GCD computation hiding in the classical postprocessing, to find the closest fraction to get the period.

The result is that, if you keep adding qubits that can be operated on in parallel, Shor's algorithm basically just keeps getting faster and faster and faster. The energy cost doesn't go down, and the number of qubits required becomes frankly absurd, but the time can go really really low.

1: https://arxiv.org/abs/quant-ph/0006004

In most quantum computer designs, gates are signals generated on demand at runtime rather than material deposited at fabrication time. In this regime, the concept of an ALU makes no sense. Instead of just sending pulses doing the exact gates you know need, why would you instead expand that short sequence into long sequences that emulate potentially applying every arithmetic operation to every input and then mux out the result you already knew you needed. It's a lot of extra work for the same final result.

A quantum ALU would also be substantially harder to design, because of the need to maintain reversibility. For example, every operation would have to run as slow as the slowest operation (or else the timing side channel would measure which operation occurred).

A gate isn't a qubit, it's an operation applied to qubits. You can do more than one operation per qubit.

The more plausible amount of optimization is less optimization. Or, more accurately, the benefits of optimization at large sizes is expected to be less beneficial than it was for the N=21 circuit.

Estimates of the cost of RSA1024 use explicit circuit constructions at the target size, rather than extrapolating from the 4 bit case. So they implicitly account for the discontinuity being pointed out in the post. So this post has no impact on those costs.

> So how many gates are we talking to factor some "cryptographically useful" number?

Table 5 of [1] estimates 7 billion Toffoli gates to factor 2048 bit RSA integers.

> Is there some pathway that makes quantum computers useful this century?

The pathway to doing billions of gates is quantum error correction. [1] estimates distance 25 surface codes would be sufficient for those 7 billion gates (given the physical assumptions it lists). This amplifies the qubit count from 1400 logical qubits to a million physical noisy qubits.

Samuel Jacques had a pretty good talk at PQCrypto this year, and he speculates about timelines in it [2].

(I'm the author of this blog post and of [1].)

[1]: https://arxiv.org/pdf/2505.15917

[2]: https://www.youtube.com/watch?v=nJxENYdsB6c

Quantum mechanics actually contains measurable real numbers (well.. complex numbers). Amplitudes are postulated to be infinitely precise, and rounding them has a tendency to introduce pretty serious consequences like FTL communication.

For example, in fault tolerant quantum computing, rotations are synthesized using sequences of 45 degree rotations around the X, Y, and Z axes. The matrices that describe those 45 degree rotations contain rational and irrational numbers (in particular: sqrt(2)). If those irrational numbers are actually truncated, this would have observable consequences. You'd need a sufficiently large quantum computer running for sufficiently long to do sufficiently accurate tomography of sequences of those rotations in order to resolve the truncation, and to be frank some of those "sufficientlies" would be very impractical to achieve especially if the truncation was small (and woe unto you if adding more qubits somehow reduces the amount of truncation!), but in principle it'd be possible.

Oh damn, in this year's sigbovik, Tom7 was trying to find out if shapes were Rupert or not: https://sigbovik.org/2025/proceedings.pdf#page=346

That paper is hilarious, and is correct that there's plenty of shit to make fun of... but there's also progress. I recommend watching Sam Jacques' talk from PQCrypto 2025 [0]. It would be silly to delay PQC adoption because of focusing on the irrelevant bad papers.

In the past ten years, on the theory side, the expected cost of cryptographically relevant quantum factoring has dropped by 1000x [1][2]. On the hardware side, fault tolerance demonstrations have gone from repetition code error rates of 1% error per round [3] to 0.00000001% error per round [fig3a of 4], with full quantum codes being demonstrated with an error rate of 0.2% [fig1d of 4] via a 2x reduction in error each time distance is increased by 2.

If you want to track progress in quantum computing, follow the gradual spinup of fault tolerance. Noise is the main thing blocking factoring of larger and larger numbers. Once the quality problem is turned into a quantity problem, then those benchmarks can start moving.

[0]: https://www.youtube.com/watch?v=nJxENYdsB6c

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

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

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

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

It's classical ray optics that fails in the path-not-longer-than-wavelength regime. Classical wave optics works in that regime. Where classical techniques fail is at low brightness (because you start resolving individual photons).

I think you're confusing the distinction between classical ray optics and classical wave optics with the distinction between classical wave optics and quantum mechanics. Quantum mechanics and classical wave optics agree on the explanation for diffraction as a path interference effect. In classical optics, the reason you don't see light coming from angles away from the shortest path is because of destructive interference between the other paths.

For example, note that the Huygens principle predates quantum mechanics by over 200 years [1]. As another example, diffraction gratings (which manifestly require interference between different paths) were being made in the mid 1800s [2] but in physics documentaries you never hear of people being confused about how to explain their behavior. Because they are explained by classical wave optics. Also see this lecture which talks about diffraction in the context of ray optics [3].

Where wave optics disagrees from quantum mechanics is in the dim-light limit, when you start resolving individual photons.

[1]: https://en.wikipedia.org/wiki/Huygens%E2%80%93Fresnel_princi...

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

[3]: https://www.youtube.com/watch?v=5tKPLfZ9JVQ&list=PLB1A0BF14E...

The standard explanation for light "knowing" the angle of diffraction is that actually light just propagates in every direction and then constructive interference is stronger for paths near the shortest path because its length is more consistent when the path is perturbed (meaning the phases of the perturbed paths tend to agree more so they add up instead of cancelling). I don't think you even need quantum mechanics for this; it occurs in classical wave optics.

You can see Feynman explaining mirrors this way in recorded lectures [1]. There's also a recent Veritaseum video explaining why the shortest paths dominate [2].

1: https://youtu.be/SsMYBWpsQu0?si=o1eAEvESwjroTke3&t=2251

2: https://www.youtube.com/watch?v=Q10_srZ-pbs

Yeah this post nails the issue.

In order to do the X-basis measurement described in the paper, it's necessary to do very funky things to the simulated agents inside the computers. Probably the easiest way to implement the measurement would be to literally rewind the simulation back to before the measurement started, when the superposition was limited to a single qubit, do the measurement at that time, and then run the simulation back forwards to the current time. The paper doesn't specify an implementation, so it should work for any implementation, so this should be a valid way of doing the operation. But this implementation implies you're undoing all the reasoning the agents did, changing the initial state, and so as you run them forwards again they are redoing the same reasoning steps but in a new context where the premises no longer apply. Which of course results in them making mistakes. The same thing would happen classically, if you rewound a simulated agent to change some crucial fact and then assumed reasoning from premises that no longer held should still be valid.

I think Scott also co-authored a follow up paper, where they made some steps towards proving that the only computationally efficient way to implement the X-basis measurement was to do this simulation rewinding thing. But unfortunately I can't seem to find it now.

> we caveat the speedup result we find by noting that [...] the oracle we construct in this work can be efficiently simulated by a classical computer.

T_T

You could replace the quantum chip with a classical signal processor decoding the gates to perform, feeding them to a Clifford simulator, and it would solve the problem just fine. They're just arbitrarily declaring that the classical computer isn't allowed to do the thing that solves the problem fast, because that would "violate the black box condition", despite the fact that their quantum compilation and error mitigation pipeline also has to violate the black box condition.

As with many quantum papers, you should ignore the headline and just focus on how large the circuits are:

> Our current implementation of Simon’s problem requires roughly 400 two-qubit gates (after compilation) and 60 qubits

So a few hundred gates. A few times smaller than random circuit sampling experiments from 2019, though much cheaper to verify and simulate.

Isn't that incompatible with the models being consistent?

Suppose model A proves BB(748) = X and model B proves BB(748) = Y > X. But presumably the models can interpret running all size 748 Turing machines for Y steps. Either one of the machines halts at step Y (forming a proof within A that BB(748) >= Y contradicting the assumed proof within A that BB(748) = X < Y) or none of the machines halts at step Y (forming a proof within B that BB(748) != Y contradicting the assumed proof within B that BB(748) = Y).

I'm guessing the only way this could ever work would be some kind of nastiness like X and Y aren't nailed down integers, so you can't tell if you've reached them or not, and somehow also there's a proof they aren't equal.

Ah yes, another entry in the "I'll compute Fibonacci fast!... oh no" genre.

My favorite of the genre so far is https://www.youtube.com/watch?v=KzT9I1d-LlQ , which tries to compute a big Fibonacci number in under a second. It doesn't do the modulus, so it has to do big integer arithmetic, and so is really about doing big multiplications with FFTs. But then it funnily spins off into a series of videos as the author keeps dryly realizing their code is extremely wasteful (ending in finally just using GMP).

Yeah, I measure ~250 nanoseconds on CPU single shot. ~125 nanos amortized if repeated 100 times. It's fast enough that I'm not sure I'm benchmarking the method, as opposed to overheads like reading the time.

    #include <stdio.h>
    #include <time.h>
    
    int fib_mod_9837(int n) {
        int a = 0;
        int b = 1;
        int k = 1;
        while (k < n) {
            k <<= 1;
        }
        while (k) {
            int a2 = a*a;
            int b2 = b*b;
            int ab2 = a*b << 1;
            a = a2 + ab2;
            b = a2 + b2;
            if (n & k) {
                int t = a;
                a += b;
                b = t;
            }
            a %= 9837;
            b %= 9837;
            k >>= 1;
        }
        return a;
    }
    
    int main() {
        struct timespec begin, end;
        clock_gettime(CLOCK_MONOTONIC_RAW, &begin);
        int result = fib_mod_9837(99999999);
        clock_gettime(CLOCK_MONOTONIC_RAW, &end);
        printf("%lld\n", result);
        printf("elapsed nanos: %lld\n", (end.tv_nsec - begin.tv_nsec) + (end.tv_sec  - begin.tv_sec)*1000000000);
    }

It could still be a pseudo random number generator behind the scenes. For example, a typical quantum circuit simulator would implement measurements by computing a probability then asking a pseudo random number generator for the outcome and then updating the state to be consistent with this outcome. Bell's theorem proves those state updates can't be local in a certain technical sense, but the program has arbitrary control over all amplitudes of the wavefunction so that's not a problem when writing the simulator code.

If the prng was weak, then the quantum circuit being simulated could be a series of operations that solve for the seed being used by the simulator. At which point collapses would be predictable. Also, it would become possible to do limited FTL communication. An analogy is some people built a redstone computer in minecraft that would detonate TNT repeatedly, record the random directions objects were thrown, and solve for the prng's seed [1]. By solving at two times, you can determine how many calls to the prng had occurred, and so get a global count of various actions (like breaking a block) regardless of where they happened in the world.

[1]: https://www.youtube.com/watch?v=FPmQ0rnJjNc

Can you provide the source for that quote? 5 billion years seems way too soon.

The Hubble constant is currently approximately one doubling per 14 billion years [1]. So 5 billion years isn't enough to double the recession speeds. AFAIK there's plenty of galaxies receding at less than half the speed of light. Wikipedia estimates 150 billion years (6000x expansion) for all but the local group to be beyond the horizon [2]. So your quote seems to be off by two orders of magnitude.

[1]: https://astronomy.stackexchange.com/questions/49248/interpre...

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