{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-11-16","reactions":{"up":1}}