Formally verified harness for Shor's order finding algorithm with $O(n^{2+ε})$ gate cost
- 발행일
- 출처
- arXiv
- 논문 번호
- 1482
- 분야
- Research Agents
- arXiv 번호
- 2611.20342
쇼어 알고리즘 회로 설계를 Lean 으로 형식 검증하는 열린 도전장을 만들어 사람과 AI 에이전트가 더 싼 인수분해 회로를 찾게 했다.
이 논문은 한마디로 재귀 곱셈을 쓰는 쇼어 차수 탐색 알고리즘을 Lean 으로 검증하는 공개 하니스 ForShor 를 소개한다. 참가자는 재귀 설계 정책만 제출하면 하니스가 정확성과 게이트 비용 증명을 자동으로 적용한다. 정확 최적화는 n = 2048 에서 계산적으로 닿지 않음을 보였다. Qualtran 자원 추정에서 단계마다 k 를 바꾸는 정책이 1.685 × 1012 T-게이트로 최저를 기록했다.
핵심 요약
- 참가자가 재귀 곱셈 설계 정책만 제출하면 Lean 이 정확성과 게이트 비용 증명을 자동으로 적용하는 하니스를 만들었다.
- 모든 유효 정책에 대해 재귀 곱셈 회로의 비용이 O(n2+ϵ) 로 개선됨을 정리로 증명했다.
- 정확 최적화의 표 구성은 암호학적 크기에서 불가능하여 n = 2048 최적 트리 인증에 약 3.2 × 1051 코어시간이 추정되었다.
- Qualtran 자원 추정에서 고정 k 최저는 k = 4 의 1.820 × 1012 T-게이트였다.
- 단계마다 k 를 바꾸는 정책이 1.685 × 1012 T-게이트로 더 낮은 비용을 보였다.
- 추가 최적화 없이는 PhaseProduct 방식이 Gidney-Ekerå 방식을 앞서려면 약 3.8 million 비트의 모듈러스 크기가 필요했다.
논문 링크
외부 연구를 정리한 자료입니다. HDATF가 발표한 논문이나 제품 성능을 측정한 결과는 아닙니다.