인간이 18년 간 못 밝힌 양자컴퓨팅 숙제, AI는 어떻게 72시간 만에 돌파했나

PSI “비공개 앤스로픽 모델이 아론슨-암바이니스 추측 증명”…2008년 양자 난제, 린 검증 통과 주장

“양자 알고리즘 속도 이점, 구조적 한계” AI 찾은 18년 만의 해답

오래전부터 수학자들의 머리를 복잡하게 만들었던 난제가 비로소 풀렸다.

미국 매사추세츠주 케임브리지에 거점을 둔 AI 연구기업 피지컬 슈퍼인텔리전스(Physical Superintelligence, PSI)가 지난 6일(현지시간) 컴퓨터 과학계의 오랜 숙제인 ‘아론슨-암바이니스 추측(Aaronson-Ambainis conjecture)’을 증명해 냈다고 발표했다.

발단의 중심에 있는 아론슨-암바이니스 추측은 스콧 애런슨(Scott Aaronson)과 안드리스 암바이니스(Andris Ambainis)가 제기한 가설이다. 값이 0과 1 사이인 낮은 차수의 다항식에는 결과에 결정적인 영향을 미치는 입력 비트가 반드시 존재한다는 내용을 담고 있다. PSI는 분산을 v, 차수를 d라 할 때 특정 비트의 영향력이 (v/d)^7 이상이라는 부등식을 수학적으로 증명했다고 밝혔다. 이 주장이 사실로 굳어지면, 무작위 입력 환경에서 예와 아니오를 판가름하는 양자 알고리즘(Quantum Algorithm)의 속도 이점은 다항식 배를 넘어서지 못한다는 결론에 이르게 된다.

이번 성과는 철저하게 AI 증명으로 이뤄졌다. 연구를 이끈 데이비드 투르투리언(David Turturean) 기술진에 따르면, 완전한 증명 초안은 PSI의 자체 연구 시스템인 ‘아르곤(Argon)’ 모델이 앤스로픽(Anthropic)의 비공개 모델 여러 인스턴스를 구동한 지 사흘 만에 나왔다. 이후 아르곤 시스템은 추가 미해결 문제들을 다루며 두 차례 수정을 거쳤고, 최종 결과물은 형식 검증(Formal Verification) 언어인 린 4(Lean 4)의 검증 문턱을 넘었다. 앞서 지난 8월 스탠퍼드대(Stanford University) 가이 블랑(Guy Blanc) 연구진이 병렬 라운드가 고정된 특수 사례를 증명한 데 이어, 전체 영역으로 시선을 넓힌 셈이다.

다만 화려한 타이틀 뒤로 물음표도 적지 않다. PSI 스스로 논문을 아직 초안(Draft) 단계라 부르는 데다, 깃허브(GitHub)에 공개된 설명문을 보면 논문 전체가 기계 검증을 거친 것은 아니다. 일부 절에는 대응하는 린(Lean) 코드가 빠져 있고, 핵심 정리 중 일부는 형식화되지 않은 타 연구자의 결과를 그대로 전제로 삼고 있다.

그럼에도 이번 결과가 지니는 의미는 결코 가볍지 않다. 검증 과정의 허들이 모두 해소된다면, 양자 컴퓨팅(Quantum Computing)의 속도 향상이 아무 때나 찾아오는 것이 아니라 입력 데이터에 명확한 구조가 갖춰져야만 가능하다는 오랜 학계의 직관에 강력한 수학적 근거가 마련되는 셈이다.

물론 이번 성과가 모든 영역의 문을 여는 것은 아니다. 이번 증명은 어디까지나 입력을 읽은 횟수를 따지는 ‘쿼리 모델(Query Model)’의 무작위 입력 환경에 국한된다. 전체 계산 시간이나 모든 종류의 입력 조건으로 곧바로 일반화할 수는 없다는 뜻이다. 아르곤 모델이 인간의 오랜 이론 난제를 스스로 풀어냈다는 기념비적인 이정표가 될지, 아니면 화려한 수식으로 포장된 해프닝으로 남을지는 이제 철저한 외부 전문가들의 독립적인 검증(Independent Verification)의 손에 달렸다.

*참고: GitHub 저장소

관련 기사

• 오픈AI·앤스로픽 “지수 시간 가설은 거짓”…검증대 오른 AI 증명
• GPT-6 아스트라, 나비에-스토크스 문제 포함 10개 난제 AI 증명
• 하버드·앤스로픽·퀘라, AI로 양자회로 최적화…연산 자원 최대 9,100배 절감