쇼어 알고리즘

직관적 비유

자물쇠(공개키 암호)의 비밀번호를 찾는 상황을 상상해 보자. 고전 컴퓨터는 수많은 열쇠를 하나씩 대입해야 하지만, 쇼어 알고리즘을 갖춘 양자 컴퓨터는 모든 열쇠를 동시에 시험하는 것과 유사한 방식으로, 지수적으로 오랜 시간이 걸리던 작업을 극적으로 단축한다.

엄밀한 정의

$N$을 소인수분해하는 문제를 주기 탐색(period finding) 문제로 환원한다. 임의의 정수 $a$에 대해 함수 $f(x)=a^x\mathrm{mod}N$의 주기 $r$을 양자 푸리에 변환(QFT)을 사용해 $O({\log }^{3}N)$ 게이트로 찾아낸다. $r$을 알면 $\gcd (a^{r/2}\pm 1,N)$으로 비자명한 인수를 고전적으로 계산할 수 있다. 이로써 고전 알고리즘의 준지수 시간 $O(e^{O({\log }^{1/3}N)})$에 비해 다항 시간 $O(\text{poly}(\log N))$으로 수행 가능하다.

중요성·응용

• RSA, ECC 등 공개키 암호 체계의 안전성 근거가 소인수분해 및 이산 로그의 어려움에 있으므로, 충분히 큰 양자 컴퓨터가 실현될 경우 현행 인터넷 보안 인프라가 위협받는다.
• 이 때문에 양자 내성 암호(Post-Quantum Cryptography) 표준화가 NIST를 중심으로 활발히 진행되고 있다.
• 양자 알고리즘 이론 발전의 핵심 이정표로, 양자 우위(quantum advantage)의 대표 사례로 꼽힌다.