PSI, AI 연구 시스템으로 Aaronson-Ambainis 추측 증명

Physical Superintelligence(PSI)가 비공개 Anthropic 모델을 실행하는 내부 연구 시스템을 활용해 2008년 양자 복잡도 이론의 미해결 문제였던 Aaronson-Ambainis 추측을 증명함
Lean 증명 도우미로 검증된 이 증명은 구조적 패턴이 없는 무작위 입력에서 양자 컴퓨터가 고전 컴퓨터보다 지수적으로 빠를 수 없으며, 최대 다항식 수준의 속도 향상에 그친다는 것을 확인함
시스템은 실행 3일 차에 완전한 증명을 발견했으며, Shachar Lovett와 Jiapeng Zhang의 계획에 기반하고 David Reimer의 Butterfly Lemma를 활용하여 결과를 두 번 개선함
핵심 수학 결과는 저차 유계 다항식에서 어떤 변수의 영향력이 (v/d)^7 이상임을 보여주며, 여기서 v는 분산, d는 차수, 상수 c는 약 0.0025임
Stanford 연구진인 Guy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan은 2026년 8월에 특수한 경우를 해결한 바 있으며, 현재 전체 증명의 해설을 작성 중임

핵심 내용