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;
That's interesting, thanks! The peak for most topics was around 2015-2020 apparently, and then came a "continuous" decline. If it really was a major event that caused the decline, wouldn't we expect to see a volatile plunge, like on the stock market?
Today with Opus, Sol, etc there's basically no reason to visit the site, but when chatGPT launched it was powered by GPT 3.5, which would realistically only be able to answer a (minor) chunk of all possible StackOverflow questions.
There are many potential explanations, including the policy changes in 2018. LLMs are definitely a concurrence to the service, but since the decline started years before they were really useful, other reasons might be relevant. I don't know to what degree. I just wondered why some of the forums had significant peaks after the GPT line.
So much for the long tail! The rate of decline after the advent of AIs is sobering. From 181,000 questions a month at the absolute peak, to less than a thousand a month now!
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.
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.
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.
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.
(2 counter) is impractical because all nodes of git will not replace objects if it thinks it already has it. So any attack has to assume this is the first time the node fetched, which is difficult before trust is established, which is difficult. This is part of the argument Linus originally outlined for this vector, which is that it only works for _very recent_ objects.
(1/3 counter) is not what I argued. I argued from the worst-case position that collision and preimages were theoretically cheap and fast. Even in that case, I feel my arguments hold.
The main issue here is that you assume you can replace an existing object with a replaced one, which you cannot. Not only that, but in all known cases, the sha1dc variant of SHA1 that Git uses will even _tell_ you that someone tried to do this, which singles out the source quickly.
It doesn't reject, but it will not replace. Same for a fetch/pull. That is another issue with this attack vector (that Linus also mentions) - it has to be the _first_ time that a node has seen this object. It makes the attack even more difficult than it already is (in like 4 different major ways)
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.
AI companies are alienating the communities they serve. Instead of a win-win dynamic, they are keen on a win-lose proposition. You dont win trust by one-upping your customer. This is unfortunate and suggests a lack of adults in the room. It also reeks of hubris and is all good when making profits is not a concern. But watch the narrative shift when there is an AI slowdown which is inevitable.
I agree insofar as this may fall on deaf ears of AI folks, but that the goals are differ is exactly the point of pointing out misalignment. To talk about this may be more useful for coalescing professional societies than for conversing directly with AI advancers.
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.
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.
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.)
Of course that also means you need a mesh network topology (every node needs a direct link to the node it wants to share qubits with), so a quantum internet (interconnected network of networks) is impossible.
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.
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 is the key point, what is the meaning of "zero knowledge" here? It seems that you need to know something about the implementation, even if it is not the full implementation. Compare this to a zero knowledge proof that you have, say, a factorization gadget, which works by you running the gadget on adversarial input, thus convincing the adversary that you can factor any of their integers. That discloses no implementation details of your factorization gadget, which can be an efficient classical algorithm, a quantum computer, or a phone line to God.
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:
reply