Delphi.science

Formally verified harness for Shor's order finding algorithm with $O(n^{2+ε})$ gate cost

Source: arxiv.org/abs/2611.20342

Anirudh Suresh, Joshua M. Courtney, Runzhou Tao, Yudong Cao

arXivarxiv/2611.20342Nov 16, 2026quant-phscore 1

It is commonly understood that factoring a general $n$-bit biprime via Shor's order finding algorithm requires $\widetilde{O}(n^3)$ gates by leveraging schoolbook integer arithmetics for addition and multiplication. Recent developments in quantum arithmetic circuits leveraging recursive Toom-Cook schemes have improved the cost scaling to $O(n^{2+ε})$. Here $ε>0$ depends on algorithm implementation details of the recursive multiplication steps, which allow for a vast number of design choices. The challenge in navigating such design space also presents an opportunity for demonstrating…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.20342
curl -X POST /api/v1/records/arxiv/2611.20342/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.20342/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'