Anthropic의 미스터리 모델이 양자 컴퓨팅의 중요한 추측을 돌파하며 수학계를 거의 20년간 괴롭혀온 난제를 해결했다

동찰 Beating AI 속보, AI 연구 회사 Physical Superintelligence(PSI)가 Anthropic의 아직 공개되지 않은 모델을 활용해 수학계를 약 20년간 괴롭혀온 Aaronson–Ambainis 추측을 증명했다고 발표했다. AI는 실행 3일째에 완전한 증명을 찾아냈고, Lean 수학 검증 도구의 검사를 통과했다.

이 추측은 두 과학자가 2008년에 제기한 것으로, 양자 컴퓨터의 속도 우위가 과연 얼마나 큰지를 연구하는 내용이다.

양자 컴퓨터는 특정 문제를 처리할 때 일반 컴퓨터보다 수억 배 빠를 수 있다. 예를 들어 매우 큰 정수를 소인수분해할 때 일반 컴퓨터는 알려진 알고리즘으로도 극히 긴 시간이 필요할 수 있지만, 양자 컴퓨터는 계산 시간을 크게 단축할 수 있을 것으로 기대된다. 그러나 이런 막대한 우위는 보통 문제 자체에 특정한 수학적 규칙이 존재하는 데 의존한다.

이번에 AI는 입력 데이터가 완전히 무작위여서 활용할 수 있는 특별한 규칙이 없다면, '예' 또는 '아니오'만 답하면 되는 문제에 대해 양자 컴퓨터가 데이터를 읽는 횟수에서 지수적 우위를 얻을 수 없음을 증명했다.

예를 들어 방대한 무작위 숫자 속에서 하나의 결과를 판별할 때, 양자 컴퓨터는 양자 중첩을 이용해 한 번의 질의로 여러 위치를 다룰 수 있다. 일반 컴퓨터는 매번 한 위치만 읽을 수 있지만, 양자 알고리즘의 판단 규칙만 알면 결과에 가장 큰 영향을 미치는 숫자들을 우선적으로 검사해 상대적으로 제한된 질의 횟수로 양자 컴퓨터의 답을 근사적으로 예측할 수 있다.

이전까지 수학자들은 특정 특수한 경우에 이것이 가능하다는 것을 알고 있었지만, 이 규칙이 보편적으로 성립한다는 것을 증명하지는 못했다. PSI가 이번에 완전한 증명을 완성하면서 약 20년간 이어진 이론 문제도 해결했다.

소식이 전해진 후 워싱턴 대학 교수 Pedro Domingos는 양자 컴퓨팅 우위의 꿈이 이미 무너졌다고까지 생각했다.

추측을 제기한 사람 중 한 명인 Scott Aaronson은 이후 이런 이해는 틀렸다고 지적했다. 이번 연구는 특정 문제에서 양자 컴퓨터가 데이터 질의를 몇 번이나 절약할 수 있는지만 제한했을 뿐, 양자 컴퓨터의 실제 연산 속도 우위를 부정한 것은 아니다. 대정수 소인수분해에 쓰이는 Shor 알고리즘과 양자 물리·화학 시뮬레이션은 모두 영향을 받지 않는다.

Aaronson은 자신이 아직 이 증명을 완전히 읽어내지는 못했지만 Lean이 검사를 완료했고 다른 수학자들도 검토했으므로 결과가 옳다고 믿는다고 밝혔다. 그는 또한 자신의 추측이 마침내 증명된 것은 기쁘지만, 인류가 결국 AI보다 먼저 그것을 해결하지 못했다는 점에는 다소 아쉽다고 농담했다.