애런슨 교수는 "축하한다"며 치켜세웠습니다. 하지만 며칠 뒤 상황이 급변했습니다. 파아타 이바니슈빌리(Paata Ivanishvili)라는 연구자가 논문의 핵심 부분인 '보조정리 5.3(Lemma 5.3)'에서 치명적인 논리적 오류를 발견했고, 논문은 결국 철회되었습니다. 애런슨 교수는 "슬프게도(retracted),"라며 "역사적 이유로 이 글을 남겨둔다"고 적었습니다.
PSI의 연구 시스템이 실행 사흘 만에 논리를 완성했고, 작성된 모든 단계는 '린(Lean)'이라는 증명 검증 언어로 컴퓨터가 직접 확인했습니다. 60쪽 분량의 논문과 검증 코드는 깃허브(GitHub)를 통해 공개되었습니다 12.
왜 이번에는 사흘 만에 쓰인 증명이 2019년처럼 뒤집히지 않을 가능성이 높을까요? 핵심은 '검증 방식'의 구조적 차이입니다. 과거에는 인간이 논리를 읽고 판단하는 과정에서 미세한 결함이 놓칠 수 있었지만, 린 검증은 논리가 작성되는 즉시 컴퓨터가 단계별 오류를 잡아내는 방식을 택했기 때문입니다. 다만 이번 증명이 학계의 전통적인 동료 심사를 완전히 통과했는지, 그리고 AI가 어떤 수학적 통찰로 해법을 찾았는지는 공개된 자료를 통해 명확히 확인되지 않았습니다.
양자컴퓨터의 이점은 '구조'에서 나온다
애런슨-암바이니스 추측을 이해하려면 양자컴퓨터가 언제 고전컴퓨터보다 월등히 빠른지를 살펴봐야 합니다. 양자컴퓨터는 소인수분해와 같은 특정 문제에서는 기하급수적인 속도를 냅니다. 하지만 이런 가속도가 모든 문제에 적용되는 것은 아닙니다. 애런슨 교수는 오래전부터 "입력값이 완전히 무작위일 때 양자컴퓨터가 고전컴퓨터보다 정말로 빠른가?"라는 의문을 가졌습니다.
애런슨 교수의 논리는 이렇습니다. 양자 알고리즘이 T번의 질문으로 입력에 접근한다면, 1998년 비얼스(Beals) 등의 결과에 따라 그 결과가 차수 2T 이하의 다항식으로 표현됩니다. 만약 이 다항식에서 영향력이 큰 변수가 항상 존재한다면, 고전컴퓨터도 그 변수만 집중적으로 질문해 양자 알고리즘을 다항 시간 횟수의 질문으로 흉내 낼 수 있습니다. 즉, 양자컴퓨터의 진정한 이점은 입력 데이터 자체에 '숨겨진 구조'가 있을 때만 발생한다는 것이었습니다. 이 생각을 수학적으로 증명하기 위해 애런슨 교수와 안드리스 암바니스(Andris Ambainis)는 2008년경 이 추측을 제안했고, 이는 2011년 논문 『양자 가속에는 구조가 필요하다(The Need for Structure in Quantum Speedups)』를 통해 공식화되었습니다 3.
이 추측은 개의 변수를 가진 다항식 의 성질을 다룹니다. 여기서 두 가지 핵심 개념을 쉽게 이해할 필요가 있습니다.
- 분산(Variance): 다항식 가 입력값에 따라 값이 얼마나 넓게 흩어져 있는지를 나타냅니다. 값이 0과 1 사이를 오가며 크게 변한다면 분산이 높다고 봅니다.
- 영향력(Influence): 특정 변수 하나를 0에서 1로(또는 그 반대로) 바꿨을 때 다항식 의 값이 평균적으로 얼마나 크게 변하는지를 나타냅니다.
추측의 내용은 "다항식의 값이 넓게 흩어져 있다면(높은 분산), 그 변화의 상당 부분을 책임지는 단 하나의 변수가 반드시 존재한다(높은 영향력)"는 것입니다. 수학적으로는 어떤 변수 의 영향력()이 분산()과 차수()로 표현 가능한 일정 수준 이상이어야 한다고 말합니다.
이것이 양자컴퓨터와 연결되는 이유는 1998년 비얼스(Beals) 등의 연구 결과 때문입니다. 양자컴퓨터가 입력값에 대해 번 질문하고 얻는 결과는 '차수가 낮은 다항식'으로 나타낼 수 있습니다. 만약 애런슨-암바이니스 추측이 사실이라면, 고전컴퓨터도 '영향력이 큰 변수'만 집중적으로 질문해 다항식을 분석함으로써 양자컴퓨터의 행동을 모방할 수 있습니다. 결론적으로, 양자컴퓨터가 고전컴퓨터보다 기하급수적으로 빨라지려면 입력 데이터에 특정한 수학적 구조가 필수적이라는 사실이 증명되는 셈입니다 3.
2019년, 한 줄의 논리가 붕괴의 시작이었다
애런슨 교수는 19페이지 분량의 논문을 정독했고, "훌륭하다(It's great!)"며 긍정적으로 평가했습니다. 그러나 애런슨 교수가 정독을 마친 후인 11월 20일, 켈러와 클라인은 파아타 이바니슈빌리가 발견한 보조정리 5.3의 오류로 인해 논문을 철회하겠다는 연락을 했습니다 3.
문제는 이런 미세한 논리적 결함이 발견되기 어렵다는 점입니다. 인간이 복잡한 수학 논문을 읽을 때는 한 줄 한 줄의 타당성을 '믿고' 넘어가는 경우가 많습니다. 애런슨 교수조차 "노이즈 연산자나 초축소성(hypercontractivity) 같은 내용은 믿고 넘어갔다"고 회고했습니다 3. 특히 켈러-클라인 증명은 특정 변수들의 영향을 분석해 함수를 단순화하는 복잡한 과정을 거쳤는데, 이 과정에서 특정 보조정리가 논리의 붕괴를 일으키는 약한 고리였습니다.
결국 2019년의 철회로 기대했던 증명은 다시 무산되었고, 이 추측은 그 뒤로도 한동안 미해결로 남아야 했습니다.
린(Lean) 검증이 만드는 새로운 규칙
2026년의 증명이 2019년의 실패를 반복하지 않을 것으로 기대되는 가장 큰 이유는 '린(Lean)'의 사용입니다. 린은 수학 논문을 컴퓨터가 이해할 수 있는 코드로 번역하고, 논리의 모든 단계를 기계적으로 검증하는 도구입니다. 인간 리뷰어는 논문을 읽으며 '대략 맞는 것 같다'고 판단할 수 있지만, 린은 단 하나의 논리 규칙 위반도 허용하지 않습니다.
PSI는 2026년 9월에 설립된 AI 물리학 연구 기업으로, 물리학 문제를 가설 트리로 분해해 병렬 검증하는 '에미(Emmy)' 플랫폼을 사용합니다 4. 과거 이 회사가 수행했던 프로젝트 보고서에서는 '반증적 감사(adversarial audit)'를 수행한다고 강조한 바 있습니다. 이번 증명 과정에서는 AI 시스템이 논리를 작성하면 린이 이를 단계별로 확인하는 구조를 거쳤습니다 12.
아래 표는 2019년과 2026년 증명 시도의 주요한 차이를 비교합니다.
| 구분 | 2019년 (켈러-클라인) | 2026년 (PSI) |
|---|---|---|
| 증명 주체 | 인간 수학자 | AI 시스템 (비공개 Anthropic 모델 기반) |
| 소요 기간 | 약 11년간 열려 있던 추측에 대한 시도 | 실행 3일 만에 도출 |
| 검증 방식 | 인간 리뷰어의 판단 의존 | 린(Lean) 언어를 통한 단계별 기계 검증 |
| 결과 | 보조정리 오류로 철회 | 기계 검증 완료 (동료 심사 진행 상황 미공개) |
기계가 좁힌 논리의 빈틈, 남은 과제
애런슨-암바이니스 추측은 양자컴퓨터 계산 능력의 본질적 한계를 규명하는 중요한 열쇠였습니다. 2008년 제시 이후 18년간 열려 있던 이 추측에서, 2019년의 한 보조정리 오류가 증명 시도를 원점으로 되돌렸던 것을 생각하면, 사흘 만에 기계 검증까지 마친 이번 증명은 의미가 큽니다.
PSI의 AI는 비공개 앤트로픽 모델들을 병렬로 운용해 논리를 구성했고, 그 결과는 린의 엄격한 단계별 검증을 통과했습니다. 다항식의 분산과 영향력을 비교하는 복잡한 수학적 직관이 컴퓨터 코드로 변환되어 논리적 오류가 없음을 확인한 것입니다.
하지만 이 증명이 학계 전체의 합의인지는 아직 단정하기 어렵습니다. 논문의 내용과 해석에 대해 전통적인 동료 심사가 어떻게 진행될지, 그리고 AI가 구체적으로 어떤 수학적 전략으로 이 해법을 찾아냈는지는 공개된 자료 밖의 영역입니다. 중요한 것은 기계 검증이라는 새로운 기준이 '논리적 빈틈'을 좁혀, 과거의 실패를 반복하지 않을 수 있는 강력한 도구가 되었다는 사실입니다.
참고자료
- ↩
- ↩
- The Aaronson-Ambainis Conjecture (2008-2019) · scottaaronson.blog↩
- ↩
