18년 된 양자 추측이 사흘 만에 무너졌다. 그 증명에는 검사기가 함께 왔다.

Physical Superintelligence는 자사의 내부 연구 시스템이 Aaronson-Ambainis 추측을 증명했다고 밝혔습니다. 그 실행은 완전한 논증을 만들어 내는 데 사흘이 걸렸습니다. 컴퓨터가 모든 단계를 검사하도록 만드는 증명 보조기인 Lean이 이를 승인했습니다. 이후 시스템은 관련 문제들을 공략했고 결과를 두 번 강화했으며, Lean은 최종 버전도 승인했습니다.
PSI는 사람이 읽을 수 있는 논문과 Apache 2.0 라이선스의 완전한 Lean 4 형식화를 함께 공개했습니다. 저장소는 해당 개발에 증명 자리표시자가 없고 추가된 공리가 없으며, 네 가지 주요 정리가 Lean 커널과 동일한 타입 검사기의 독립 구현인 lean4lean을 통해 다시 재검증되었다고 명시합니다. Lean과 nanoda 커널을 모두 사용하는 비교기는 최종 결과를 승인했습니다. 두 번째 머신에서 같은 비교기는 올바른 토이 해법 하나를 승인하고, 의도적으로 틀린 네 개를 거부했습니다.
제가 계속 되돌아오는 부분은 바로 그 통제 테스트입니다. 주장과 영수증을 구분해 주는 것이죠.
그 추측이 실제로 말하는 것
가장 유명한 양자 속도 향상은 대부분 구조에 의존합니다. 1994년 쇼어의 소인수분해 알고리즘이 작동하는 이유는 입력이 반복 주기를 숨기고 있기 때문입니다. 균일하게 무작위인 입력에 대한 예/아니오 질문에 답하라고 양자 컴퓨터에 요청하면 그 구조는 사라지며, 바로 여기에 미해결 질문이 있었습니다. 양자 기계가 여전히 지수적으로 더 빠를 수 있을까?
Aaronson과 Ambainis는 이 질문을 다항식에 관한 명제로 바꿨습니다. 질의 모델에서는 알고리즘이 입력을 몇 번 읽는지 셉니다. T번의 질의 후 양자 알고리즘이 '예'라고 답할 확률은 차수가 최대 2T이고 값이 0과 1 사이에 있는 다항식으로 쓸 수 있습니다. 그 알고리즘을 고전적으로 시뮬레이션하려면 지수적인 수의 입력 비트를 읽지 않고도 그 다항식을 추정해야 합니다.
이 추측은 거의 상수에 가깝지 않은, 유계인 저차수 다항식은 적어도 하나의 높은 영향력을 가진 좌표를 갖는다고 말합니다. 그 한 비트를 뒤집으면 평균적으로 다항식의 값을 의미 있는 만큼 움직여야 합니다. 그것이 성립하면 고전 기계는 대부분의 입력에서 T에 대해 다항식 개수의 질의를 사용해 임의의 T-질의 양자 알고리즘을 시뮬레이션할 수 있습니다. 비구조적 입력에서는 지수적 속도 향상이 없습니다.
PSI의 증명은 명시적 하한을 제시합니다. 어떤 비트는 영향력이 적어도 상수 × v^(5/2) / d^6 이상입니다. 여기서 v는 분산, d는 차수이며 상수는 약 0.0025입니다. 더 느슨한 형태로는 적어도 (v/d)^7입니다.
이 경로는 Shachar Lovett과 Jiapeng Zhang이 제시한 계획을 따르며, 분수 인증서(fractional certificates)와 레벨 집합(level sets)에 기반합니다. Lovett과 Zhang은 하나의 부등식을 미해결로 남겨 두었고, 이를 추측으로 제시했습니다. PSI의 시스템은 입력 설정의 행렬식 기반 짝짓기에서 도출한 새로운 모든 쌍 부등식으로 이를 대체했으며, 이는 얼마나 많은 좌표가 일치할 수 있는지를 제한함으로써 David Reimer의 이전 Butterfly 보조정리를 넘어선다고 말합니다.
무엇이 기계 검증되었고, 무엇이 아니었나
이 이야기에 관한 대부분의 보도가 틀릴 지점이 바로 여기라고 생각합니다. Lean 증명은 강력한 산출물입니다. 그것은 결과에 대한 완전한 인증이 아니며, PSI도 그렇게 말합니다.
세 가지가 기계 검증 밖에 있습니다. Lean 커널, 컴파일러, Mathlib의 정의, 그리고 검증을 수행하는 하드웨어는 모두 신뢰 기반(trusted base)의 일부입니다. 산문 논문은 기계 검증되지 않으며, 형식 명제만 검증됩니다. 그리고 형식 명제가 Aaronson과 Ambainis가 2008년에 인쇄한 그대로의 추측과 일치하는지는 여전히 사람이 확인해야 합니다.
PSI는 마지막 단계를 가능한 한 쉽게 만들었습니다. 저장소는 Mathlib 외에는 아무것도 가져오지 않는 파일 안에 `PrintedConjecture`라는 단일 정의를 분리해 두었습니다. 그래서 회의적인 독자는 파일 하나를 열어 원 논문과 비교할 수 있습니다. 이는 검증을 위한 사려 깊은 인터페이스 설계이며, 저자들이 약한 연결부가 어디인지 알고 있었다는 것도 보여줍니다.

감사는 내부에서 이루어졌습니다. Jim Halverson이 증명을 감사했고 Phiala Shanahan이 형식화에 대해 논평했으며, 두 사람 모두 PSI 고문입니다. 동료 검토도, 저널 출판도 없었습니다. 2026년 8월 특수 사례를 증명한 스탠퍼드 연구자 네 명, Guy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan은 전체 증명을 읽고 의견을 보냈으며, 더 짧은 설명문을 준비하고 있습니다. 인용된 그들의 평가는 이를 거대한 결과라고 부릅니다. 관심 있는 전문가와의 서신 교환은 유용합니다. 그것은 동료 검토가 아닙니다.
인간의 역할이 이름으로 명시되어 있는데, 저는 이 점이 좋습니다. MIT에서 물리학과 AI를 공부한 기술 직원인 David Turturean은 연구 시스템을 구축하고, 문제 범위를 정하고, 실행했으며, 비공개 Anthropic 모델 인스턴스에 첫 초안을 패키징하도록 프롬프트를 넣고, 그 초안을 검토했으며, 논문의 정확성에 대한 책임자로 명시되어 있습니다. 저장소는 AI 모델이 수학적 명제, 첫 초안, Lean 형식화를 생성했음을 공개합니다.
그러한 역할 분담은 분명히 말할 가치가 있습니다. 곧 일상이 될 것이기 때문입니다. 사람은 문제를 고르고 책임을 집니다. 모델은 후보 논증을 만들어냅니다. 검사기는 닫히지 않는 논증을 거부합니다. 결과물은 노트북과 오후 한나절만 있으면 누구나 다시 실행할 수 있는 주장입니다.
왜 모델보다 검사기가 더 중요한가
Anthropic은 이 뒤에 있는 모델이 언제, 혹은 출시될지 말하지 않았습니다. 그 세부 사항은 거의 주의를 흐트러뜨리는 요소입니다. 여기서 흥미로운 대상은 파이프라인이며, 그 파이프라인은 벤치마크 점수와 달리 재현 가능합니다.
회의적인 수학자가 이번 공개로 무엇을 할 수 있는지 생각해 보십시오. 저장소를 클론합니다. `PrintedConjecture`를 읽습니다. Lean을 실행합니다. lean4lean을 실행합니다. 비교기를 실행합니다. 추가된 공리가 없는지 확인합니다. 그 모든 단계는 통과하거나 실패하며, 실패 방식은 구체적입니다.
대안과 비교해 보십시오. 어떤 연구소는 차트, 제품 페이지, 추론 개선에 관한 한 문단을 올립니다. 당신은 그것을 믿거나 믿지 않거나 둘 중 하나입니다.
형식 검증은 마법이 아니며 수학을 완전히 해결하지도 않습니다. 그것은 더 좁은 것을 해결합니다. 특정 형식 명제가 특정 규칙에 따라 특정 공리들로부터 도출되는지 여부입니다. 그 명제가 올바른 명제인지, 공리들이 올바른 공리인지, 결과가 중요한지는 모두 사람에게 남습니다.
PSI는 매사추세츠주 케임브리지에 있는 공익 목적 회사(public benefit corporation)로, Breakthrough Energy Ventures가 주도한 5,800만 달러 시드 라운드와 함께 9월에 공개 출범했습니다. 스스로를 AI 네이티브 물리학 연구소라고 설명하며, 이론가처럼 추론하고 계산 물리학자처럼 검증하도록 설계된 가상 물리학자들로 구성되어 있다고 합니다. 지난달 양자 정보 이론의 오래된 문제 다섯 개를 해결했다고 말하며, 이번은 약 2주 만의 두 번째 주요 발표입니다. 그 속도는 인상적이거나 경고입니다. 그중 얼마나 많은 것이 외부의 주목을 받은 뒤에도 살아남느냐에 달려 있습니다.
양자 이야기에 무엇을 의미하나
이 결과는 경계를 더 선명하게 합니다. 비구조적 무작위 입력에 대한 예/아니오 질문에서는 양자 기계가 지수적으로 많은 질의를 절약할 수 없습니다. 알고리즘 설계자들은 일반적 입력에서 속도 향상을 찾기보다 수학이나 물리학 안의 실제 구조를 가진 문제를 찾아야 합니다.
어떤 응용이 성과를 낼지는 말해 주지 않습니다. 질의 모델은 데이터를 로드하고 처리하는 작업이 아니라 입력 읽기 횟수를 세므로, 총 실행 시간이나 양자 컴퓨터의 상업적 가치에 일반적인 한계를 두지 않습니다. 이 논문을 양자 컴퓨팅이 죽었다는 증거로 인용하는 사람은 논문에 없는 것을 인용하는 것입니다.
그것이 하지 않는 또 다른 일은 AI가 연구를 수행하는 것에 관한 논쟁을 끝내는 것입니다. 내부 시스템이 만들어 내고 내부에서 감사했으며, 주변 문헌이 이미 접근법을 하나의 미해결 부등식으로 좁혀 둔 문제에 대한 단일 결과는 하나의 데이터 포인트입니다. Lovett과 Zhang에게는 계획이 있었습니다. Reimer에게는 보조정리가 있었습니다. 시스템은 간극을 메웠습니다. 그것은 실제 작업이며, 동시에 수학 연구가 포함하는 것의 좁은 한 조각입니다.
남은 단계는 PSI가 스스로 할 수 없는 일입니다. 현장의 누군가가 형식 명제를 읽고, 그것이 Aaronson과 Ambainis의 추측이지 그 추측의 편리한 사촌이 아니라는 데 동의하고, 공개적으로 그렇게 말해야 합니다. 그때까지 존재하는 것은 유명한 주장에 매우 가까운 무언가의 기계 검증된 도출과, 마지막 1마일이 짧도록 만들어진 저장소입니다.
그것은 대부분의 발표가 남겨 주는 것보다 나은 위치입니다.