AI 지원 증명으로 양자 가속에 관한 오랜 난제 해결

인사이더 브리프

• Aaronson-Ambainis 추측의 증명에 따르면, 대부분의 무작위 생성 입력에 대한 예/아니오 질문에 답할 때 입력 읽기에서의 지수적 양자 이점을 위해서는 구조가 필요하다는 사실이 입증되었습니다.
• PSI는 자사의 연구 시스템이 비공개 Anthropic 모델을 사용하여 증명을 찾아냈으며, 이는 Lean 증명 도우미를 통해 확인되고 연구자들의 검토를 거쳤다고 밝혔습니다.
• 이 정리는 총 계산 시간이 아닌 데이터 읽기를 제한하므로 실용적인 양자 이점의 여지를 남겨두며, 수학적 범위를 강화하기 위한 추가적인 연구 과제를 제시합니다.

수학적 증명을 통해 2008년부터 미해결 상태였던 추측이 해결되었습니다. 이 추측은 양자 컴퓨터가 기존 컴퓨터에 비해 언제 엄청난 우위를 점할 수 있는지에 관한 것으로, 구조화되지 않은 입력에 대해 고전적 알고리즘을 능가하는 능력의 한계를 설정했습니다.

이 결과는 Aaronson-Ambainis 추측을 입증하며, 이는 수학적 함수에 관한 질문을 해결 중인 문제의 특별한 구조가 비약적인 속도 향상을 위해 필요한지 여부와 연결합니다. 즉, 이는 양자 컴퓨팅의 핵심 사안입니다.

양자 컴퓨팅의 경우, 실질적인 시사점은 수학적 또는 물리적 구조가 이점을 제공하는 문제를 향한 양자 알고리즘 연구의 더 명확한 방향성입니다. 이 정리는 그러한 접근 방식에 대한 이론적 근거를 강화하지만, 어떤 응용 분야가 유용한 속도 향상을 가져올지 최종적으로 결정하지는 않습니다.

Physical Superintelligence, 또는 PSI의 David Turturean이 git hub에 게시한 논문에 따르면, 알고리즘이 입력에 액세스하는 빈도를 측정하는 널리 사용되는 프레임워크 내에서 답은 '예'입니다. 예/아니오 계산의 경우, 고전적 알고리즘은 지수적으로 더 많은 액세스 없이도 대부분의 균등하게 무작위인 입력에 대해 양자 알고리즘이 '예'라고 답할 확률을 근사화할 수 있습니다.

PSI는 관련 블로그 게시물에서 비공개 Anthropic 모델의 인스턴스를 사용하는 내부 개발 연구 시스템이 실행 3일 차에 완전한 증명을 발견했다고 밝혔습니다. 논문에 따르면 주요 정리와 원래 추측의 공식화는 증명 도우미인 Lean으로 형식화되었으며, 논리적 단계를 검증하는 소프트웨어 구성 요소인 커널에 의해 확인되었습니다.

양자와 고전의 경계

이번 발견은 양자 컴퓨팅과 고전 컴퓨팅 사이의 이론적 경계를 더욱 명확히 합니다. 이는 컴퓨터가 문제에 제공된 데이터(입력)를 읽어야 하는 빈도에 대한 한계를 설정합니다. 이 측정치는 데이터를 처리하는 데 필요한 모든 작업을 고려하지 않으므로, 이 정리가 총 계산 시간이나 양자 컴퓨터의 상업적 가치에 대한 일반적인 한계를 설정하는 것은 아닙니다.