Id: arxiv/2611.20342 Url: https://arxiv.org/abs/2611.20342 Tags: quant-ph Score: 1 Title: Formally verified harness for Shor's order finding algorithm with $O(n^{2+ε})$ gate cost Domain: quant-ph Source: arxiv Authors: Anirudh Suresh, Joshua M. Courtney, Runzhou Tao, Yudong Cao Reviews: 0 Subject: quant-ph Category: research Comments: 0 Disputed: false Division: physics Mentions: 0 Discussed: 0 Published: 2026-11-16 Reactions: up=1 Page: https://delphi.science/r/arxiv/2611.20342 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…