쇼어 알고리즘

이 Qiskit in Classrooms 모듈을 사용하려면 다음 패키지가 설치된 Python 환경이 필요합니다:

• qiskit v2.1.0 이상
• qiskit-ibm-runtime v0.40.1 이상
• qiskit-aer v0.17.0 이상
• qiskit.visualization
• numpy
• pylatexenc

위 패키지 설치 및 설정 방법은 Qiskit 설치 가이드를 참고하세요. 실제 양자 컴퓨터에서 작업을 실행하려면, IBM Cloud 계정 설정 가이드의 단계를 따라 IBM Quantum® 계정을 만들어야 합니다.

이 모듈은 테스트를 거쳤으며 QPU 시간을 3초 사용했습니다. 이는 추정치이며, 실제 사용량은 다를 수 있습니다.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

소개

1990년대 초, 고전 컴퓨터가 풀기 어려운 문제를 양자 컴퓨터로 해결할 수 있을지도 모른다는 기대가 높아졌습니다. 몇몇 재능 있는 컴퓨터 과학자들이 일부 틈새적이고 인위적인 문제에서 양자 컴퓨팅의 강점을 보여주는 알고리즘을 고안하기는 했지만, 양자 컴퓨팅 분야를 확실하게 혁신할 "킬러 앱"을 찾아낸 사람은 없었습니다. 그러다가 1994년, 피터 쇼어가 지금은 쇼어 알고리즘이라고 불리는 대형 수 인수분해 알고리즘을 고안해냈습니다.

당시 큰 수의 소인수를 찾는 것이 고전 컴퓨터에게 매우 어렵다는 사실은 잘 알려져 있었습니다. 실제로 인터넷 보안 프로토콜은 바로 이 어려움에 의존하고 있었습니다. 쇼어는 이론적인 미래의 양자 컴퓨터에 더 까다로운 단계 일부를 맡겨, 이 인수들을 지수적으로 더 효율적으로 찾는 방법을 발견했습니다.

이 모듈에서는 쇼어 알고리즘을 살펴봅니다. 먼저 알고리즘의 배경을 좀 더 설명하고, 풀고자 하는 문제를 명확히 정의하며, 사이버 보안과의 관련성을 설명합니다. 다음으로 모듈러 수학에 대한 기초 개념과 이를 인수분해 문제에 적용하는 방법을 소개하고, 인수분해가 "위수 찾기(order-finding)"라는 다른 문제로 어떻게 귀결되는지 보여줍니다. 이전 모듈에서 배웠던 양자 푸리에 변환과 양자 위상 추정이 어떻게 활용되는지, 그리고 이를 사용해 위수 찾기 문제를 어떻게 푸는지 설명합니다.

마지막으로 실제 양자 컴퓨터에서 쇼어 알고리즘을 실행해 봅니다! 다만, 이 알고리즘이 진정으로 유용해지려면 아직 몇 년은 더 걸릴 대형 내결함성 양자 컴퓨터가 필요하다는 점을 기억하세요. 따라서 알고리즘이 어떻게 작동하는지 보여주기 위해 작은 수를 인수분해해 보겠습니다.

인수분해 문제

인수분해 문제의 목표는 수 $N$의 소인수를 찾는 것입니다. 일부 수 $N$에 대해서는 이것이 꽤 쉽습니다. 예를 들어 $N$이 짝수라면 소인수 중 하나는 2입니다. $N$이 소수의 거듭제곱, 즉 어떤 소수 $p$에 대해 $N=p^k$인 경우에도 $p$를 찾기가 비교적 쉽습니다. $N$의 $k$번째 근을 근사한 뒤 $p$가 될 수 있는 근처의 소수를 찾으면 됩니다.

하지만 $N$이 홀수이고 소수의 거듭제곱이 아닌 경우가 고전 컴퓨터가 어려움을 겪는 상황입니다. 쇼어 알고리즘이 다루는 경우도 바로 이것입니다. 이 알고리즘은 $N=pq$를 만족하는 두 인수 $p$와 $q$를 찾습니다. 모든 인수가 소수가 될 때까지 재귀적으로 적용할 수 있습니다. 다음 절에서 이 문제를 어떻게 해결하는지 살펴보겠습니다.

사이버 보안과의 관련성

오늘날 일반적으로 사용되는 RSA를 포함하여, 많은 암호화 방식이 큰 수를 인수분해하기 어렵다는 사실을 기반으로 구축되었습니다. RSA에서는 두 개의 큰 소수를 곱하여 $N = p\cdot q$를 구하는 방식으로 공개 키를 만듭니다. 그러면 누구든 이 공개 키를 사용하여 데이터를 암호화할 수 있습니다. 하지만 개인 키, 즉 $p$와 $q$를 가진 사람만이 그 데이터를 복호화할 수 있습니다.

$N$을 쉽게 인수분해할 수 있다면 누구든 $p$와 $q$를 알아내어 암호화를 깰 수 있을 것입니다. 하지만 그렇지 않습니다. 이것은 매우 어려운 문제로 잘 알려져 있습니다. 실제로 1024 비트, 309 자리 십진수로 이루어진 RSA1024라는 수의 소인수는 아직 발견되지 않았습니다. 1991년에 인수분해에 대한 현상금 $100,000이 걸렸음에도 불구하고 말입니다.

쇼어의 해법

1994년 피터 쇼어는 양자 컴퓨터가 고전 컴퓨터보다 지수적으로 더 효율적으로 큰 수를 인수분해할 수 있음을 깨달았습니다. 그의 통찰은 이 인수분해 문제와 모듈러 산술 사이의 관계에 기반합니다. 모듈러 산술에 대한 간단한 기초를 살펴본 후, 이를 이용해 $N$을 인수분해하는 방법을 알아보겠습니다.

모듈러 산술

모듈러 산술은 순환하는 방식으로 수를 세는 체계입니다. 일반적인 방식인 0, 1, 2 등의 정수로 시작하지만, 어느 시점에서 주기 $N$이 지나면 다시 처음부터 시작합니다. 예를 들어 살펴보겠습니다. 주기가 5라고 하면, 수를 셀 때 원래라면 5가 되어야 할 자리에서 다시 0으로 돌아갑니다:

$0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, ...$

이는 "모듈로-5" 세계에서 5가 0과 동일하기 때문입니다. $5\bmod 5 \ = 0$이라고 표현합니다. 실제로 5의 모든 배수는 $0\bmod 5$와 동일합니다.

이해도 확인

아래 질문을 읽고 답을 생각해 본 후, 삼각형을 클릭하여 해답을 확인하세요.

모듈러 산술을 사용하여 다음 문제를 풀어보세요:

오전 8시에 긴 대륙 횡단 기차 여행을 출발합니다. 기차 여행은 60시간 동안 지속됩니다. 도착했을 때 몇 시입니까?

정답:

하루는 24시간이므로 주기는 24입니다. 따라서 이 문제는 모듈러 산술로 다음과 같이 표현할 수 있습니다:

$(8+60)\text{mod}(24) = 20$

따라서 목적지에 20:00, 즉 오후 8시에 도착하게 됩니다.

$\mathbb{Z}_N$과 $\mathbb{Z}_N^*$

두 집합 $\mathbb{Z}_N$과 $\mathbb{Z}_N^*$를 도입하면 유용한 경우가 많습니다. $\mathbb{Z}_N$은 단순히 "모듈로-$N$" 세계에 존재하는 수들의 집합입니다. 예를 들어 모듈로-5로 수를 셀 때 집합은 $\mathbb{Z}_5=\{0,1,2,3,4\}$가 됩니다. 또 다른 예로 $\mathbb{Z}_{15} = \{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$입니다. $\mathbb{Z}_N$의 원소들에 대해 덧셈과 곱셈(모듈로 $N$)을 수행할 수 있으며, 각 연산의 결과도 $\mathbb{Z}_N$의 원소입니다. 따라서 $\mathbb{Z}_N$은 *환(ring)*이라는 수학적 객체가 됩니다.

쇼어 알고리즘에서 특히 중요한 $\mathbb{Z}_N$의 특수한 부분 집합이 있습니다. 각 원소와 $N$ 사이의 최대공약수가 1인, 즉 각 원소가 $N$과 "서로소"인 수들의 부분 집합입니다. 이 수들의 집합에 모듈러 곱셈 연산을 더하면 *군(group)*이라는 또 다른 수학적 객체가 형성됩니다. 이 군을 $\mathbb{Z}_N^*$라고 부릅니다. $\mathbb{Z}_N^*$(그리고 일반적인 유한군)에서 임의의 원소 $a \in \mathbb{Z}_N^*$를 선택하여 $a$를 반복해서 곱하면 결국 항상 1이 나옵니다. $a$를 자기 자신에 곱하여 1을 얻기 위한 최소 횟수를 $a$의 **위수(order)**라고 합니다. 이 사실은 아래에서 수를 인수분해하는 방법을 논의할 때 매우 중요합니다.

이해도 확인

아래 질문을 읽고 답을 생각해 본 후, 삼각형을 클릭하여 해답을 확인하세요.

$\mathbb{Z}_{15}^*$는 무엇인가요?

정답:

$\mathbb{Z}_{15}^* = \{1,2,4,7,8,11,13,14\}$

다음 수들은 제외했습니다:

$$\begin{aligned} 3: GCD(3,15)=3 \\ 5: GCD(5,15)=5 \\ 6: GCD(6,15)=3 \\ 9: GCD(9,15)=3 \\ 10: GCD(10,15)=5 \\ 12: GCD(12,15)=3 \\ \end{aligned}$$

$\mathbb{Z}_{15}^*$의 각 원소의 위수는 무엇인가요?

정답:

위수 $r$은 각 원소 $a$에 대해 $a^r\text{mod}(15)=1$을 만족하는 가장 작은 수입니다.

$$\begin{aligned} 1^1\text{mod}(15) = 1, r=1 \\ 2^4\text{mod}(15) = 1, r=4 \\ 4^2\text{mod}(15) = 1, r=2 \\ 7^4\text{mod}(15) = 1, r=4 \\ 8^4\text{mod}(15) = 1, r=4 \\ 11^2\text{mod}(15) = 1, r=2 \\ 13^4\text{mod}(15) = 1, r=4 \\ 14^2\text{mod}(15) = 1, r=2 \\ \end{aligned}$$

$\mathbb{Z}_{15}^*$의 수들에 대한 위수를 찾을 수 있었지만, 이것은 일반적으로 더 큰 $N$에 대해서는 쉬운 작업이 아닙니다. 이것이 인수분해 문제의 핵심이며 양자 컴퓨터가 필요한 이유입니다. 나머지 노트북을 진행하면서 그 이유를 알게 될 것입니다.

인수분해 문제에 모듈러 산술 적용하기

$N=pq$를 만족하는 인수 $p$와 $q$를 찾는 핵심은 다음 조건을 만족하는 다른 정수 $x$를 찾는 것입니다:

$x^2 \equiv 1 \bmod N$ 이고 $x \not\equiv \pm 1 \bmod N.$

$x$를 찾는 것이 인수 $p$와 $q$를 찾는 데 어떻게 도움이 될까요? 이제 그 논리를 살펴보겠습니다. $x^2 \equiv 1 \bmod N$이므로 $x^2 - 1 \equiv 0 \bmod N$입니다. 다시 말해, $x^2 - 1$은 $N$의 배수입니다. 따라서 어떤 정수 $l$에 대해:

$x^2 - 1 = l N$

$x^2 - 1$을 인수분해하면:

$(x+1)(x-1) = l N$

초기 가정에서 $x \not\equiv \pm 1 \bmod N$이므로 $N$은 $x+1$ 또는 $x-1$ 중 어느 것도 나누어 떨어지게 하지 않습니다. 따라서 $N$의 두 인수 $p$와 $q$는 각각 $x-1$과 $x+1$을 나누어야 합니다. $p$가 $x-1$의 인수이고 $q$가 $x+1$의 인수이거나, 그 반대입니다. 따라서 $N$과 $x-1$, $x+1$ 각각의 최대공약수(GCD)를 계산하면 인수 $p$와 $q$를 구할 수 있습니다. 두 수 사이의 GCD를 계산하는 것은 예를 들어 유클리드 알고리즘을 사용하여 고전적으로 쉽게 수행할 수 있는 작업입니다.

이해도 확인

아래 질문을 읽고 답을 생각해 본 후, 삼각형을 클릭하여 해답을 확인하세요.

위의 각 논리 단계를 이해하기 어려울 수 있으니, 예제를 통해 직접 풀어보세요. $N=15$, $x=11$을 사용하세요. 먼저 $x^2 \equiv 1 \text{mod}(N)$이고 $x \not\equiv \pm 1 \bmod N$임을 확인하세요. 그런 다음 각 단계를 계속 확인하세요. 마지막으로 $\text{GCD}(11\pm1,15)$를 계산하고 이것이 $15$의 인수임을 확인하세요.

정답:

$11^2 = 121$이며, 이는 $15*8 + 1$이므로 $11^2\bmod 15 = 1$입니다. $\checkmark$

$11 - 1 = 10$이며, 이는 $0\bmod 15$와 동일하지 않습니다. $\checkmark$

$11 + 1 = 12$이며, 이는 $0\bmod 15$와 동일하지 않습니다. $\checkmark$

이제 어떤 정수 $l$에 대해 $(x+1)(x-1) = l N$임을 알고 있습니다. $x$와 $N$을 대입하면: $(12)(10) = l 15$이며 $l = 8$일 때 성립합니다. $\checkmark$

이제 $\text{GCD}(12,15)$와 $\text{GCD}(10,15)$를 계산해야 합니다.

$$\begin{aligned} \text{GCD}(12,15) = 3 \\ \text{GCD}(10,15) = 5 \end{aligned}$$

이렇게 $15$의 인수를 찾았습니다!

알고리즘

어떤 정수 $x$를 찾아서 $x^2 \equiv 1\bmod N$을 만족시키면 $N$을 인수분해하는 데 도움이 된다는 것을 살펴보았습니다. 이제 Shor의 알고리즘 전체를 살펴보겠습니다. 알고리즘의 핵심은 결국 $x$를 찾는 것입니다:

1. 임의의 정수 선택 $1 < a < N$을 만족하는 임의의 정수 $a$를 선택합니다.

• 고전적인 방법으로 $\text{GCD}(a, N)$을 계산합니다.
  • $\text{GCD}(a, N) > 1$이면 이미 인수를 찾은 것입니다. 종료합니다.
  • 그렇지 않으면 계속 진행합니다.

2. $a$를 $N$으로 나눈 위수 $r$ 찾기 $a^r \equiv 1 \pmod N$을 만족하는 가장 작은 양의 정수 $r$을 찾습니다.

3. 위수가 짝수인지 확인

• $r$이 홀수이면 1단계로 돌아가 새로운 $a$를 선택합니다.
• $r$이 짝수이면 4단계로 진행합니다.

4. $x = a^{r/2} \bmod N$ 계산

• $x \not\equiv 1 \pmod N$이고 $x \not\equiv -1 \pmod N$인지 확인합니다.
  • $x \equiv \pm 1 \pmod N$이면 1단계로 돌아가 새로운 $a$를 선택합니다.
• 그렇지 않으면, GCD를 계산하여 인수를 추출합니다:

$$p = \text{GCD}(x-1, N), \quad q = \text{GCD}(x+1, N)$$

이 값들이 $N$의 비자명 인수가 됩니다.

5. 필요 시 재귀적으로 인수분해

• $p$나 $q$가 소수가 아니면 알고리즘을 재귀적으로 적용하여 완전히 인수분해합니다.
• 모든 인수가 소수가 되면 인수분해가 완료됩니다.

이 절차만 보면 왜 양자 컴퓨터가 필요한지 명확하지 않을 수 있습니다. 양자 컴퓨터가 필요한 이유는 2단계, 즉 $a$를 $N$으로 나눈 위수를 찾는 것이 고전적으로는 매우 어려운 문제이기 때문입니다. 복잡도가 $N$에 대해 지수적으로 증가합니다. 하지만 양자 컴퓨터를 사용하면 Quantum Phase Estimation을 활용하여 이를 해결할 수 있습니다. 4단계인 두 정수의 GCD를 구하는 것은 고전적으로도 비교적 쉬운 작업입니다. 따라서 양자 컴퓨터의 능력이 실제로 필요한 단계는 위수 찾기 단계뿐입니다. 이를 인수분해 문제가 위수 찾기 문제로 "귀착된다"고 합니다.

어려운 부분: 위수 찾기

이제 위수 찾기에 양자 컴퓨터를 어떻게 활용하는지 살펴보겠습니다. 먼저 "위수"가 무엇을 의미하는지 명확히 하겠습니다. 물론 위수의 수학적 의미는 이미 설명했습니다: $a^r = 1 \pmod N$을 만족하는 0이 아닌 첫 번째 정수 $r$입니다. 하지만 이 개념에 대해 좀 더 직관적인 이해를 얻어 보겠습니다.

$N$이 충분히 작은 경우, $a$의 각 거듭제곱을 계산하고 그 수에 $N$을 모듈러 연산한 다음, $a^r = 1 \text{mod}(N)$을 만족하는 거듭제곱 $r$을 찾으면 됩니다. 위에서 $N=15$ 예제에서 한 것이 바로 그 방법입니다. 다양한 $a$와 $N$ 값에 대해 이 모듈러 거듭제곱의 그래프를 살펴보겠습니다:

무언가 눈에 띄지 않나요? 이것들은 주기 함수입니다! 그리고 위수 $r$은 주기와 같습니다! 즉, 위수 찾기는 주기 찾기와 동일합니다.

양자 컴퓨터는 함수의 주기를 찾는 데 매우 적합합니다. 이를 위해 Quantum Phase Estimation이라는 알고리즘 서브루틴을 사용할 수 있습니다. QPE와 Quantum Fourier Transform의 관계는 이전 모듈에서 다루었습니다. 자세한 복습이 필요하다면 QFT 모듈이나 John Watrous의 양자 알고리즘 강좌에 있는 Quantum Phase Estimation 강의를 참고하세요. 이제 절차의 핵심을 살펴보겠습니다:

Quantum Phase Estimation(QPE)에서는 유니터리 $U$와 그 유니터리의 고유 상태 $|\psi\rangle$에서 시작합니다. 그런 다음 QPE를 사용하여 대응하는 고유값을 근사합니다. 연산자가 유니터리이므로 고유값은 $e^{2\pi i \theta}$ 형태입니다. 따라서 고유값을 찾는 것은 주기 함수에서 $\theta$ 값을 찾는 것과 같습니다. Circuit은 다음과 같습니다:

제어 Qubit의 수(위 그림에서 상단 $m$개 Qubit)가 근사의 정밀도를 결정합니다.

Shor의 알고리즘에서는 유니터리 연산자 $M_a$에 QPE를 적용합니다:

$M_a|y\rangle \equiv |ay \mod N \rangle .$

여기서 $|y\rangle$은 다중 Qubit 레지스터의 계산 기저 상태를 나타내며, Qubit들의 이진 값이 정수 $y$에 대응합니다. 예를 들어, $N=15$이고 $y = 2$인 경우, 15까지의 숫자를 인코딩하기 위해 4개의 Qubit이 필요하므로 $|y\rangle$는 4-Qubit 기저 상태 $|0010\rangle$으로 표현됩니다. (이 개념이 낯설다면 양자 상태의 이진 인코딩에 대한 복습을 위해 입문 Qiskit in classrooms 모듈을 참고하세요.)

이제 이 유니터리의 고유 상태를 찾아야 합니다. $|1\rangle$ 상태에서 시작하면, $U$를 연속적으로 적용할 때마다 레지스터의 상태가 $a \pmod N$씩 곱해지고, $r$번 적용하면 다시 $|1\rangle$ 상태로 돌아옵니다. 예를 들어 $a = 3$이고 $N = 35$인 경우:

$$\begin{aligned} M_3|1\rangle &= |3\rangle & \\ M_3^2|1\rangle &= |9\rangle \\ M_3^3|1\rangle &= |27\rangle \\ & \vdots \\ M_3^{(r-1)}|1\rangle &= |12\rangle \\ M_3^r|1\rangle &= |1\rangle \end{aligned}$$

따라서 이 사이클의 상태들($|\psi_j\rangle$)의 다음 형태의 중첩 상태:

$|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$

는 모두 $M_a$의 고유 상태입니다. (이 형태 이외의 고유 상태도 더 있습니다. 하지만 위의 형태인 것들만 관심을 가지면 됩니다.)

이해도 확인

아래 질문을 읽고, 답을 생각한 후, 삼각형을 클릭하여 해답을 확인하세요.

$a=2$이고 $N = 15$에 해당하는 유니터리의 고유 상태를 구하세요.

답:

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2^2|1\rangle &= |4\rangle \\ M_2^3|1\rangle &= |8\rangle \\ M_2^4|1\rangle &= |1\rangle \\ \end{aligned}$$

따라서 위수 $r=4$입니다. 관심 있는 고유 상태들은 위에서 거쳐간 모든 상태들의 등비 중첩에 다양한 위상이 붙은 형태입니다:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{1}{4}}|2\rangle+e^{2 \pi i \frac{2}{4}}|4\rangle+e^{2 \pi i \frac{3}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{2}{4}}|2\rangle+e^{2 \pi i \frac{4}{4}}|4\rangle+e^{2 \pi i \frac{6}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{3}{4}}|2\rangle+e^{2 \pi i \frac{6}{4}}|4\rangle+e^{2 \pi i \frac{9}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

이 고유 상태들 중 하나로 Qubit 상태를 초기화할 수 있다고 가정해 봅시다(스포일러 — 실제로는 그렇지 않습니다. 적어도 쉽지는 않습니다. 곧 그 이유와 대안을 설명하겠습니다). 그렇다면 QPE를 사용하여 대응하는 고유값 $\omega_j = e^{2 \pi i \theta_j}$ (여기서 $\theta_j = \frac{j}{r}$)를 추정할 수 있습니다. 그런 다음 간단한 방정식으로 위수 $r$을 구할 수 있습니다:

$r = \frac{j}{\theta_j}.$

하지만 QPE는 $\theta_j$를 추정하는 것이지 정확한 값을 제공하지는 않는다는 점을 기억하세요. 추정값은 $r$과 $r+1$을 구별할 수 있을 만큼 정확해야 합니다. 제어 Qubit의 수 $m$이 많을수록 추정이 더 정확해집니다. 수업 말미의 문제에서 숫자 $N$을 인수분해하기 위해 필요한 최소 $m$을 구하는 문제를 풀게 됩니다.

이제 한 가지 문제를 해결해야 합니다. 위의 설명은 모두 고유 상태 $|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$를 준비하는 것에서 시작합니다. 하지만 $r$을 먼저 알지 못하면 이를 수행할 방법을 모릅니다. 논리가 순환적입니다. 고유 상태를 초기화하지 않고도 고유값을 추정하는 방법이 필요합니다.

$M_a$의 고유 상태에서 시작하는 대신, 초기 상태를 이진수로 $|1\rangle$에 해당하는 $n$-Qubit 상태(즉, $|000...01\rangle$)로 준비할 수 있습니다. 이 상태 자체는 명백히 $M_a$의 고유 상태가 아니지만, 모든 고유 상태 $|\psi_k\rangle$의 중첩입니다:

$|1\rangle = \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle}$

이해도 확인

아래 질문을 읽고, 답을 생각한 후, 삼각형을 클릭하여 해답을 확인하세요.

이전 확인 문제에서 $N=15$, $a=2$에 대해 구한 고유 상태들의 중첩이 $|1\rangle$과 동일함을 검증하세요.

답:

네 개의 고유 상태는 다음과 같았습니다:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

따라서,

$$\begin{aligned} \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle} &= \frac{1}{2}(|\psi_0\rangle + |\psi_1\rangle + |\psi_2\rangle + |\psi_3\rangle ) \\ &= \frac{1}{4}(|1\rangle+|2\rangle+|4\rangle+|8\rangle+|1\rangle+i|2\rangle-|4\rangle-i|8\rangle+|1\rangle-|2\rangle+|4\rangle-|8\rangle + |1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ &= \frac{1}{4}(4|1\rangle) = |1\rangle \end{aligned}$$

이것이 위수 $r$을 찾는 데 어떻게 도움이 될까요? 시작 상태가 위에 나열된 형태의 모든 고유 상태들의 중첩이므로, QPE 알고리즘은 이 고유 상태들에 대응하는 각 $\theta_k$를 동시에 추정합니다. 따라서 마지막에 $m$개 제어 Qubit을 측정하면 무작위로 선택된 고유값 $k \in \{0,1,2,...,r-1\}$ 중 하나에 해당하는 값 $k/r$의 근사값이 나옵니다. 이 Circuit을 몇 번 반복하여 서로 다른 $k$ 값의 샘플 몇 개를 얻으면, 빠르게 $r$을 추론할 수 있습니다.

Qiskit으로 구현하기

앞서 언급했듯이, 현재 하드웨어로는 RSA1024와 같은 큰 수를 인수분해할 수 없습니다. 알고리즘이 어떻게 동작하는지 보여주기 위해 작은 수를 인수분해할 것입니다. 이 데모에서는 Shor의 알고리즘 튜토리얼에 소개된 코드의 단순화된 버전을 사용합니다. 더 자세한 내용은 해당 튜토리얼을 참고하세요.

알고리즘은 양자 문제를 해결하기 위한 표준 프레임워크인 Qiskit 패턴 프레임워크를 사용하여 실행합니다. 이 프레임워크는 네 단계로 구성됩니다:

1. 문제를 양자 Circuit으로 매핑하기
2. 양자 하드웨어에서 실행할 수 있도록 Circuit 최적화하기
3. 양자 컴퓨터에서 Circuit 실행하기
4. 측정값 후처리하기

1. 매핑

$N=15$를 인수분해하고, 서로소 정수로 $a=2$를 선택합니다.

먼저 모듈러 곱셈 유니터리 $M_a$를 구현할 Circuit을 만들어야 합니다. 이 부분이 전체 구현 중 가장 까다로운 부분으로, 구현 방법에 따라 계산 비용이 매우 커질 수 있습니다. 여기서는 약간의 편법을 사용합니다. 시작 상태가 $|1\rangle$임을 알고 있고, 앞선 이해 확인 문제에서

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2|2\rangle &= |4\rangle \\ M_2|4\rangle &= |8\rangle \\ M_2|8\rangle &= |1\rangle \\ \end{aligned}$$

임을 확인했습니다. 그래서 이 네 상태에 대해 올바른 연산을 수행하되, 나머지 상태는 그대로 두는 유니터리를 구성할 것입니다. 이것이 편법인 이유는, $2\bmod 15$의 위수에 대한 사전 지식을 활용하여 유니터리를 단순화하기 때문입니다. 만약 인수를 알 수 없는 수를 실제로 인수분해하려 한다면, 이런 방식을 사용할 수 없습니다.

이해 확인

아래 질문을 읽고 답을 생각한 뒤, 삼각형을 클릭하여 정답을 확인하세요.

위에서 $M_2$ 연산자가 각 상태에 어떻게 작용하는지 알고 있으므로, 두 Qubit의 상태를 교환하는 SWAP Gate들의 연속으로 이 연산자를 구성하세요. (힌트: 각 상태 $|i\rangle$를 이진수로 표현하면 도움이 됩니다.)

정답:

$M_2$의 작용을 이진수로 다시 써 봅시다:

$$\begin{aligned} M_2|0001\rangle &= |0010\rangle \\ M_2|0010\rangle &= |0100\rangle \\ M_2|0100\rangle &= |1000\rangle \\ M_2|1000\rangle &= |0001\rangle \\ \end{aligned}$$

이러한 각 작용은 간단한 SWAP으로 구현할 수 있습니다. $M_2|0001\rangle$은 Qubit $0$과 $1$의 상태를 교환하여 달성됩니다. $M_2|0010\rangle$은 Qubit $1$과 $2$의 상태를 교환하여 달성됩니다. 이런 식으로 계속됩니다. 따라서 $M_2$ 행렬을 다음과 같은 SWAP Gate 연속으로 분해할 수 있습니다:

$$M_2 = SWAP(0,1)SWAP(1,2)SWAP(2,3)$$

연산자는 오른쪽에서 왼쪽으로 작용함을 기억하며, 각 상태에 원하는 효과가 나타나는지 확인해 봅시다:

$$\begin{aligned} M_2|0001\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0001\rangle \\ &= SWAP(0,1)SWAP(1,2)|0001\rangle \\ &= SWAP(0,1)|0001\rangle \\ &=|0010\rangle \checkmark \\ M_2|0010\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0010\rangle \\ &= SWAP(0,1)SWAP(1,2)|0010\rangle \\ &= SWAP(0,1)|0100\rangle \\ &=|0100\rangle \checkmark \\ M_2|0100\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0100\rangle \\ &= SWAP(0,1)SWAP(1,2)|1000\rangle \\ &= SWAP(0,1)|1000\rangle \\ &=|1000\rangle \checkmark \\ M_2|1000\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|1000\rangle \\ &= SWAP(0,1)SWAP(1,2)|0100\rangle \\ &= SWAP(0,1)|0010\rangle \\ &=|0001\rangle \checkmark \\ \end{aligned}$$

이제 이 연산자와 동일한 Qiskit Circuit을 코딩할 수 있습니다.

먼저 필요한 패키지를 임포트합니다:

# Import necessary packages

import numpy as np
from fractions import Fraction
from math import floor, gcd, log

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import QFTGate
from qiskit.transpiler import generate_preset_pass_manager
from qiskit.visualization import plot_histogram

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler

그런 다음 $M_2$ 연산자를 만듭니다:

def M2mod15():
    """
    M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M2 operator
M2 = M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M2, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

QPE 알고리즘은 제어-$U$ Gate를 사용합니다. 따라서 $M_2$ Circuit이 준비되었으니, 이제 제어-$M_2$ Circuit을 만들어야 합니다:

def controlled_M2mod15():
    """
    Controlled M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M2 operator
controlled_M2 = controlled_M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M2, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

이제 제어-$U$ Gate가 완성되었습니다. 그런데 양자 위상 추정 알고리즘을 실행하려면 제어-$U^2$, 제어-$U^4$, …, 제어-$U^{2^{m-1}}$이 필요합니다. 여기서 $m$은 위상 추정에 사용되는 Qubit 수입니다. Qubit 수가 많을수록 위상 추정의 정밀도가 높아집니다. 위상 추정 절차에 $m=8$개의 제어 Qubit을 사용할 것입니다. 따라서 다음이 필요합니다:

$$M_{a^{2^k}}|y\rangle \equiv |a^{2^k} y \bmod N \rangle$$

여기서 인덱스 $k$는 $0 \le k \le m-1 = 7$의 범위를 가지며, 제어 Qubit에 대응합니다. 이제 각 $k$ 값에 대해 $a^{2^k}\bmod N$을 계산해 봅시다:

def a2kmodN(a, k, N):
    """Compute a^{2^k} (mod N) by repeated squaring"""
    for _ in range(k):
        a = int(np.mod(a**2, N))
    return a

k_list = range(8)
b_list = [a2kmodN(2, k, 15) for k in k_list]

print(b_list)

[2, 4, 1, 1, 1, 1, 1, 1]

$k \ge 2$이면 $a^{2^k} \bmod N = 1$이므로, 대응하는 연산자들($M_8$ 이상)은 모두 항등 연산자와 동일합니다. 따라서 행렬 하나($M_4$)만 추가로 구성하면 됩니다.

참고: 이 단순화는 $2 \bmod 15$의 위수가 $4$이기 때문에 가능합니다. $k=2$가 되면(즉, $2^k = 4$), 이후의 모든 거듭제곱 연산자는 항등 연산자가 됩니다. 일반적으로 더 큰 $N$이나 다른 $a$를 선택하면, 높은 거듭제곱의 연산자 구성을 건너뛸 수 없습니다. 이것이 이 예제를 장난감 예제라고 부르는 이유 중 하나입니다. 작은 수를 사용하기 때문에 더 큰 경우에는 통하지 않는 지름길을 사용할 수 있습니다.

def M4mod15():
    """
    M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M4 operator
M4 = M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M4, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

앞서와 마찬가지로, 이를 제어-$M_4$ 연산자로 만듭니다:

def controlled_M4mod15():
    """
    Controlled M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M4 operator
controlled_M4 = controlled_M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M4, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

이제 모든 것을 조합하여 위상 추정을 사용하는 양자 Circuit으로 $2\bmod 15$의 위수를 구할 수 있습니다:

# Order finding problem for N = 15 with a = 2
N = 15
a = 2

# Number of qubits
num_target = floor(log(N - 1, 2)) + 1  # for modular exponentiation operators
num_control = 2 * num_target  # for enough precision of estimation

# List of M_b operators in order
k_list = range(num_control)
b_list = [a2kmodN(2, k, 15) for k in k_list]

# Initialize the circuit
control = QuantumRegister(num_control, name="C")
target = QuantumRegister(num_target, name="T")
output = ClassicalRegister(num_control, name="out")
circuit = QuantumCircuit(control, target, output)

# Initialize the target register to the state |1>
circuit.x(num_control)

# Add the Hadamard gates and controlled versions of the
# multiplication gates
for k, qubit in enumerate(control):
    circuit.h(k)
    b = b_list[k]
    if b == 2:
        circuit.compose(
            M2mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    elif b == 4:
        circuit.compose(
            M4mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    else:
        continue  # M1 is the identity operator

# Apply the inverse QFT to the control register
circuit.compose(QFTGate(num_control).inverse(), qubits=control, inplace=True)

# Measure the control register
circuit.measure(control, output)

circuit.draw("mpl", fold=-1)

2. 최적화

Circuit을 매핑했으니, 다음 단계는 특정 양자 컴퓨터에서 실행할 수 있도록 최적화하는 것입니다. 먼저 Backend를 불러와야 합니다.

service = QiskitRuntimeService()

backend = service.backend("ibm_marrakesh")

계정에 사용 가능한 시간이 없거나 어떤 이유로든 시뮬레이터를 사용하고 싶다면, 아래 셀을 실행하여 위에서 선택한 양자 장치를 모방하는 시뮬레이터를 설정할 수 있습니다.

pm = generate_preset_pass_manager(optimization_level=2, backend=backend)

transpiled_circuit = pm.run(circuit)

print(f"2q-depth: {transpiled_circuit.depth(lambda x: x.operation.num_qubits==2)}")
print(f"2q-size: {transpiled_circuit.size(lambda x: x.operation.num_qubits==2)}")
print(f"Operator counts: {transpiled_circuit.count_ops()}")
transpiled_circuit.draw(output="mpl", fold=-1, style="clifford", idle_wires=False)

2q-depth: 188
2q-size: 281
Operator counts: OrderedDict({'sx': 548, 'rz': 380, 'cz': 281, 'measure': 8, 'x': 6})

3. 실행

# Sampler primitive to obtain the probability distribution
sampler = Sampler(backend)

# Turn on dynamical decoupling with sequence XpXm
sampler.options.dynamical_decoupling.enable = True
sampler.options.dynamical_decoupling.sequence_type = "XpXm"
# Enable gate twirling
sampler.options.twirling.enable_gates = True

pub = transpiled_circuit
job = sampler.run([pub], shots=1024)

result = job.result()[0]
counts = result.data["out"].get_counts()

plot_histogram(counts, figsize=(35, 5))

00000000, 01000000, 10000000, 11000000에서 네 개의 뚜렷한 피크가 보이며, 양자 컴퓨터의 노이즈로 인해 다른 비트열에도 일부 카운트가 있습니다. 이 값들은 무시하고, 임계값을 설정하여 지배적인 네 개의 피크만 남깁니다. 임계값을 초과하는 카운트만 노이즈 위의 진짜 신호로 간주합니다.

# Dictionary of bitstrings and their counts to keep
counts_keep = {}
# Threshold to filter
threshold = np.max(list(counts.values())) / 2

for key, value in counts.items():
    if value > threshold:
        counts_keep[key] = value

print(counts_keep)

4. 후처리

Shor의 알고리즘에서는 상당 부분이 고전적으로 수행됩니다. 따라서 양자 컴퓨터에서 측정값을 얻은 후, 나머지 처리를 "후처리" 단계에 넣겠습니다. 위의 각 측정값은 정수로 변환할 수 있으며, $2^m$으로 나누면 $\frac{k}{r}$에 대한 근사값이 됩니다. 여기서 $k$는 매번 무작위로 선택됩니다.

a = 2
N = 15

FACTOR_FOUND = False
num_attempt = 0

while not FACTOR_FOUND:
    print(f"\nATTEMPT {num_attempt}:")
    # Here, we get the bitstring by iterating over outcomes
    # of a previous hardware run with multiple shots.
    # Instead, we can also perform a single-shot measurement
    # here in the loop.
    bitstring = list(counts_keep.keys())[num_attempt]
    num_attempt += 1
    # Find the phase from measurement
    decimal = int(bitstring, 2)
    phase = decimal / (2**num_control)  # phase = k / r
    print(f"Phase: theta = {phase}")

    # Guess the order from phase
    frac = Fraction(phase).limit_denominator(N)
    r = frac.denominator  # order = r
    print(f"Order of {a} modulo {N} estimated as: r = {r}")

    if phase != 0:
        # Guesses for factors are gcd(a^{r / 2} ± 1, 15)
        if r % 2 == 0:
            x = pow(a, r // 2, N) - 1
            d = gcd(x, N)
            if d > 1:
                FACTOR_FOUND = True
                print(f"*** Non-trivial factor found: {x} ***")

ATTEMPT 0:
Phase: theta = 0.0
Order of 2 modulo 15 estimated as: r = 1

ATTEMPT 1:
Phase: theta = 0.75
Order of 2 modulo 15 estimated as: r = 4
*** Non-trivial factor found: 3 ***

결론

이 모듈을 마치고 나면, 이토록 영리한 알고리즘을 고안해낸 Peter Shor의 뛰어난 통찰력에 새삼 감탄하게 될 것입니다. 하지만 동시에, 이 알고리즘이 겉보기와 달리 얼마나 단순한 원리로 이루어져 있는지도 깨닫게 되기를 바랍니다. 알고리즘이 인상적으로 (혹은 위압적으로) 복잡해 보일 수 있지만, 각 논리 단계를 나누어 천천히 따라가다 보면 여러분도 쇼어 알고리즘을 직접 실행할 수 있게 됩니다.

RSA1024와 같은 수를 인수분해하는 데 이 알고리즘을 실제로 활용하기까지는 아직 갈 길이 멀지만, 양자 컴퓨터는 날마다 발전하고 있습니다. *내결함성(fault tolerance)*이라고 불리는 기준점에 도달하는 순간, 이런 알고리즘들도 곧바로 현실에서 쓰일 수 있게 될 것입니다. 지금이야말로 양자 컴퓨팅을 배우기 가장 흥미로운 시대입니다!

연습 문제

핵심 개념

• 현대 암호 시스템은 큰 정수의 인수분해가 고전 컴퓨터로는 어렵다는 사실에 기반합니다.
• $\mathbb{Z}_N$ 및 $\mathbb{Z}_N^*$ 구조를 포함한 모듈러 산술은 쇼어 알고리즘의 수학적 기반을 제공합니다.
• 정수 $N$의 인수분해 문제는 $N$을 법으로 하는 어떤 수의 위수(order)를 찾는 문제로 환원될 수 있습니다.
• 양자 위수 찾기는 양자 위상 추정 기법을 사용하여 함수 $a^x \mod N$의 주기를 결정합니다.
• 쇼어 알고리즘은 밑수를 선택하고, 양자 위수 찾기를 수행한 뒤, 그 결과로부터 고전적으로 인수를 계산하는 고전-양자 하이브리드 워크플로로 구성됩니다.

참/거짓

1. 참/거짓: 쇼어 알고리즘의 효율성은 RSA 암호화의 보안을 위협한다.
2. 참/거짓: 쇼어 알고리즘은 오늘날의 모든 양자 컴퓨터에서 효율적으로 실행할 수 있다.
3. 참/거짓: 쇼어 알고리즘은 양자 위상 추정(QPE)을 핵심 서브루틴으로 사용한다.
4. 참/거짓: 쇼어 알고리즘의 고전적 부분에는 최대공약수(GCD) 계산이 포함된다.
5. 참/거짓: 쇼어 알고리즘은 짝수의 인수분해에만 적용된다.
6. 참/거짓: 쇼어 알고리즘이 성공적으로 실행되면 항상 올바른 인수가 보장된다.

단답형

1. 쇼어 알고리즘이 RSA 암호화에 잠재적인 미래 위협으로 간주되는 이유는 무엇인가요?
2. 모듈러 지수 함수의 주기, 즉 위수를 찾는 것이 쇼어 알고리즘에서 수의 인수분해에 왜 도움이 되나요?

심화 문제

1. 인수분해하려는 수 $N$이 주어졌을 때, 올바른 위수 $r$ 값을 찾는 데 필요한 QPE의 정밀도를 얻으려면 제어 Qubit이 몇 개($m$) 필요한가요?

2. 여기서 15를 인수분해하기 위해 따랐던 절차를 그대로 적용하여, 이번에는 21을 인수분해해 보세요.