Strilanc

Joined 16 years ago

Karma

5,208

Submissions

1,118

Member since

Jun 22

View on Hacker News

Recent submissions

Comment · 3 days ago

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;

Comment · 9 days ago

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.

Comment · 9 days ago

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

Comment · 9 days ago

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.

Comment · 1 month ago

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

Comment · 1 month ago

That's only one of mathematics' many purposes.

Comment · 1 month ago

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.

Comment · 1 month ago

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.

Comment · 1 month ago

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.

Comment · 5 months ago

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

Comment · 5 months ago

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

Comment · 6 months ago

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.

Comment · 6 months ago

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

Comment · 6 months ago

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.

Comment · 6 months ago

> 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