양자 우월성

직관적 비유

100명이 달려들어도 수천 년 걸릴 미로 찾기를 양자 컴퓨터는 단 몇 분 만에 풀어낸다고 상상해 보자. '양자 우월성'은 바로 그 순간—양자 장치가 고전 세계의 챔피언을 처음으로 앞지르는 순간—을 가리키는 개념이다.

엄밀한 정의

양자 우월성(quantum supremacy)은 존 프레스킬(John Preskill)이 2012년 제안한 용어로, 특정 계산 과제에서 양자 프로세서의 수행 시간이 최선의 고전 알고리즘 대비 지수적(exponential)으로 짧아지는 체제를 말한다. 2019년 구글은 53큐비트 프로세서 *시커모어(Sycamore)*로 무작위 양자 회로 샘플링(random circuit sampling) 문제를 약 200초에 해결했으며, 당시 세계 최고 슈퍼컴퓨터로는 약 10,000년이 소요된다고 추산했다. 수식으로는 고전 시뮬레이션 복잡도가 $\mathcal{O}(2^n)$ 이상일 때 양자 장치가 $\mathcal{O}(\text{poly}(n))$에 근접함을 보이는 것으로 표현된다.

중요성과 응용

양자 우월성은 실용적 응용보다 원리적 가능성의 증명에 가깝다. 이를 발판으로 오류 정정(error correction)과 알고리즘 개발이 가속화되며, 장기적으로 암호 해독·신약 개발·최적화 문제 등 산업 전반에 파급될 것으로 기대된다. 최근에는 '양자 이점(quantum advantage)'이라는 용어가 보다 실용적·중립적 표현으로 병행 사용된다.