양자 우월성

1. 개요

양자 우월성은 양자 컴퓨터가 고전 컴퓨터로는 실현 불가능하거나 매우 어려운 특정 계산 작업을 수행할 수 있음을 의미한다. 2019년 구글은 시커모어 양자 컴퓨터를 통해 양자 우월성에 도달했다고 발표했으나, IBM 등 경쟁사들은 이에 대한 반론을 제기하며 논쟁이 일었다. 20세기에는 앨런 튜링, 리처드 파인만 등의 연구를 통해 양자 컴퓨팅의 이론적 토대가 마련되었고, 쇼어의 알고리즘, 그로버의 알고리즘 등 양자 알고리즘이 개발되었다. 21세기에는 D-Wave Systems의 상업용 양자 컴퓨터 출시, 구글의 양자 우월성 발표 등 기술적 진전이 있었으며, 중국 과학기술대학교와 Xanadu Quantum Technologies 등에서도 양자 우월성 달성을 보고했다. 양자 우월성 입증을 위한 실험으로는 쇼어의 알고리즘, 보손 샘플링, 무작위 양자 회로의 출력 분포 샘플링 등이 제안되었으며, 계산 복잡도 이론을 통해 양자 우월성을 평가한다. 양자 컴퓨터는 오류에 취약하며, 양자 우월성이라는 용어의 적절성에 대한 논쟁도 존재한다.

2. 역사

2019년 9월 20일, 파이낸셜타임스는 구글이 양자우월성에 도달했다는 기사를 보도했다. 이 기사는 NASA 웹사이트의 문서를 인용했는데, 구글이 시커모어라는 양자컴퓨터 칩을 만들었다는 내용이었다. 구글은 2018년 NASA와 양자우월성 확인 연구 계약을 맺었으며, IBM과 함께 양자컴퓨터 개발에 투자하고 있다. 당시 구글은 53개의 큐비트로 구성된 시커모어 양자컴퓨터를 개발했다고 알려졌다.

서미트는 2019년 당시 세계 1위 슈퍼컴퓨터로, 148페타플롭스(PF)의 연산 속도를 자랑했다. 1PF는 초당 1000조 번의 계산을 처리하는 속도다. 서미트가 1만 년 걸려 풀 수학문제를 시커모어는 3분 20초 만에 풀어, 양자 컴퓨터가 슈퍼컴퓨터 성능을 최초로 넘어선 사건이 되었다.

구글 연구원은 시커모어가 다른 프로그래밍이 가능한 컴퓨터라고 주장했지만, 경쟁사인 IBM은 제한적인 컴퓨터라고 평가절하했다. 시커모어는 난수를 생성하고 이것이 진짜 난수인지 증명하는 단순 작업을 수행하는 컴퓨터다.

미국 정부가 공개 보고서를 갑자기 삭제하는 경우는 극비 최첨단 기술과 관련된 경우가 많다는 점을 고려할 때, IBM의 주장이 사실인지 확인하기는 어렵다.

2019년 10월 23일, 구글은 네이처지에 양자우월성 도달을 공식 발표했다. 그러나 IBM은 슈퍼컴퓨터로 1만 년이 아니라 2.5일이면 문제를 풀 수 있다고 반박하며, 양자우월성 개념 자체에 회의적인 입장을 보였다. IBM은 전통적인 컴퓨터와 양자컴퓨터는 서로 다른 작업을 잘 수행한다고 주장했다.

2.1. 20세기 양자 우위

1936년, 앨런 튜링은 튜링 기계의 개념을 제시하며 현대 컴퓨터 과학의 기초를 다졌다. 1980년, 폴 베니오프는 튜링의 논문을 바탕으로 양자 컴퓨팅의 이론적 가능성을 제시했다. 1981년, 리처드 파인만은 고전 컴퓨터로는 양자 역학을 효율적으로 시뮬레이션하기 어렵다는 점을 지적하며, 양자 컴퓨터의 필요성을 강조했다.

1994년, 피터 쇼어는 쇼어의 알고리즘을 발표하여, 양자 컴퓨터가 정수 인수분해 문제를 효율적으로 해결할 수 있음을 보였다. 이는 RSA 암호 체계에 대한 잠재적 위협으로 이어져 양자 컴퓨터 연구에 대한 관심을 증폭시켰다. 쇼어의 알고리즘은 n 비트 정수의 소인수 분해를 $\backslash tilde\{O\}\; (n^3)$ 시간 안에 수행하는 반면, 알려진 최선의 고전 알고리즘은 $2^\{O(n^\{1/3\})\}$ 시간이 필요하다.

1996년, 러브 그로버는 그로버의 알고리즘을 통해 양자 컴퓨터가 데이터베이스 검색 속도를 향상시킬 수 있음을 보였다.

2.2. 21세기 발전

2000년대 초, 최초의 5-큐비트 핵자기 공명 컴퓨터 개발, 쇼어의 알고리즘 증명 등 양자 우위 달성을 위한 기술적 진전이 이루어졌다. 2011년, D-Wave Systems는 최초의 상업용 양자 컴퓨터를 판매하기 시작했다.

구글(Google)은 2017년 말까지 49개의 초전도 큐비트 배열을 사용하여 양자 우월성을 시연할 계획을 발표했다. 2019년, 구글은 시커모어 양자 컴퓨터를 이용해 특정 문제에서 슈퍼컴퓨터보다 빠른 계산 속도를 달성했다고 발표했다. 파이낸셜 타임스의 보도에 따르면, 시커모어 양자 컴퓨터는 53개의 큐비트로 구성되어 있으며, 당시 세계 1위 슈퍼컴퓨터였던 서밋이 1만 년 걸려 풀 문제를 3분 20초 만에 해결하여, 세계 최초로 양자 컴퓨터가 슈퍼 컴퓨터 성능을 뛰어넘는 사건이 발생했다. 그러나 경쟁사인 IBM은 구글의 주장에 대해 이의를 제기하며, 실제로는 2.5일이 걸릴 수 있다고 주장했다.

2020년 12월, 중국과학기술대학교(USTC) 연구팀은 가우스 보손 샘플링을 이용한 양자 컴퓨터 주장을 통해 양자 우월성을 달성했다고 발표했다. 2021년, 중국 연구팀은 주장 2.0과 조충지라는 두 대의 슈퍼컴퓨터를 구축하여 양자 우월성을 보고했다. 2022년, Xanadu는 보손 샘플링 실험 결과를 보고했다. 2024년, D-Wave Systems는 양자 어닐링 기반 프로세서를 사용하여 텐서 네트워크 및 신경망을 포함한 고전적 방법보다 뛰어난 실험을 보고했다.

3. 계산 복잡도

양자 복잡도 이론은 양자 튜링 기계를 기반으로 양자 컴퓨터의 계산 능력을 연구한다. 양자 정보는 고전적 정보의 일반화이므로, 양자 컴퓨터는 모든 고전적 알고리즘을 시뮬레이션할 수 있다. BQP(Bounded-error Quantum Polynomial time)는 양자 컴퓨터가 다항 시간 내에 해결할 수 있는 결정 문제의 집합이다. 고전적 계산으로는 불가능한 것을 증명하는 어려움이 양자 우월성 입증의 핵심 과제이다. 예/아니오 응답이 필요한 결정 문제와 달리, 샘플링 문제는 확률 분포에서 샘플을 추출하는 문제로, 양자 우월성 입증에 활용된다. 임의의 양자 회로의 출력에서 효율적으로 샘플링할 수 있는 고전적 알고리즘이 있는 경우, 다항 시간 계층 구조는 일반적으로 매우 가능성이 낮다고 간주되는 세 번째 수준으로 축소될 것이다. 보존 샘플링은 더 구체적인 제안이며, 고전적 난이도는 큰 행렬의 영구를 계산하는 것이 어렵다는 것에 달려 있으며, 이는 #P-완전 문제이다.

4. 제안된 실험

NISQ 장치라고 불리는 현재 기술을 사용하여 양자 계산 우위를 입증하기 위한 몇 가지 제안이 있다. 이러한 제안은 다음과 같다.

* 잘 정의된 계산 문제
* 이 문제를 해결하기 위한 양자 알고리즘
* 이 문제를 해결하기 위한 최상의 고전 알고리즘 비교
* 합리적인 가정을 전제로, 고전 알고리즘이 현재 알고리즘보다 훨씬 더 나은 성능을 낼 수 없다는 복잡성 이론적 논증 (따라서 양자 알고리즘은 여전히 초다항 속도 향상을 제공)

4.1. 쇼어의 알고리즘

쇼어의 알고리즘은 n 비트 정수의 소인수 분해를 \(\tilde{O} (n^3)\) 시간 안에 수행한다. 반면에, 가장 잘 알려진 고전적 알고리즘은 \(2^{O(n^{1/3})}\) 시간이 필요하며, 이 문제의 복잡성에 대한 최상의 상한은 \(O(2^{n/3+o(1)})\)이다. 이 알고리즘은 정수 인수분해로 귀착되는 모든 문제를 고속화하며, 홀수 차수의 체 위의 행렬군에 대한 멤버십 문제를 포함한다.

이 알고리즘은 양자 컴퓨터에 대해 실용적이면서 역사적으로도 중요하다. 고전 컴퓨터로는 풀기 어렵다고 여겨지는 실제 문제에 대해 제안된 최초의 다항 시간 양자 알고리즘이기 때문이다. 즉, RSA 암호 체계가 안전하다는 합리적인 가정 하에 초다항적 속도 향상을 제공한다.

인수분해는 다른 양자 우월성 제안에 비해 몇 가지 이점이 있다. 인수분해 알고리즘이 풀 수 없을 정도로 느린 대규모 사례의 경우에도, 정수를 곱하기만 하면 고전 컴퓨터로 빠르게 결과를 확인할 수 있기 때문이다. 그러나 현재 기술로는 대규모 숫자에 대한 쇼어의 알고리즘 구현이 불가능하므로, 양자 우월성을 입증하기 위한 전략으로는 추구되지 않고 있다.

4.2. 보손 샘플링

보손 샘플링은 동일한 광자를 선형 광학 네트워크를 통해 전송하는 것을 기반으로 한다. 이는 몇 가지 복잡성 이론적 추측(가우스 행렬의 퍼먼넌트 계산이 #P-Hard이고 다항식 위계가 붕괴되지 않는다는 가정)을 바탕으로 고전 컴퓨터로는 풀 수 없는 특정 샘플링 및 검색 문제를 해결할 수 있다. 그러나 충분한 손실과 노이즈가 있는 시스템에서 보손 샘플링을 효율적으로 시뮬레이션할 수 있음이 밝혀졌다.

현재까지 보손 샘플링의 가장 큰 실험적 구현은 6개의 모드를 가지고 있어 한 번에 최대 6개의 광자를 처리할 수 있었다. 보손 샘플링을 시뮬레이션하기 위한 최상의 제안된 고전 알고리즘은 n개의 광자와 m개의 출력 모드가 있는 시스템의 경우 $O(n2^n+mn^2)$ 시간에 실행된다. 이 알고리즘은 보손 샘플링을 사용하여 양자 우위를 입증하는 데 50개의 광자가 필요하다는 추정치를 제시한다.

4.3. 무작위 양자 회로의 출력 분포 샘플링

임의의 양자 회로를 시뮬레이션하는 데 가장 잘 알려진 알고리즘은 큐비트 수에 따라 지수적으로 증가하는 시간이 필요하며, 한 연구팀은 약 50개의 큐비트만으로도 양자 우위를 입증하기에 충분할 것이라고 추정했다. 2018년 Bouland, Fefferman, Nirkhe, 바지라니는 효율적으로 임의 양자 회로를 시뮬레이션하려면 계산적 다항식 계층이 붕괴되어야 한다는 이론적 증거를 제시했다. 구글은 2017년 말까지 49큐비트 칩을 제작 및 실행하여 양자 우위를 입증하겠다는 의사를 발표했는데, 이 칩은 현재의 모든 고전 컴퓨터로는 합리적인 시간 내에 접근할 수 없는 분포를 샘플링할 수 있었다. 당시 고전 슈퍼컴퓨터에서 실행되는 가장 큰 범용 양자 회로 시뮬레이터는 48개의 큐비트를 시뮬레이션할 수 있었다. 그러나 특정 종류의 회로의 경우 56개의 큐비트를 사용한 더 큰 양자 회로 시뮬레이션이 가능했다. 이는 양자 우위를 입증하기 위해 큐비트 수를 늘려야 할 수도 있다.

2019년 10월 23일, 구글은 Nature에 "프로그래밍 가능한 초전도 프로세서를 사용한 양자 우위"라는 제목의 연구 결과를 발표했는데, 이 연구에서는 벤치마크 테스트를 수행하기 위해 빠르고 고충실도의 양자 논리 게이트를 수행할 수 있는 새로운 53큐비트 프로세서인 "시커모어"를 개발했다. 구글은 자사의 머신이 목표 계산을 200초 만에 수행했으며, 동일한 문제를 해결하는 데 세계에서 가장 빠른 슈퍼컴퓨터에서 10,000년이 걸릴 것이라고 추정했다. IBM은 이 주장에 이의를 제기하며, 개선된 고전 알고리즘을 사용하면 동일한 슈퍼컴퓨터에서 이 문제를 이틀 반 만에 해결할 수 있다고 주장했다.

5. 비판 및 논쟁

2019년 파이낸셜타임스는 구글이 양자우월성에 도달했다고 보도했지만, 경쟁사인 IBM은 이에 대해 회의적인 반응을 보였다. IBM은 구글의 시커모어 양자 컴퓨터가 난수 발생 및 검증이라는 제한적인 작업만 수행 가능하다고 폄하했다. 또한 서미트 (슈퍼컴퓨터)로 1만 년 걸린다는 문제도 실제로는 2일 반이면 해결 가능하다며 구글의 발표를 반박했다.

IBM은 양자컴퓨터와 고전 컴퓨터는 서로 다른 작업을 잘 수행하므로 '양자우월성'이라는 개념 자체에 대해서도 의문을 제기했다.

5.1. 오류 민감성

양자 컴퓨터는 디코히어런스와 잡음 때문에 고전 컴퓨터보다 오류에 훨씬 더 취약하다. 양자 임계값 정리에 따르면, 각 컴퓨터 사이클에서 발생하는 오류가 특정 숫자 미만이라는 가정 하에, 잡음이 있는 양자 컴퓨터가 양자 오류 정정 코드를 사용하여 잡음이 없는 양자 컴퓨터를 시뮬레이션할 수 있다. 수치 시뮬레이션 결과에 따르면 해당 숫자는 최대 3%가 될 수 있다. 그러나 오류 정정에 필요한 자원이 큐비트 수에 따라 어떻게 확장될지는 아직 확실하게 알려져 있지 않다. 회의론자들은 확장된 양자 시스템에서 잡음의 알려지지 않은 거동이 양자 컴퓨팅을 성공적으로 구현하고 양자 우월성을 입증하는 데 잠재적인 장애물이 될 수 있다고 지적한다.

5.2. "양자 우월성" 용어 논쟁

"우월성(supremacy)"이라는 용어가 백인 우월주의를 연상시킨다는 비판이 제기되었다. 13명의 연구자들은 네이처에 논평 기사를 내고 "양자 이점(quantum advantage)"이라는 대체 용어를 제안했다.

이 용어를 제안한 캘리포니아 공과대학교의 이론 물리학 교수인 존 프레스킬은 양자 컴퓨터가 고전 컴퓨터를 능가하는 지점을 명확히 표현하기 위해 해당 용어를 선택했다고 설명했다. 그는 "양자 이점"이라는 용어가 자신이 전달하고자 하는 의미를 충분히 담아내지 못한다고 생각했다. "이점"은 양자 컴퓨터가 고전 컴퓨터보다 약간의 우위를 점한다는 의미로 해석될 수 있지만, "우월성"은 어떤 고전 컴퓨터보다 완전한 우위를 더 잘 나타낸다는 것이다.

필립 볼은 2020년 12월에 네이처에서 "양자 이점"이라는 용어가 "대체로" "양자 우월성"이라는 용어를 대체했다고 썼다.