AI 시스템, 사흘 만에 완전 증명…동료심사는 아직
PSI가 AI 연구시스템으로 2008년 양자 추측의 Lean 검증 증명을 6일(현지시간) 공개했다.
동료심사는 아직이고, 형식문이 원 추측과 같은지는 사람이 맞춰 봐야 한다고 공개 저장소가 밝혔다. 8월 특수 사례를 푼 스탠퍼드 연구진은 전문 해설을 쓰는 중이라고 PSI 발표는 전했다.
시스템, 사흘 만에 증명 완성
PSI 발표에 따르면, 기술직원 데이비드 터투리언이 구축한 시스템이 자체 인프라에서 비공개 Anthropic 모델 인스턴스를 돌렸다. 인스턴스는 기존 아이디어를 찾고, 새 아이디어를 제안·결합·시험하며 서로 감독했다고 원고 공개문이 적는다. 실행 사흘째에 완전 증명이 나왔고 증명 보조기 Lean이 수락했다.
공개 저장소에 따르면, 관련 난제로 돌린 뒤 결과가 두 차례 더 강해졌고 Lean이 최종본도 받았다. 부록 타임라인상 첫 완전본은 영향력 하한이 (ε/d)^22였고, 이어 11, 마지막이 7이다. 최종 정리의 하한은 차수 d·분산 v인 유계 다항식에서 상수 c≈0.0025, 곧 8√15/(125π^4) 곱하기 v^{5/2}/d^6이다. 원 추측이 요구한 (ε/d)^{O(1)} 형태를 만족한다.
원고 공개문에 따르면, 원고와 Lean 4 형식화는 같은 저장소에 올렸다. 공개 선언은 aaronson_ambainis 등 네 정리이며, 자리 표시자·추가 공리 없이 증명됐다. Lean 커널과 독립 구현 lean4lean으로 다시 재생됐다. 수학 문장·초고·Lean 코드는 AI가 만들었고, 터투리언이 초고를 검토한 뒤 책임을 진다. 고문 짐 할버슨이 증명을 감사했고, 피알라 샤나한은 Lean 형식화에 의견을 냈다.
정리, 구조 없는 입력만 제한
스콧 아론슨과 안드리스 암바이니스의 2008년 추측은 구조 없는 무작위 입력을 다룬다. 예·아니오 물음에서 양자 컴퓨터가 지수적으로 적은 조회만으로 이길 수 있는지가 핵심이다. T번 조회한 양자 알고리즘의 수락 확률은 차수 최대 2T인 유계 다항식이 된다. 영향력 큰 비트를 고전 알고리즘이 골라 읽으면, 대부분 입력에서 poly(T)번 조회로 그 확률을 근사할 수 있다.
쇼어 소인수분해처럼 희귀 패턴을 약속한 문제는 그대로다. The Quantum Insider는 이번 결과가 입력 조회 횟수를 재며 총 연산 시간 한도는 다루지 않는다고 짚었다.
증명 골격은 샤하르 로벳·지아펑 장의 계획이다. 그들이 추측으로 남긴 부등식을 행렬식 기반 일대일 짝짓기로 새로 메웠다. 짝짓기는 라이머의 나비 보조정리보다 세고, 쌍이 각 좌표에서 얼마나 자주 같은지도 제한한다. 샌드박스 비교기는 네 정리를 수락하고 고의로 틀린 네 개는 거부했다.
스탠퍼드팀, 전문 해설 준비
가이 블랑·조던 독터·카르멘 스트라슬·리양 탄은 고정 병렬 라운드 특수 사례를 8월에 푼 뒤 전체 증명을 읽고 의견을 보냈다.
이는 엄청난 결과다. 양자 속도 향상이 가능한 문제의 성격에 중요한 함의를 지닌 수십 년 된 추측을 해결한다. 증명은 불리언 함수 분석과 확률 조합론의 여러 줄을 끌어와 확장한다. 모든 것이 꽤 마법처럼 한데 모인다.
— 스탠퍼드 연구진, PSI 11월 6일 · “This is a huge result. It resolves a decades-old conjecture with important implications for the nature of problems that admit quantum speedups. The proof draws on and extends several lines of work in the analysis of boolean functions and probabilistic combinatorics. Everything is brought together in a rather magical way.”
네 명은 전문가용 짧은 해설을 준비 중이다.
Lean은 통과, 원문 일치는 미제
검증 기록은 Lean 커널·컴파일러·Mathlib 정의·검사 장비를 신뢰 경계 안에 둔다. PrintedConjecture가 원 추측과 같은지, 사람이 읽는 원고가 기계 검증과 맞는지 확인은 독자와 전문가에게 남는다. 사람이 읽는 논문 본문 자체는 기계 검증 대상이 아니다.
Business Insider에 따르면 Anthropic은 어떤 미공개 모델인지에 대한 논평 요청에 응하지 않았다. 모델 이름도 공개되지 않았다. 아론슨과 암바이니스의 공개 평가는 7일 기준 확인되지 않았고, 동료심사 착수 여부도 정해지지 않았다.
