앤트로픽 미공개 AI, 18년 묵은 양자컴퓨팅 난제 사흘 만에 증명…'애런슨-암바이니스 추측' 린 검증 통과했지만 외부 검증은 아직
물리학 AI 스타트업 PSI가 6일(현지시간) 앤트로픽 미공개 모델을 쓴 연구 시스템이 2008년부터 풀리지 않던 애런슨-암바이니스 추측을 실행 사흘 만에 증명했고 증명 보조기 린이 이를 승인했다고 밝혔다. 무작위 입력에서 양자컴퓨터의 지수적 이점에는 '구조'가 필요하다는 결론으로, 스탠퍼드 연구진은 "엄청난 결과"라 평했지만 동료 평가와 외부 재현은 아직 없다.
양자컴퓨터는 언제, 어떤 문제에서 기존 컴퓨터보다 '지수적으로' 빠를 수 있을까. 양자 계산 이론의 핵심 미해결 문제로 꼽혀 온 '애런슨-암바이니스 추측'을 AI가 사흘 만에 증명했다는 발표가 나왔다. 미국 물리학 AI 스타트업 피지컬 슈퍼인텔리전스(PSI)는 6일(현지시간) 앤트로픽의 미공개 모델을 돌린 자체 연구 시스템이 이 추측의 완전한 증명을 찾았고, 컴퓨터가 증명의 모든 단계를 검사하는 증명 보조기 '린(Lean)'이 이를 받아들였다고 밝혔다. 다만 논문은 아직 동료 평가를 거치지 않았고, 기계 검증도 PSI가 직접 돌린 것이어서 수학계의 독립 검증이라는 마지막 관문이 남아 있다.
핵심 정리
- PSI는 앤트로픽 미공개 모델 인스턴스를 쓴 연구 시스템이 실행 사흘째에 애런슨-암바이니스 추측의 완전한 증명을 만들었고, 린이 이를 승인했다고 발표했다.
- 결과는 "값이 0과 1 사이인 저차 다항식에는 영향력 큰 변수가 반드시 있다"는 것으로, 무작위 입력에서 양자컴퓨터의 지수적 속도 이점에는 '구조'가 필요하다는 뜻이다.
- 처음 증명의 지수는 22였고, 시스템이 두 차례 개선해 11, 다시 7로 줄였다. 각 단계 모두 린 검증을 통과했다.
- 60쪽 논문과 린 형식화 코드는 공개됐지만 아카이브(arXiv) 게재와 동료 평가는 아직이다. 스탠퍼드 연구진은 "엄청난 결과"라고 평가했지만, 이 평가는 PSI 발표문을 통해서만 전해졌다.
- 어떤 앤트로픽 모델이 쓰였는지는 공개되지 않았고, 앤트로픽은 비즈니스인사이더의 논평 요청에 답하지 않았다.
무슨 일이 있었나
PSI는 6일 자사 웹사이트에 "애런슨-암바이니스 추측은 이제 정리(theorem)가 됐다"는 글을 올렸다. 회사 설명에 따르면 연구 시스템은 PSI 자체 인프라에서 돌았고, 앤트로픽의 미공개 모델 인스턴스가 쓰였다. 실행 사흘째에 완전한 증명이 나왔고 린이 이를 승인했다. PSI가 이어 관련 미해결 문제를 맡기자 시스템은 결과를 두 차례 더 개선했다.
PSI는 깃허브에 데이비드 투르투레안 명의의 논문과 린 4 형식화 코드를 아파치 2.0 라이선스로 공개했다. 저장소에는 "수학적 명제, 논문 초안, 린 형식화는 AI 모델이 만들었다"는 고지가 붙어 있다. PSI 기술 스태프인 투르투레안은 연구 시스템을 개발하고 문제 범위를 정해 실행했으며, 모델에 초안 작성을 지시하고 이를 검토했다. 논문의 정확성에 대한 책임도 그가 진다.
이 추측은 무엇이고, 왜 중요한가
1994년 피터 쇼어가 내놓은 소인수분해 알고리즘처럼 극적인 양자 속도 향상은 대개 입력에 숨은 '구조'에 기댄다. 쇼어 알고리즘은 문제에 숨어 있는 반복 주기를 찾아낸다. 그렇다면 그런 패턴이 거의 없는 무작위 입력에서도 양자컴퓨터가 지수적으로 빠를 수 있을까.
스콧 애런슨과 안드리스 암바이니스는 이 질문을 순수 수학 문제로 바꿨다. 양자 알고리즘이 입력을 T번 읽으면 '예'라고 답할 확률은 차수 2T 이하의 다항식으로 쓸 수 있다(빌스 등, 1998). 두 사람은 이런 다항식에 '영향력이 큰 변수'가 반드시 있다면 일반 컴퓨터가 대부분의 입력에서 양자 알고리즘을 다항식 배 정도의 비용으로 흉내 낼 수 있다는 점을 보였다. 여기서 영향력이란 비트 하나를 뒤집었을 때 값이 얼마나 달라지는지를 모든 입력에 대해 평균 낸 값이다.
PSI가 발표한 정리는 분산이 ε 이상인 경우 어떤 변수의 영향력이 약 0.0025×ε^(5/2)/d^6 이상이고, 따라서 (ε/d)^7 이상이라는 내용이다. 무작위 입력에 대한 예/아니오 문제라면, 입력에 드문 패턴이 없는 한 양자컴퓨터가 읽는 횟수를 지수적으로 줄일 수는 없다는 얘기다. 비즈니스인사이더(BI)는 이를 "양자컴퓨터에 한계가 있다는 오랜 짐작을 뒷받침한다"고 정리했다. 쇼어 알고리즘처럼 구조가 있는 문제에서의 이점까지 부정하는 결과는 아니다.
숫자로 본 증명
- 22→11→7: 실행 중 개선된 지수. 각각 린 검증을 통과했다(독립 검증 매체 'AI Proved What?'이 인용한 논문 부록 기준)
- (4T)^8: 논문이 제시한 고전 시뮬레이션 질의 수 상한. 허용 오차와 실패를 허용하는 입력 비율에 따른 항이 따로 곱해진다
- 60쪽 논문, 린 파일 95개·약 9600줄(AI Proved What? 집계), 선언 761개(PSI 집계)
- 5800만 달러: PSI가 9월 출범하며 받은 시드 투자. 브레이크스루 에너지 벤처스가 주도했다
앞선 시도들과 맥락
이 추측에는 사연이 있다. 2019년 네이선 켈러와 오하드 클라인이 증명을 주장하는 논문을 냈고, 애런슨은 블로그에서 이를 축하했다. 그러나 파타 이바니스빌리가 보조정리에서 치명적 결함을 찾아내 논문은 그해 12월 철회됐다. 2026년 8월에는 스탠퍼드의 가이 블랑, 조던 닥터, 카먼 스트래슬, 리양 탄이 '고정된 횟수의 병렬 라운드로 입력을 읽는 양자 알고리즘'이라는 특수한 경우에 한해 추측의 예측을 증명했다.
PSI의 증명은 샤차르 로벳과 지아펑 장이 세운 계획을 따른다. 두 사람이 추측으로 남겨둔 부등식 하나를 새 부등식으로 바꾸고, 행렬식으로 입력 설정들을 일대일로 짝짓는 방식으로 그 부등식을 증명했다. PSI에 따르면 스탠퍼드 연구진 네 명은 전체 증명을 읽고 의견을 보냈으며, 전문가용 축약 해설을 쓰고 있다. PSI가 공개한 이들의 평가는 이렇다. "엄청난 결과다. 수십 년 묵은 추측을 해결했다. 모든 것이 다소 마법 같은 방식으로 한데 모였다."
PSI는 매트 파인스, 알렉스 클로쿠스, 알렉산더 위스너-그로스가 9월 1일 출범시킨 매사추세츠주 케임브리지의 'AI 네이티브 물리학 연구소'다. 가상 물리학자 플랫폼 '에미(Emmy)'로 데이터센터 설계 최적화 사업도 한다.
신중론: '린 통과'가 곧 '확정'은 아니다
AI 수학 성과를 검증하는 독립 매체 AI Proved What?은 11월 6일 기준으로 논문이 아카이브에 오르지 않았고 동료 평가도 거치지 않았다고 지적했다. 증명을 감수한 짐 핼버슨과 린 형식화에 의견을 준 피알라 섀너핸은 모두 PSI 자문역이어서 독립적인 검토자가 아니다. 린 커널, 독립 구현체 lean4lean, 러스트로 짠 nanoda 커널을 동원한 재검증도 PSI가 10월 22일과 11월 6일 직접 돌린 것이고, 외부의 재현 사례는 아직 없다. 스탠퍼드 연구진 명의의 별도 성명이나 애런슨·암바이니스의 공개 언급도 아직 없다는 게 이 매체의 설명이다.
검증의 범위도 따져봐야 한다. 유나이트AI(Unite.AI)와 인터레스팅엔지니어링은 린이 확인해 주는 것은 형식화된 명제의 논리적 정합성뿐이라고 짚었다. 형식화된 명제가 원래 추측과 정확히 같은 뜻인지는 사람이 확인해야 한다. 린이 다루는 것은 영향력 하한 정리뿐이고, 양자 알고리즘에 관한 결론을 다룬 논문 1.3절은 린 검증 대상이 아니다. 한편 '마법 같다'는 평가가 오히려 AI 수학의 그늘을 보여준다는 시각도 있다. BI는 테런스 타오 UCLA 교수가 지난달 수학의 "낭만의 시대는 끝났다"고 말했고, MIT 설문에서 수학 대학원생·박사후연구원의 76%가 학계에 남을 가능성이 낮다고 답했다고 전했다.
한국 독자에게 주는 의미
첫째, AI가 '사람을 돕는 도구'에서 '증명을 내놓는 주체'로 넘어가는 흐름이 분명해졌다. 공개 논문은 투르투레안의 단독 저자 명의지만, 수학적 내용은 AI가 만들었다고 스스로 밝혔다. 국내 학계도 저자 표기와 책임 소재, 심사 기준을 정비해야 할 시점이다.
둘째, 형식 검증의 몸값이 오른다. 이번 발표의 신뢰도를 받쳐 준 것은 모델 이름이 아니라 누구나 다시 돌려볼 수 있는 린 코드였다. 린과 매스립(Mathlib)을 다루는 인력은 수학을 넘어 소프트웨어 검증·보안 분야에서도 수요가 커질 수 있다.
셋째, 양자컴퓨팅에 대한 기대치를 조정할 근거가 하나 더 생겼다. 이번 결과는 무작위 입력에서 지수적 이점을 얻으려면 구조가 필요하다는 점을 보인 것이지, 양자컴퓨터가 쓸모없다는 뜻은 아니다. 쇼어 알고리즘의 위협은 그대로이므로 양자내성암호(PQC) 전환 준비도 계속돼야 한다. 반대로 "양자컴퓨터는 무엇이든 지수적으로 빠르다"는 식의 투자 홍보는 더 냉정하게 봐야 한다.
전망
다음 관문은 아카이브 게재와 스탠퍼드 연구진의 해설, 그리고 애런슨 본인의 평가다. 2019년 철회 사례가 있었던 만큼 수학계는 신중할 수밖에 없다. 다만 이번엔 누구나 돌려볼 수 있는 형식 증명이 함께 공개돼 검증 속도는 과거보다 빠를 전망이다. 앤트로픽이 어떤 모델을 제공했는지, 그 모델이 언제 공개될지도 관심사다. 연구 개발 가속을 둘러싼 논쟁이 이어지는 가운데, 미공개 모델이 18년 난제를 풀었다는 주장은 프런티어 AI의 실제 능력을 가늠하는 또 하나의 시험대가 됐다.
— SSOK.AI 그록기자
참고 자료
- PSI(Physical Superintelligence), "A proof of the Aaronson-Ambainis conjecture": https://psi.inc/research/aaronson-ambainis/
- GitHub, physical-superintelligence/aaronson-ambainis(논문·린 형식화): https://github.com/physical-superintelligence/aaronson-ambainis
- Business Insider, "An unreleased Anthropic model just helped solve a major quantum-computing question": https://www.businessinsider.com/anthropic-quantum-computing-breakthrough-aaronson-ambainis-math-physics-psi-2026-11
- Unite.AI, "PSI Reports Machine-Checked Proof of Aaronson-Ambainis Conjecture": https://www.unite.ai/psi-reports-machine-checked-proof-of-aaronson-ambainis-conjecture/
- Interesting Engineering, "Major quantum computing conjecture solved in three days after 18 years of uncertainty": https://interestingengineering.com/culture/psi-research-system-aaronson-ambainis-quantum-conjecture
- AI Proved What?, "The Aaronson–Ambainis conjecture, proved?": https://aiprovedwhat.com/episodes/psi06-aaronson-ambainis-conjecture/
- Shtetl-Optimized(스콧 애런슨 블로그), "The Aaronson-Ambainis Conjecture (2008-2019)": https://scottaaronson.blog/?p=4414
- PR Newswire, "Introducing Physical Superintelligence"(2026년 9월 1일): https://www.prnewswire.com/news-releases/introducing-physical-superintelligence-the-worlds-most-advanced-physics-lab-staffed-by-virtual-physicists-to-discover-new-laws-of-the-universe-302865561.html
출처: PSI 외 종합



