Formally verified harness for Shor's order finding algorithm with $O(n^{2+ε})$ gate cost
- Published
- Source
- arXiv
- Paper number
- 1482
- Field
- Research Agents
- arXiv ID
- 2611.20342
Key points
- The authors built a harness where participants submit only a recursive multiplication design policy and Lean automatically applies correctness and gate-cost proofs.
- They proved as a theorem that the recursive multiplication circuits improve the cost scaling to O(n2+ϵ) for every valid policy.
- Exact optimization is intractable at cryptographic sizes, with an estimated 3.2 × 1051 core-hours to certify the best known tree at n = 2048.
- In Qualtran resource estimation, the best fixed k was 1.820 × 1012 T-gates at k = 4.
- A policy varying k at each level achieved a lower count of 1.685 × 1012 T-gates.
- Without further optimization, the PhaseProduct approach would need a modulus size of about 3.8 million bits to beat the Gidney-Ekerå method.
Paper links
External research summaries. These are not HDATF publications or measured product results.