고전 컴퓨터와의 비교, 양자 이점
<양자 기술백서 |
┗<양자컴퓨팅의 구현|
개요
양자 우위(quantum supremacy)란 양자 컴퓨터의 연산 능력이 월등히 뛰어나 그 어떤 고전 컴퓨터로도 동등한 수준의 연산을 수행할 수 없는 경우를 의미한다. 양자 컴퓨터가 고전 컴퓨터보다 연산 능력이 얼마나 좋은지 알기 위해서는 각각의 연산 능력을 정량화하여 서로 비교를 해야 정확히 알 수 있다. 하지만, 불행하게도 대부분 문제들의 경우 고전컴퓨터가 얼마나 잘 풀 수 있는지에 관한 이론과 그 증명이 아직 잘 알려져 있지 않다. 또한, 현존하는 양자 컴퓨터는 아직 양자역학적인 오류들로부터 자유롭지 않은 원형(prototype)이기 때문에, 우위(supremacy)라는 표현이 적절하지 않다는 의견들이 나오면서 양자 이점(quantum advantage)라는 용어도 많이 사용하고 있다.
양자 컴퓨터를 이용한 연산이 양자 우위라고 주장하기 위해서는 주로 몇 가지 조건들이 필요하다는 것이 알려져 있다.[1] 우선, 계산을 하기 위한 문제가 잘 정의되어 있어야한다. 두번째, 문제를 해결하기 위한 양자 알고리즘이 있어야 한다. 세번째, 동일한 문제를 고전컴퓨터로도 해결할 수 있어야 한다. 네번째, 복잡 이론의 가정(complexity-theoretical assumption)이 있어야한다. 마지막으로, 양자 알고리듬의 계산 성능과 고전 알고리듬의 계산 성능을 명확하게 구분할 수 있어야 한다.
자연수의 소인수분해 문제의 경우 위의 조건을 잘 만족한다. 이진법으로 기술된 자연수를 N이라고 했을 때, 고전 알고리듬을 이용하여 소인수분해를 할 경우 그 연산량이 $$2^{O\left( N^{1/3} \right)}$$ 로 알려져 있다. 반면, 양자 알고리듬인 쇼어 알고리듬을 이용하면 $$O\left( \log N^{3} \right)$$의 다항 시간이 걸린다 . 따라서 적당한 크기의 자연수에 대해서는 고전컴퓨터와 양자 컴퓨터의 연산 능력을 명확하게 비교할 수 있고, 충분히 큰 자연수에 대해서는 쇼어 알고리듬이 더 빠르다는 것을 알 수 있다. 하지만 구글 팀에서 발표한 논문에 의하면, 쇼어 알고리듬이 2048비트의 정수를 인수분해하기 위해서는 이상적인 양자컴퓨터의 큐비트가 대략 20,000,000개 정도 필요하다고 예측하였다.[2] 2021년 현재, 프로그래밍이 가능한 양자 컴퓨터는 여전히 오류를 가지고 있으며, 가장 많은 큐비트 개수는 IBM의 Hummingbird 칩으로 65개에 불과하다.
수십 개의 큐비트 개수와 여러 오류들을 가지고 있는 양자 컴퓨터이지만 이를 이용하여 양자 우월성을 보이는 연구가 최근 활발히 진행되고 있다. 특히, 현존하는 NISQ 컴퓨터로 샘플링 문제(무작위 양자 회로 샘플링 및 보손 샘플링 문제들)를 다루어 양자 우월성을 입증한 연구결과들이 있다. 이에 대해 간단하게 소개하고자 한다.
구글의 시카모어 (Sycamore)
구글(Google)은 53개의 초전도체 큐비트로 구성된 양자 컴퓨터 프로세서인 시카모어(Sycamore)칩을 개발하였다. 2019년 10월, 구글 팀은 고전 컴퓨터로는 다룰 수 없는 문제를 시카모어를 이용하여 문제를 해결했다는 연구 결과를 네이처 학술지에 발표하였다.[4]
구글이 다룬 문제는 무작위 양자 회로 샘플링 문제로서, 시카모어를 통해 임의의 무작위로 양자 연산을 적용한 양자 회로를 여러 번 시행하여 가능한 모든 비트열(bit string)의 결과값과 그 확률 분포를 이해하는 것이 목적이다. 구글 팀은 시카모어가 이 문제를 해결하는데 단지 3분 20초의 시간이 소요되었으며, 이는 슈퍼컴퓨터 서밋(Summit)을 이용하여 풀게 되면 대략 10,000년이 걸릴 것이라고 추정하였다.
이후 IBM 측에서 바로 발표한 논문에서는 서밋(Summit)을 사용하여 약간의 다른 방법을 이용하면 2.5일 걸린다고 주장하였다. IBM의 주장을 따르면 이는 양자 우월이라고 명백하게 말하기는 힘들지만, 고전 컴퓨터를 이용하여 계산하는 것보다는 속도가 더 빠르다는 것을 확실하다. 따라서 이를 구현한 구글의 시카모어칩은 양자컴퓨터 이정표라 볼 수 있는 실험이다.
중국과학기술대학의 구장 (Jiuzhang in University of Science and Technology of China)
2020년 12월 중국과학기술대학(University of Science and Technology of China)에서 광자 기반 76큐비트 양자컴퓨터 구장(Jiuzhang)을 이용하여 보손 샘플링(boson sampling) 문제를 해결한 연구 내용을 사이언스 학술지를 통하여 발표하였다.[6]
스콧 아론슨(Scott Aronson)과 알렉스 아르키포프(Alex Arkhipov)가 처음 제안한 보손 샘플링은 보손 입자인 광자들의 위치 확률 분포를 계산하는 문제이다.[7] 조금 더 자세히 말하자면, 레이저 펄스에서 정보를 광자의 위치와 편광 상태에 부여한다. 이 후 광자들의 양자 파동 함수들이 서로 간섭하면 입자들의 위치와 편광 값은 무작위가 된다. 마지막으로 광자 검출기를 이용하여 결과값들의 확률분포를 측정한다. 이러한 일련의 과정들은 기존 고전 컴퓨터로는 불가능한 계산을 인코딩하는 효과를 지닌다. 수십 개의 보손 입자를 고려하게 되면, 이 문제는 현존하는 고전 컴퓨터로는 풀지 못한다는 것이 수학적으로 증명되었다(#P-hard 문제로써 이는 NP-hard 문제보다 더 어렵다고 알려져있다).
이러한 보손 샘플링 문제를 중국과학기술대학 연구팀이 상온 광자 회로(photonic circuit)에서 200초 내에 풀어냈다. 그들은 이 문제가 슈퍼컴퓨터로 풀 경우 대략적으로 25억년이 걸린다고 추정했다. 대략 1014배의 양자 이점을 보인 셈이다. 구글의 시카모어(Sycamore)랑 비교했을 때, 구장(Jiuzhang)은 프로그래밍이 불가능하다는 단점이 있지만, 최근 연구 결과에 따르면 보손 샘플링 문제가 단순히 양자 이점(quantum advantage)을 보일 뿐만 아니라, 그래프 이론, 양자 화학, 그리고 기계학습 분야에 잠재적인 활용 가능성을 지니고 있다고 알려졌다.
참고 문헌
- ↑ Harrow, A. W. & Montanaro, A. Quantum computational supremacy. Nature 549, 203-209, (2017). doi:[1].
- ↑ Gidney, C. & Ekerå, M. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum 5, 433, (2021). doi:10.22331/q-2021-04-15-433.
- ↑ Gibney, E. (2019), Hello quantum world! Google publishes landmark quantum supremacy claim, Nature, 574(7779) : 461. https://doi.org/10.1038/d41586-019-03213-z
- ↑ Arute, F. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505-510, (2019). doi:10.1038/s41586-019-1666-5.
- ↑ Ball, P. (2020), Physicists in China challenge Google's quantum advantage, Nature, 588(7838) : 380. https://doi.org/10.1038/d41586-020-03434-7
- ↑ Zhong, H.-S. et al. Quantum computational advantage using photons. Science 370, 1460-1463, (2020). doi:10.1126/science.abe8770.
- ↑ Aaronson, S. & Arkhipov, A. in Proceedings of the forty-third annual ACM symposium on Theory of computing pp.333–342 (Association for Computing Machinery, San Jose, California, USA, 2011).