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가 발표한 논문이나 제품 성능을 측정한 결과는 아닙니다.

원문 보기 (새 탭에서 열림)