Definition
양자 컴퓨터가 특정 문제를 고전 컴퓨터보다 더 빠르거나 효율적으로 풀 수 있음을 실험적·이론적으로 입증한 상태. 단순한 속도 차이가 아닌, 자원 스케일링의 질적 우위를 의미한다.
양자 이점 (Quantum Advantage)
(1) 직관적 비유
거대한 미로를 탐색한다고 상상해보자. 고전 컴퓨터는 한 번에 하나의 경로를 시도하지만, 양자 컴퓨터는 중첩(superposition) 을 이용해 수많은 경로를 동시에 탐색하는 것처럼 작동한다. 양자 이점이란, 이 병렬적 탐색 능력이 실제 문제에서 고전 방식보다 확실히 유리한 결과를 낳는 시점이 도래했음을 뜻한다.
(2) 엄밀한 정의
어떤 계산 문제 $\mathcal{P}$에 대해, 고전 알고리즘의 최선 복잡도가 $T_{\text{classical}}(n)$이고 양자 알고리즘이 $T_{\text{quantum}}(n)$일 때,
$$T_{\text{quantum}}(n) = o\bigl(T_{\text{classical}}(n)\bigr)$$
이 점근적으로 성립하거나, 동일한 시간 내 해결 불가능한 규모의 문제를 양자 장치가 실제로 처리했을 때 양자 이점이 있다고 말한다. 이론적 이점(예: Shor 알고리즘의 지수적 가속)과 실험적 시연(예: Google의 2019년 무작위 회로 샘플링)을 구분하는 것이 중요하다.
(3) 중요성·응용
- 암호학: Shor 알고리즘은 RSA를 다항 시간에 해독 → 양자 내성 암호 전환의 동력
- 최적화·물류: Grover 탐색의 $O(\sqrt{N})$ 가속은 공급망·금융 포트폴리오에 적용 연구 중
- 양자 시뮬레이션: 분자·재료 모델링에서 고전 슈퍼컴퓨터 대비 지수 우위 기대
- 기준선: 양자 이점 입증은 양자 컴퓨팅 산업화의 마일스톤으로 간주됨
