고전 컴퓨터와의 비교, 양자 이점
<양자 기술백서 |
┗<양자컴퓨팅의 구현|
┗<하드웨어별 개발 현황|
개요
양자 우위(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] 현재, 프로그래밍이 가능한 양자 컴퓨터는 여전히 오류를 가지고 있으며, 큐비트 개수는 불과 53개에 불과하다.
수십 개의 큐비트 개수와 여러 오류들을 가지고 있는 양자 컴퓨터이지만 이를 이용하여 양자 우월성을 보이는 연구가 최근 활발히 진행되고 있다. 특히, 현존하는 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. (2017), “Quantum computational supremacy”, Nature, 549(7671) : 203.
- ↑ Gidney, C., & Ekerå, M. (2019), “How to factor 2048 bit rsa integers in 8 hours using 20 million noisy qubits”, arXiv preprint arXiv:1905.09749.
- ↑ Gibney, E. (2019), “Hello quantum world! Google publishes landmark quantum supremacy claim”, Nature, 574(7779) : 461.
- ↑ Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J. C., Barends, R., ... & Burkett, B. (2019), “Quantum supremacy using a programmable superconducting processor”, Nature, 574(7779) : 505.
- ↑ Ball, P. (2020), “Physicists in China challenge Google's' quantum advantage”, Nature, 588(7838) : 380.
- ↑ Zhong, H. S., Wang, H., Deng, Y. H., Chen, M. C., Peng, L. C., Luo, Y. H., ... & Hu, P. (2020), “Quantum computational advantage using photons”, Science, 370(6523) : 1460.
- ↑ Aaronson, S., & Arkhipov, A. (2011, June, “The computational complexity of linear optics”, In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, 333.