Quantum computing

tl;dr: What has happened in quantum computing over the years.

A history

In 2001, Vandersypen et al. claimed an “experimental realization” of Shor’s quantum factoring algorithm¹. Their results demonstrate feasibility of building very small, highly specialized quantum circuits. Specifically, they show a quantum circuit tailored for factoring 15, but in designing this circuit they leveraged knowledge of its factorizaton (i.e., $3\times5 = 15$). Naturally, the relevance of these results has been questioned, most notably by Smolin et al.² who write:

While there is no objection to having a classical compiler help design a quantum circuit (indeed, probably all quantum computers will function in this way), it is not legitimate for a compiler to know the answer to the problem being solved. To even call such a procedure compilation is an abuse of language.

Others, have been less gentle and mocked this kind of “experimental realization”³.

There might’ve been full runs that factor 15 after.

Google’s results: Willow, error-correction, new ECDLP algorithm. Oratomic’s result. This result⁴. Craig Gidney’s post and his past paper on Shor.

Some interesting readings

• Lecture 14: Skepticism of quantum computing, Scott Aaronson, Fall 2006
• Reasons to believe II: quantum edition, Scott Aaronson, September 8th, 2006
• Mistake of the Week: “X works on paper, but not in the real world”, Scott Aaronson, October 26th, 2006
  • Scott does away with the well-known “in theory, theres no difference between theory and practice; in practice, there is.” quote, saying “In theory, there’s no difference between theory and practice even in practice.” (Otherwise, the theory is wrong and thus no longer a theory.)
• NSA and IETF: Can an attacker simply purchase standardization of weakened cryptography, Daniel J. Bernstein, October 2025
• Factoring is not a good benchmark to track Q-day, Bas Westerbaan, April 2nd, 2026
• Bitcoin and Quantum Computing, Neha Narula, April 3rd, 2026

Blockchain space responses (chronological)

• March 2nd, 2022: Algorand announced future support for state proofs using Falcon digital signatures
• September 7th, 2022: Algorand Protocol Upgrade Introduces State Proofs for Trustless Cross Chain Communication and 5x Faster Performance, by Algorand
• October 15th, 2025: EIP-8051: Precompile for ML-DSA signature verification, by Renaud Dubois and Simon Masson
• November 3rd, 2025: Technical Brief: Quantum-resistant transactions on Algorand with Falcon signatures, by Larkin Young
• December 9th, 2025: AIP-137: Post-quantum Aptos accounts via SLH-DSA-SHA2-128s signatures, by Alin Tomescu
• January 14th, 2026: Announcing Project Eleven’s Series A, by Project 11
  • Mentions a Solana testnet with ML-DSA support
• February 1st, 2026: PR for “SIMD-0461: enabling falcon signature verification as a precompile”, by zz-sol

TODOs

• The threshold theorem and the reasonableness of its assumptions
• What do we know about CRQC’s ability to break hash functions? e.g., BHT, Grover search. Is there a proof that you cannot do better asymptotically?
  • What do we know about quantum algorithms that attack the structure of the hash function, rather than the idealized hash function?
• There are many different approaches to building QCs. What are the universal metrics that we should be looking for to judge them?(# of “stable” logical qubits is a popular one, but deeply inadequate)

References

For cited works, see below 👇👇