양자계산 18년 난제 증명 발표…앤트로픽 AI 활용

AI 연구기업 Physical Superintelligence(PSI)가 양자계산 분야에서 2008년 제기된 애런슨·암바이니스 추측의 증명을 공개했다. 무작위 입력을 다루는 특정 계산에서 양자컴퓨터가 입력 조회 횟수를 지수적으로 줄일 수 없다는 내용이다.

PSI는 6일 연구 발표에서 자체 인프라에서 실행한 연구 시스템이 비공개 앤트로픽(Anthropic) 모델을 활용했다고 밝혔다. 같은 모델의 여러 실행본이 사용됐고, 시스템은 실행 셋째 날 완전한 증명을 얻어 Lean 검사를 통과했다.

PSI는 이후 시스템에 관련 난제를 맡겨 결과를 두 차례 개선했으며, 최종 버전도 Lean 검사를 통과했다고 설명했다. 사용한 모델의 구체적인 이름은 공개하지 않았다.

스콧 애런슨(Scott Aaronson)과 안드리스 암바이니스(Andris Ambainis)가 제기한 추측은 특별한 규칙이 없는 무작위 입력에서 양자컴퓨터가 일반 컴퓨터보다 입력을 읽는 횟수를 지수적으로 줄일 수 있는지를 묻는다. 연구 대상인 입력은 0과 1로 이뤄진 긴 문자열이고, 계산은 이를 바탕으로 ‘예’ 또는 ‘아니오’를 판별한다.

일반 컴퓨터는 입력을 조회할 때 문자열의 한 비트를 읽는다. 양자 알고리즘은 여러 위치에 걸친 중첩을 이용해 한 번의 조회로 여러 위치의 정보를 다룰 수 있다.

양자 알고리즘이 ‘예’라고 답할 확률은 입력 비트의 다항식으로 표현된다. PSI는 기존 연구에서 이 확률이 조회 횟수의 두 배를 넘지 않는 차수의 다항식으로 나타난다는 점을 바탕으로 증명을 구성했다.

증명에 따르면 일반 컴퓨터는 무작위 문자열 대부분에서 양자 알고리즘의 답변 확률을 작은 오차 안에서 근사할 수 있다. 필요한 조회 횟수는 양자 알고리즘의 조회 횟수에 대해 고정된 다항식 수준으로 늘어날 뿐, 지수적으로 늘어나지 않는다.

추측의 수학적 핵심은 입력 비트 하나가 다항식 출력에 미치는 ‘영향력’이다. 영향력은 비트 하나를 뒤집었을 때 다항식 출력값의 변화량을 제곱해 모든 입력에서 평균한 값이다.

PSI는 0과 1 사이 값을 내는 비상수 저차 다항식에 대해 일정한 영향력을 가진 입력 비트가 존재한다는 하한을 제시했다. 구체적으로 영향력은 출력의 분산을 v, 다항식 차수를 d로 놓았을 때 약 0.0025×v의 2.5승/d의 6승 이상이라고 밝혔다.

이 결과는 양자컴퓨터의 모든 계산이 빠르지 않다는 뜻은 아니다. 무작위 입력에 대한 특정 예·아니오 판정에서 입력 조회 횟수를 비교한 이론적 결과다.

큰 수의 소인수분해를 빠르게 하는 쇼어 알고리즘은 문제에 숨은 반복 패턴을 활용한다. PSI는 알려진 극적인 양자 가속 사례 대부분이 이런 구조에 기대며, 무작위 입력에는 그와 같은 패턴이 거의 없다고 설명했다.

스탠퍼드대 연구진은 2026년 8월 정해진 횟수의 병렬 단계로 입력을 조회하는 양자 알고리즘에서 이 추측의 특수한 경우를 증명했다. PSI는 네 명의 연구진이 현재 전체 증명을 검토하고 있다고 밝혔다.

연구진은 PSI에 보낸 서한에서 “수십 년 된 추측을 해결한 큰 성과”라고 평가했다. 이들은 증명이 불리언 함수 분석과 확률 조합론의 여러 연구 흐름을 묶었다고 덧붙였다.

PSI는 샤하르 러벳(Shachar Lovett)과 지아펑 장(Jiapeng Zhang)의 접근을 바탕으로 증명을 전개했다고 밝혔다. 두 연구자가 남겨둔 부등식을 새 부등식으로 대체했고, 행렬식을 이용해 입력 설정을 짝짓는 결과를 얻었다.

PSI는 연구를 이끈 담당자가 연구 시스템을 개발하고 문제를 정해 실행했으며, AI가 작성한 논문 초고를 검토하고 정확성에 책임졌다고 설명했다. 자문위원은 증명을 감사했고, 별도의 자문위원은 Lean 형식화를 검토했다.

논문과 Lean 형식화 코드는 공개 저장소에 올라왔다. 저장소는 코드에 빈 증명 자리표시자나 추가 공리가 없고, 두 종류의 독립된 Lean 커널 구현으로 다시 검사했다고 밝혔다.

Lean은 코드에 형식화된 명제와 증명의 논리 단계를 확인한다. 저장소는 코드 속 명제가 원래 추측과 일치하는지 독자가 문제 정의와 대조해야 한다고 안내했다. 체인뉴스 ABMedia는 논문이 학술지 심사를 거치지 않았다고 보도했다. AI가 수학 난제를 형식화한 다른 사례로는 오픈AI가 나비에–스토크스 방정식 증명을 공개한 일이 있다.