AI 연구 스타트업 피지컬 슈퍼 인텔리전스(PSI)는 2026년 11월 6일, 2008년부터 미해결 상태였던 아론슨-암바이니스 추측의 증명을 공개했습니다. PSI에 따르면 자체 연구 시스템이 공개되지 않은 앤트로픽 모델을 자사 인프라에서 사용해 증명을 만들었습니다. 연구 시작 사흘째 증명 초안을 완성했고, 이후 관련 문제를 더 풀도록 하자 결과를 두 차례 개선했습니다.
증명은 수학적 논리의 각 단계를 컴퓨터가 검사하는 도구인 Lean 4의 검증을 통과했습니다. PSI가 공개한 코드 저장소에는 추측을 표현한 명제와 이를 증명하는 코드가 담겨 있으며, 회사는 증명 과정에 빈칸이나 추가 가정을 넣지 않았고 두 가지 독립적인 Lean 커널로 다시 확인했다고 밝혔습니다. PSI 시스템을 구축하고 문제 범위를 정한 연구원 데이비드 터투리언은 결과를 검토했으며, 논문의 정확성에 책임을 맡았습니다.
증명은 무엇을 말하나
아론슨-암바이니스 추측은 양자컴퓨터가 무작위 입력을 다룰 때 일반 컴퓨터보다 지수적으로 적은 횟수의 데이터 조회만으로 답을 낼 수 있는지를 묻습니다. 이번 결과는 그런 무작위 입력에서는 일반 컴퓨터도 양자 알고리즘이 ‘예’라고 답할 확률을 근사적으로 예측할 수 있음을 보입니다. 다만 이는 입력을 확인하는 횟수에 관한 결과이지, 전체 계산 시간이나 모든 종류의 문제에 대한 비교는 아닙니다.
따라서 이 증명이 양자컴퓨터의 우위를 부정하는 것은 아닙니다. PSI가 든 대표 사례인 쇼어 알고리즘은 큰 수를 소인수분해할 때 입력에 숨어 있는 반복 구조를 이용합니다. 이번 결과는 그런 특별한 수학적 구조가 없는 무작위 입력에서는 지수적 속도 향상을 기대하기 어렵다는 점을 뒷받침합니다. 양자컴퓨터가 어떤 문제에서 유용한지는 입력의 구조에 달려 있다는 뜻입니다.
검증은 어디까지 이뤄졌나
스탠퍼드대학교의 가이 블랑, 조던 닥터, 카르멘 스트라슬레, 리양 탄은 이 결과를 “수십 년 된 추측을 해결한 큰 성과”라고 평가했습니다. PSI는 이들이 전체 증명을 읽고 의견을 보냈으며, 전문가를 위한 더 짧은 설명을 준비하고 있다고 전했습니다. 앞서 이 연구진은 2026년 8월, 추측이 예측하는 결과를 특정한 계산 조건에서 증명한 바 있습니다.
Lean 검증은 코드에 적힌 수학적 명제가 참인지 확인합니다. 그러나 그 명제가 원래 추측의 의도와 정확히 일치하는지, 논문에서 수학적 설명이 적절한지는 전문가가 살펴야 합니다. PSI는 증명 전체의 형식 검증과 수학적 내용의 전문가 검토를 같은 것으로 제시하지 않았습니다. 또 사용한 앤트로픽 모델의 이름과 PSI가 어떻게 접근권을 얻었는지는 공개하지 않았습니다.
왜 중요한가
양자컴퓨터 연구자와 이를 지켜보는 사람들에게 이번 결과는 무작위 입력과 구조가 있는 입력을 구분해 성능을 봐야 한다는 수학적 근거를 제공합니다. 다만 조회 횟수에 대한 결과이며, 양자컴퓨터의 실제 속도나 모든 문제에서의 성능을 판정한 것은 아닙니다.
