쇼어의 알고리즘

이 Qiskit in Classrooms 모듈을 위해 학생들은 다음 패키지가 설치된 작동 Python 환경을 갖추어야 합니다:

• v2.1.0qiskit 또는 최신 버전
• v0.40.1qiskit-ibm-runtime 또는 최신 버전
• v0.17.0qiskit-aer 또는 최신 버전
• qiskit.visualization
• numpy
• pylatexenc

위 패키지를 설정하고 설치하려면 Qiskit 설치 가이드를 참조하십시오. 실제 양자 컴퓨터에서 작업을 실행하려면 학생들은 '계정 IBM Cloud 설정 가이드'의 단계를 따라 IBM Quantum® 계정을 설정해야 합니다.

이 모듈은 테스트되었으며 QPU 시간을 3초 사용했습니다. 이것은 단지 예상일 뿐입니다. 실제 사용량은 다를 수 있습니다.

# 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'

소개

초기에는 양자 컴퓨터가 기존 컴퓨터로는 해결하기 어려운 문제들을 해결할 1990s 수 있는 잠재력에 대한 기대감이 점점 커지고 있었다. 몇몇 재능 있는 컴퓨터 과학자들이 특정 틈새 시장이나 인위적인 문제에 대해 양자 컴퓨팅의 힘을 입증하는 알고리즘을 고안해냈지만, 양자 컴퓨팅 분야에 확실한 혁명을 가져올 단 하나의 '킬러 애플리케이션'은 아직 발견되지 않았다. 그것은 1994년, 피터 쇼어가 현재 쇼어의 알고리즘이라 불리는 대수 분해 알고리즘을 제안하기 전까지의 이야기였다.

당시에는 큰 수의 소인수를 찾는 것이 고전적인 컴퓨터에게는 극히 어려운 일이라는 것이 잘 알려져 있었다. 사실, 인터넷 보안 프로토콜은 이 어려움을 기반으로 했다. 쇼어는 더 까다로운 단계 일부를 이론적인 미래 양자 컴퓨터로 이전함으로써 이러한 요소들을 기하급수적으로 더 효율적으로 찾는 방법을 발견했다.

이 모듈에서는 쇼어 알고리즘을 살펴보겠습니다. 먼저, 해당 알고리즘에 대한 배경 설명을 좀 더 제공하겠습니다. 이를 통해 알고리즘이 해결하는 문제를 공식화하고 사이버 보안과의 관련성을 설명하겠습니다. 다음으로 모듈러 수학의 기초와 이를 인수분해 문제에 적용하는 방법을 설명하며, 인수분해가 '순서 찾기'라는 다른 문제로 환원되는 과정을 보여드리겠습니다 이전 단원에서 배운 양자 푸리에 변환과 양자 위상 추정법이 어떻게 활용되는지, 그리고 이를 이용해 순서 찾기 문제를 해결하는 방법을 보여드리겠습니다.

마침내, 우리는 실제 양자 컴퓨터에서 쇼어 알고리즘을 실행할 것입니다! 다만, 이 알고리즘은 대규모의 내결함성 양자 컴퓨터가 등장해야 비로소 실질적인 유용성을 발휘할 것이며, 이는 아직 몇 년은 더 걸릴 것이라는 점을 명심해야 합니다. 그러니까, 알고리즘이 어떻게 작동하는지 보여주기 위해 작은 수를 인수분해해 보겠습니다.

팩토링 문제

소인수분해 문제의 목표는 정수 $N$ 의 소인수를 찾는 것이다. 일부 정수 $N$ 의 경우 이는 상당히 쉽다. 예를 들어, $N$ 가 짝수라면, 그 소인수 중 하나는 2일 것이다. $N$ 이 소수의 거듭제곱, 즉 어떤 소수 $N=p^k$ 에 대해 $p$ 라면 $p$ 찾는 것도 상당히 쉽습니다. $N$ 의 $k^{\text{th}}$ 근을 근사하고 $p$ 될 수 있는 근처의 소수를 찾으면 됩니다.

그러나 고전 컴퓨터가 어려움을 겪는 경우는 가 홀수이면서 소수 $N$ 제곱이 아닐 때이다. 이것이 쇼어 알고리즘이 다루는 경우입니다. 이 알고리즘은 두 인수 $p$ 와 $q$ 를 찾아내어 를 $N=pq$ 만족시킵니다. 모든 인수가 소수가 될 때까지 재귀적으로 적용될 수 있습니다. 다음 섹션에서는 이 문제가 어떻게 해결되는지 살펴보겠습니다.

사이버 보안과의 관련성

많은 암호화 체계가 큰 수의 인수분해가 어렵다는 사실에 기반하여 구축되었으며, 오늘날 널리 사용되는 RSA도 그중 하나이다. RSA에서는 두 개의 큰 소수를 곱하여 생성된 공개 키를 사용합니다 $N = p\cdot q$. 이후 누구나 이 공개 키로 데이터를 암호화할 수 있습니다. 그러나 개인 키를 가진 사람만이 해당 데이터를 복호화할 수 있습니다. $p$ $q$

가 쉽게 $N$ 인수분해된다면, 누구나 와 $q$ 가 $p$ 무엇인지 알아내고 암호화를 해독할 수 있을 것이다. 하지만 그렇지 않다. 이것은 유명한 난제입니다. 사실, 1024진수 1024자리이자 10진수 309자리인 숫자 의 소인수 분해는 1991년 당시 10만 달러의 RSA1024 상금이 걸렸음에도 아직까지 발견되지 않았다.

쇼어의 해법

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

모듈러 연산

모듈러 산술은 순환적인 계산 체계로, 일반적인 방식으로 정수 0, 1, 2 등으로 시작하지만, 어느 시점, 일정 기간이 지난 $N$ 후, 카운팅이 다시 시작된다. 예시를 통해 어떻게 작동하는지 살펴보겠습니다. 우리의 주기가 5라고 가정하자. 그러면 우리가 세어 나갈 때, 보통 5에 도달할 지점에서 대신 0부터 다시 시작합니다:

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

이는 " modulo-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인 의 부분집합으로 $\mathbb{Z}_N$, 각 원소는 와 "서로소"이다. 이러한 수들의 집합을 모듈러 곱셈 연산과 함께 $N$ 취하면, 이는 군 (群)이라 불리는 또 다른 수학적 대상을 형성한다. 우리는 이 군을 라고 $\mathbb{Z}_N^*$ 부릅니다. (그리고 $\mathbb{Z}_N^*$ 일반적으로 유한군)에서는 임의의 원소 $a \in \mathbb{Z}_N^*$ 를 선택하고 를 $a$ 스스로에 반복적으로 곱하면 결국 항상 숫자 를 얻게 $1$ 됩니다. 를 얻기 위해 를 $a$ 스스로에 곱해야 하는 $1$ 최소 횟수를 의 순서 라고 합니다. 이 사실은 아래에서 숫자를 $a$ 인수분해하는 방법에 대한 논의에 매우 중요할 것입니다.

이해도 점검

?란 무엇인가 $\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^r\text{mod}(15)=1$ 성립하는 $a$ 가장 작은 수이다.

  $$\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$ 인수분해 문제의 핵심이며 양자 컴퓨터가 필요한 이유입니다. 나머지 노트북 내용을 살펴보면서 그 이유를 알게 될 것입니다.

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

와 $p$ 를 찾는 $q$ 열쇠는 를 만족하는 다른 정수 $x$ 를 찾는 $N=pq$ 데에 달려 있다

$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$, $p$ $N$ 와 $q$ 는 각각 와 $x-1$ 를 나누어야 합니다. 가 의 $x-1$ 인자이고 $q$ $p$ 가 $x+1$ 의 인자이거나, 그 $x+1$ 반대의 경우여야 합니다. 따라서, 와 $x-1$ 와 $N$ 사이의 최대공약수 $x+1$ (GCD)를 계산하면, 그 결과로 $p$ 인자와 를 얻을 수 $q$ 있습니다. 두 수 사이의 최대공약수를 계산하는 것은 유클리드 알고리즘을 사용하는 등, 고전적으로 쉬운 작업입니다.

이해도 점검

위의 논리적 단계들을 하나하나 이해하기 어려울 수 있으니, 예시를 통해 직접 풀어보면서 이해해 보세요. 와 $x=11$ 를 $N=15$ 사용하십시오. 먼저, 와 가 $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$

  이제 우리는 어떤 정수 에 대해 $(x+1)(x-1) = l N$ 임을 $l$ 알고 있습니다. 이는 와 $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$ 된다는 점을 확인했으니, 쇼어 알고리즘을 살펴볼 수 있습니다. 본질적으로 다음을 찾는 것으로 $x$ 귀결됩니다:

1. 임의의 정수를 선택하세요 다음과 같은 임의의 $a$ $1 < a < N$ 정수를 선택하세요:

• 고전적으로 $\text{GCD}(a, N)$ 계산한다.
  • 만약 $\text{GCD}(a, N) > 1$, 이미 인수를 찾은 것입니다. 멈춰.
  • 그렇지 않으면 계속하십시오.

2. 모듈로 $a$ 의 $r$ 순서를 찾으시오. 를 $N$ $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$ 선택하십시오.
• 그렇지 않으면, 공약수를 계산하여 인자를 추출하십시오:

이것들은 의 사소하지 않은 $N$ 인자가 될 것이다.

5. 필요할 경우 재귀적으로 인수분해하십시오

• 와/또는 $q$ 가 $p$ 소수가 아닐 경우, 이를 완전히 인수분해하기 위해 알고리즘을 재귀적으로 적용한다.
• 모든 인자가 소수인 경우, 인수분해가 완료됩니다.

이 절차에 따르면, 이 작업을 완료하기 위해 양자 컴퓨터가 필요한 이유가 분명하지 않을 수 있습니다. 그것은 단계 2, 즉 모듈로 $a$ 의 순서를 찾는 것이 전통적으로 매우 $N$ 어려운 문제이기 때문에 필요합니다. 복잡도는 수에 따라 지수적으로 $N$ 증가한다. 그러나 양자 컴퓨터를 사용하면 양자 위상 추정법을 활용하여 이를 해결할 수 있다. 4단계, 두 정수의 최대공약수를 찾는 것은 사실 고전적인 방법으로 꽤 쉽게 할 수 있는 일이다. 따라서 양자 컴퓨터의 성능이 실제로 필요한 단계는 순서 찾기 단계뿐입니다. 팩토링 문제가 순서 찾기 문제로 "환원된다"고 말한다.

어려운 부분: 주문 찾기

이제 양자 컴퓨터를 활용하여 탐색하는 방법을 살펴보겠습니다. 먼저, "순서"라는 용어가 무엇을 의미하는지 명확히 해 봅시다 물론, 이 순서가 수학적으로 무엇을 의미하는지는 이미 말씀드렸습니다: 이는 를 만족하는 첫 번째 $r$ 0이 $a^r = 1 \pmod N.$ 아닌 정수입니다. 하지만 이 개념에 대해 조금 더 직관적으로 이해할 수 있는지 살펴보겠습니다.

충분히 작은 $N$ 에 대해서는, 각 의 거듭제곱을 계산하고 그 수의 의 $N$ 모듈러스를 취한 후, 를 $a$ $a^r = 1 \text{mod}(N)$ 만족하는 $r$ 거듭제곱 을 찾을 때 중단함으로써 순서를 결정할 수 있다. 위의 예시 에서 우리가 $N=15$ 한 작업이 바로 그것이다. 다음과 같은 모듈러 거듭제곱의 그래프를 몇 $N$ 가지 예시 값에 대해 $a$ 살펴보겠습니다:

뭔가 눈치채셨나요? 이것들은 주기 함수입니다! 그리고 순서는 주기와 $r$ 동일합니다! 따라서, 순서 찾기는 주기 찾기와 동일하다.

양자 컴퓨터는 함수의 주기를 찾는 데 매우 적합합니다. 이를 위해 양자 위상 추정(Quantum Phase Estimation)이라는 알고리즘 서브루틴을 사용할 수 있습니다. 이전 모듈에서 우리는 양자 푸리에 변환(QPT)과 양자 푸리에 변환(QPT)의 관계를 논의했습니다. 자세한 복습을 원하시면 QFT 모듈 또는 존 왓러스의 양자 알고리즘 강좌 중 '양자 위상 추정' 강의를 참고하세요. 이제 절차의 요점을 살펴보겠습니다:

양자 위상 추정(QPE)에서는 먼저 유니터리 연산자 $U$ 와 그 유니터리 연산자의 고유상태 $|\psi\rangle$ 를 갖습니다. 그런 다음 QPE를 사용하여 대응하는 고유값을 근사합니다. 연산자가 유니터리이므로 이 고유값은 의 형태를 가집니다. 따라서 고유값을 찾는 것은 주기 $e^{2\pi i \theta}$ 함수에서 $\theta$ 의 값을 찾는 것과 동일합니다. 회로는 다음과 같습니다:

여기서 제어 큐비트 수(위 그림의 상단 $m$ 큐비트)가 근사값의 정밀도를 결정한다.

쇼어 알고리즘에서 우리는 단위 연산자에 대해 QPE를 $M_a$ 사용합니다:

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

여기서 $|y\rangle$ 는 다중 큐비트 레지스터의 계산 기저 상태를 나타내며, 여기서 큐비트의 이진값은 정수 에 $y$ 대응한다. 예를 들어, 이고 $N=15$ $y = 2$ 라면 $|0010\rangle$, $|y\rangle$ 는 4큐비트 기저 상태 로 표현된다. 이는 15까지의 숫자를 인코딩하는 데 4개의 큐비트가 필요하기 때문이다. (이 개념이 생소하다면, 양자 상태의 이진 인코딩에 대한 복습을 위해 교실용 Qiskit 입문 모듈 을 참조하십시오.)

이제 우리는 이 단위 행렬의 고유상태를 찾아야 합니다. 만약 우리가 상태 에서 $|1\rangle$ 시작했다면, 의 연속적인 적용은 $U$ 레지스터의 상태를 로 곱하게 하며, 번 적용 $r$ 후에는 다시 $a \pmod N$ $|1\rangle$ 상태 에 도달하게 됨을 알 수 있다. 예를 들어 와 $a = 3$ $N = 35$ :

따라서 이 주기( $|\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}$$

우리가 큐비트 상태를 이러한 고유상태 중 하나로 초기화할 수 있다고 가정해 보자 (스포일러 — 우리는 할 수 없다). 아니면, 적어도 쉽게는 아니었다. 그 이유와 대신 할 수 있는 방법을 곧 설명드리겠습니다). 그러면 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$ 충분히 정확해야 합니다. 제어 큐비트 $m$ 가 많을수록 추정값의 정확도는 높아집니다. 수업 마지막 문제에서는, 어떤 수를 인수분해하는 데 필요한 $m$ 최소한의 $N$ 값을 구하도록 요청받을 것입니다.

이제 우리는 문제를 해결해야 합니다. 위의 모든 설명은 고유상태 를 찾는 방법에 관한 것이며, 이는 $r$ $|\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$ 상태(즉, $|000...01\rangle$ )로 준비할 수 있다. 비록 이 상태 자체가 의 고유상태는 $M_a$ 아니지만, 모든 고유상태에 대한 중첩 $|\psi_k\rangle$ 상태이다:

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

이해도 점검

이전 체크인 문제에서 $a=2$ 와 에 $N=15$ 대해 찾은 고유상태들의 중첩과 동등함을 $|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$ 큐비트를 측정하면 임의로 선택된 고유값 중 하나인 의 $k/r$ 근사값을 $k \in \{0,1,2,...,r-1\}$ 얻을 수 있다. 이 회로를 몇 번 반복하고 서로 다른 값을 가진 $k$ 샘플을 몇 개 얻으면, 우리는 빠르게 를 $r$ 추론할 수 있을 것이다.

Qiskit에서 구현

앞서 언급했듯이, 우리의 하드웨어는 아직. 같은 거대한 숫자를 인수분해할 수 RSA1024 있는 수준에 이르지 못했습니다. 작은 수를 인수분해하여 알고리즘이 어떻게 작동하는지 보여드리겠습니다. 이 데모에서는 쇼어 알고리즘 튜토리얼에서 제시된 코드의 단순화된 버전을 사용할 것입니다. 더 자세한 내용을 원하시면 튜토리얼을 방문해 주세요.

우리는 양자 문제 해결을 위한 표준 프레임워크인 Qiskit 패턴 프레임워크를 사용하여 알고리즘을 실행할 것입니다. 다음과 같은 네 단계로 구성됩니다:

1. 문제를 양자 회로에 매핑하기
2. 양자 하드웨어에서 실행될 회로를 최적화하십시오
3. 양자 컴퓨터에서 회로를 실행하십시오
4. 측정값을 후처리하다

1. 지도

를 인수분해하자 $N=15$. 여기서 를 서로소 정수로 $a=2$ 선택한다.

먼저, 모듈러 곱셈 유니터리를 구현할 회로를 구성해야 합니다. $M_a$ 이는 전체 구현 과정에서 가장 까다로운 부분이며, 구현 방식에 따라 계산 비용이 매우 높을 수 있습니다. 이를 위해 우리는 약간 속임수를 쓸 것입니다: 우리는 상태 에서 시작한다는 $|1\rangle$ 것을 알고 있으며, 이전 체크인 질문에서

따라서, 우리는 이 네 가지 상태에 대해 올바른 연산을 수행하지만 다른 모든 상태는 그대로 두는 단위 연산을 구성할 것입니다. 이것은 우리가 단위 행렬을 단순화하기 위해 $2\bmod 15$ 의 순서에 대한 지식을 사용하고 있기 때문에 부정행위입니다. 만약 우리가 실제로 인수가 알려지지 않은 수를 인수분해하려고 한다면, 우리는 이를 수행할 수 없을 것이다.

이해도 점검

위 상태들을 $M_2$ 연산자가 어떻게 변환하는지 알고 있으므로, 두 큐비트의 상태를 교환하는 일련의 SWAP 게이트로 해당 연산자를 구성하십시오. (힌트: 각 상태를 $|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$ 는 큐비트 $0$ 와 의 상태를 교환함으로써 $1$ 달성됩니다. $M_2|0010\rangle$ 는 큐비트 $1$ 와 의 상태를 교환함으로써 $2$ 달성됩니다. 이와 같은 방식으로 진행됩니다. 따라서, 우리는 $M_2$ 행렬을 다음과 같은 일련의 SWAP 게이트로 분해할 수 있습니다:

  $$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에서 이 연산자와 동등한 회로를 코딩할 수 있습니다.

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

# 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)

Output:

QPE 알고리즘은 제어된 $U$ 게이트를 사용합니다. 이제 회로를 $M_2$ 확보했으니, 이를 제어 가능한 $M_2$ 회로로 만들어야 합니다:

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)

Output:

이제 제어 $U$ 게이트를 갖게 되었습니다. 그러나 양자 위상 추정 알고리즘을 실행하려면 제어된- $U^2$, 제어된- $U^4$, 최대 제어된-이 $U^{2^{m-1}}$ 필요하며, 여기서 $m$ 는 위상 추정에 사용되는 큐비트 수입니다. 큐비트가 많을수록 위상 추정 정확도가 높아진다. 위상 추정 절차에 제어 큐비트를 $m=8$ 사용할 것입니다. 그러니까, 우리는 다음이 필요합니다:

여기서 지수 $k$ 는 제어 $0 \le k \le m-1 = 7$ 큐비트에 대응한다. 이제 각 값에 대해 를 $a^{2^k}\bmod N$ $k$ 계산해 보자:

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)

Output:

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

에 $a^{2^k} \bmod N = 1$ 대해 $k \ge 2$, 모든 대응하는 연산자( $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)

Output:

그리고 이전과 마찬가지로, 우리는 이를 제어된$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)

Output:

이제 위상 추정법을 사용하여 양자 회로로 의 $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)

Output:

2. 최적화

회로도를 작성했으니, 다음 단계는 특정 양자 컴퓨터에서 실행되도록 회로를 최적화하는 것입니다. 먼저 백엔드를 로드해야 합니다.

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)

Output:

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))

Output:

양자 컴퓨터의 노이즈로 인해 다른 비트열에서도 일부 카운트가 발생하지만, 01000000 10000000,, 11000000``00000000, 에 네 개의 뚜렷한 피크가 관찰됩니다. 우리는 임계값을 설정하여 이들을 무시하고 우세한 네 개만 유지할 것입니다: 이 임계값을 초과하는 카운트만 잡음 위의 진정한 신호로 간주됩니다.

# 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. 후처리

쇼어 알고리즘의 경우, 알고리즘의 상당 부분이 고전적으로 수행됩니다. 따라서, 양자 컴퓨터로부터 측정값을 얻은 후 나머지 작업은 "후처리" 단계에서 수행할 것입니다. 위의 각 측정값은 정수로 변환될 수 있으며, 이를 로 나눈 값이 $2^m$ 우리의 근사값이 됩니다. 여기서 $k$ 는 $\frac{k}{r}$ 매번 무작위로 결정됩니다.

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} ***")

Output:

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 ***

결론

이 모듈을 학습한 후, 여러분은 피터 쇼어가 이토록 기발한 알고리즘을 고안해낸 천재성에 대해 새롭게 감탄하게 될지도 모릅니다. 하지만 그 속임수 같은 단순함에 대한 새로운 차원의 이해에 도달하셨기를 바랍니다. 비록 이 알고리즘이 인상적(혹은 위협적)일 정도로 복잡해 보일지라도, 논리의 각 단계를 쪼개서 천천히 따라가면 여러분도 쇼어 알고리즘을 실행할 수 있을 것입니다.

비록 우리가 아직 이 알고리즘으로 와 RSA1024 같은 숫자를 인수분해하는 데는 한참 멀었지만, 양자 컴퓨터는 매일 발전하고 있으며, 오류 내성이라는 임계점에 도달하는 순간, 이러한 알고리즘들도 곧 뒤따를 것입니다. 양자 컴퓨팅을 배우기에 정말 흥미진진한 시기입니다!

문제점

핵심 개념:

• 현대 암호 시스템은 큰 정수를 인수분해하는 고전적인 난이도에 의존한다.
• 모듈러 산술 — 구조 $\mathbb{Z}_N$ 와 를 포함하여 $\mathbb{Z}_N^*$ — 는 쇼어 알고리즘의 수학적 기초를 제공한다.
• 정수의 인수분해 문제는 모듈로 에서의 $N$ 순서를 찾는 $N$ 문제로 환원될 수 있다.
• 양자 순서 찾기는 양자 위상 추정 기법을 사용하여 함수 의 주기를 $a^x \mod N$ 결정한다.
• 쇼어 알고리즘은 기저를 선택하고 양자 순서 찾기를 수행한 후 결과로부터 인자를 고전적으로 계산하는 고전-양자 하이브리드 워크플로로 구성된다.

참/거짓:

1. T/F 쇼어 알고리즘의 효율성은 RSA 암호화의 안전성을 위협한다.
2. T/F 쇼어 알고리즘은 현대 양자 컴퓨터에서 효율적으로 실행될 수 있다.
3. T/F 쇼어 알고리즘은 양자 위상 추정(QPE)을 핵심 서브루틴으로 사용한다.
4. T/F 쇼어 알고리즘의 고전적인 부분은 최대공약수(GCD)를 계산하는 것을 포함한다.
5. T/F 쇼어의 알고리즘은 짝수만 인수분해할 수 있다.
6. T/F 쇼어 알고리즘의 성공적인 실행은 항상 올바른 인수들을 보장한다.

간단한 답변:

1. 쇼어 알고리즘이 왜 RSA 암호화에 대한 잠재적 미래 위협으로 간주되는가?
2. 모듈러 지수 함수의 주기(또는 순서)를 찾는 것이 쇼어 알고리즘에서 수를 인수분해하는 데 왜 도움이 되는가?

도전 문제:

1. 주어진 수를 $N$ 인수분해하여 순서의 올바른 값을 찾기 위해 QPE에서 필요한 $r$ 정밀도를 얻으려면 몇 개의 제어 큐비트가 $m$ 필요한가?

2. 여기서 설명한 절차에 따라 15를 인수분해한 후, 이제 21을 인수분해해 보세요.