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.

Read original (opens in a new tab)