HNHacker News
TopNewBestAskShowJobs

Strilanc

5,205 karma · joined June 22, 2010

submissionscomments
Strilanc··on StackOverflow now gets fewer than 1000 questions a month
If you look at the data on a log scale, and include other stack exchange sites, it's apparent that the serious decline is starting after ChatGPT launches: https://x.com/CraigGidney/status/2115664509042053377/photo/1

One way that stackoverflow does stand out from the other stackexchange sites is that its half life appears far shorter. On a log scale plot it has a steeper descent than the other stackexchange sites. I'm not sure what to make of that. Another interesting thing is that the math stackexchange initially declines more slowly than the others for a year or two and then decays pretty similarly. You can also see examples in some of the other sites of their decay beginning before chatgpt releases (e.g. drupal). You can also see some sites decaying a decade earlier (e.g. expressionengine). I think those outliers are from their subject being too specific and going out of style.

I got the cross-site data from data.stackexchange.com with this vibe-coded query:

    DECLARE @sql NVARCHAR(MAX) = N'
    SELECT
      site = [$site_name$],
      month = DATEADD(MONTH, DATEDIFF(MONTH, 0, CreationDate), 0),
      questions = COUNT(*)
    FROM PostsWithDeleted
    WHERE PostTypeId = 1
    GROUP BY DATEADD(MONTH, DATEDIFF(MONTH, 0, CreationDate), 0)
    ';

    EXEC dbo.sede_ineachdb
      @SQLCommand = @sql,
      @IncludeMainSites = 1,
      @IncludeMetaSites = 0,
      @IncludeMainMeta = 0;
Strilanc··on Designing more efficient quantum circuits with Claude
No, it is not like SIMD. It's more like an ALU, in that there needs to be gates present for each possible operation (and then muxers/demuxers route through the correct one).

Something that is like SIMD in quantum computing is that if a block code supports a transversal operation then it is far cheaper to apply that operation to every qubit in the block than to selectively target one of them with the operation.

Strilanc··on Designing more efficient quantum circuits with Claude
Typical quantum simulation papers do not target 100% accuracy, they target "chemical accuracy [1]". That said, chemistry simulations do tend to be less tolerant of approximations because you are sampling an unknown distribution and so can't easily tell if a shot had a failure. But the linked article is about a subroutine for Shor's algorithm, where it is very obvious if you succeeded or not because you either recovered the private key or you didn't.

[1]: https://chemistry.stackexchange.com/questions/62001/why-is-c...

Strilanc··on Designing more efficient quantum circuits with Claude
Yes strictly speaking it's a different computation, but the differences are so small that it won't meaningfully affect the outcome of Shor's algorithm.

One of the most important things to realize when optimizing quantum algorithms is this: approximations are overpowered. The difference between 99.99999% accurate and 100% accurate can be a factor of 10 in cost. And there's lots of places where a 90% accurate algorithm is more than good enough.

Strilanc··on Git 3.0's upcoming SHA-256 default will be a costly mistake
The post's argument that hash collisions are irrelevant in practice is not convincing at all. Basically they amount to:

1. Collisions aren't as bad as preimage attacks

2. Even if you made a file-with-malicious-hash, how would you get people to pull it?

3. Other attacks are a bigger problem (social engineering)

(2) is laughable in a world with github. It's common for unknown people to submit pull requests to code bases, and for those changes to be reviewed and merged. For example, as part of reviewing pull requests, I have `git fetch`'d proposed changes to my local machine to check behavior on some additional test cases. "If you fetch it you're fucked" is unacceptable as a security boundary.

(1) and (3) are just tu-quoque arguments about other attacks being worse. The relevant question isn't how bad other attacks are, it's how bad this attack is.

The fundamental problem with collisions is that software often assumes they can't happen (or is not tested against them). Thus collisions can trigger bugs, or otherwise cause surprising behavior. For example, webkit figured the colliding PDFs demonstrating a sha1 collision would be excellent for unit tests, so they merged the PDFs into their SVN repo... which completely fucked it [1]. I don't know the exact internals of git so I can't comment on how you would get surprising things to happen, but "oops the file you merged was different than the file you reviewed" and "oops the repository got corrupted" seem entirely plausible.

[1]: https://www.reddit.com/r/programming/comments/5vyhy2/webkit_...

Strilanc··on A misalignment of AI in mathematics
That's only one of mathematics' many purposes.
Strilanc··on A misalignment of AI in mathematics
This letter is complaining that human understanding has been crucial to advancing of mathematics, and AI companies are not bothering with it. But the promise (and horror) of AI mathematics is that, if it succeeds, human understanding becomes irrelevant. That's the goal. So this letter's message will fall on deaf ears.

Keep in mind employees at AI companies are publicly stating that they believe they're risking a >10% chance of human extinction. They're knowingly risking the lives of every man, woman, and child to continue the work. The lives of their own sons and daughters. A person already rationalizing that isn't going to shed a tear for the careers of mathematicians. Just a bug on the windshield.

Strilanc··on IBM Quantum Nighthawk R2
Currently the two qubit gate error rate is listed as ~2.7e-3 (see https://quantum.cloud.ibm.com/computers?system=ibm_phoenix but note it will vary from day to day). That implies you can expect ~400 entangling gates before experiencing an error. A zero-shenanigans factoring of 21 takes ~2000 entangling gates. So it's not good enough to factor 21 in any meaningful sense.

Really what matters about this chip is that it is better suited for error correction. They have a square grid connectivity (previous IBM chips incurred fatal overheads from their heavy hex connectivity), they can actually reset their qubits now (previous IBM chips couldn't scale to long running computations because once leakage arose nothing could remove it except waiting a long time), and they have tunable couplers instead of fixed frequency ones (previous IBM chips were just doomed whenever some problem happened to land on their operating area in frequency space).

Most interesting quantum computations take millions or billions of gates. Factoring classically intractable numbers takes tens of billions of gates. No one is going to do that many quantum gates without error correction. Whenever a quantum computing company says anything other than "it made error correction better" or "it will make error correction better", you can ignore that. It's just some side quest. Maybe it's interesting in and of itself, but it's not what matters for progress.

Strilanc··on Discovery of a new OpenAI agent message board
In order for a person to observe themselves working at Anthropic (or any other AI company), that person must be actively failing to internalize the risks of the work they are doing. This "Anthropic principle" neatly explains why OpenAI would be so negligent about security.
Strilanc··on Quantum Key Distribution (QKD) and Quantum Cryptography (QC)
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

Strilanc··on Quantum Key Distribution (QKD) and Quantum Cryptography (QC)
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

Strilanc··on A more efficient implementation of Shor's algorithm
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.

Strilanc··on Replace IBM Quantum back end with /dev/urandom
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

Strilanc··on Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys
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.

Strilanc··on A cryptography engineer's perspective on quantum computing timelines
> 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

Strilanc··on Quantum computing bombshells that are not April Fools
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 .
Strilanc··on Quantum computing bombshells that are not April Fools
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.
Strilanc··on Quantum computing bombshells that are not April Fools
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.
Strilanc··on Quantum computing bombshells that are not April Fools
Caution: that 10M estimate assumes gate error rates 10x lower than the ones assumed in the papers from TFA.
Strilanc··on Quantum computing bombshells that are not April Fools
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

Strilanc··on Quantum computing bombshells that are not April Fools
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.

Strilanc··on Quantum computing bombshells that are not April Fools
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.
Strilanc··on Securing Elliptic Curve Cryptocurrencies Against Quantum Vulnerabilities [pdf]
> [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

Strilanc··on The “JVG algorithm” only wins on tiny numbers
Minor update: Dominik condensed the blog posts into a pre-print: https://arxiv.org/abs/2603.09901
Strilanc··on The “JVG algorithm” only wins on tiny numbers
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

Strilanc··on The “JVG algorithm” only wins on tiny numbers
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.

Strilanc··on The “JVG algorithm” only wins on tiny numbers
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

Strilanc··on The “JVG algorithm” only wins on tiny numbers
What reviewers? It's not a peer reviewed article.
Strilanc··on The “JVG algorithm” only wins on tiny numbers
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.

Strilanc··on The “JVG algorithm” only wins on tiny numbers
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

Page 1 of 34Next →