양자 이점

양자 이점 (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})$ 가속은 공급망·금융 포트폴리오에 적용 연구 중
• 양자 시뮬레이션: 분자·재료 모델링에서 고전 슈퍼컴퓨터 대비 지수 우위 기대
• 기준선: 양자 이점 입증은 양자 컴퓨팅 산업화의 마일스톤으로 간주됨