"양자비트와 양자암호" 요약 - 8장. 쇼어의 혁명

시카고 전체의 전화번호가 적힌 책에서 Harold Carter 란 사람의 전화번호를 찾는다고 하자. 전화번호부가 알파벳 순서이므로 "C" 부분에서 시작해서, "Ca", "Car" 을 지나 "Carter" 에 이르는 과정은 2 또는 3초보다 훨씬 긴 시간일 것이다. 그렇다면 312-2453-749의 번호에 해당하는 사람의 이름을 검색해 달라는 요청을 받았다고 해보자. 이는 직관적으로 몇 년 아니면 적어도 몇 시간이 걸릴 것이다. 그러므로 "평균적으로 얼마나 시간이 걸릴까?"라는 질문이 타당하다. 전화번호 면의 수가 N이면 평균적으로 N/2면을 찾게 될 것이라고 말할 수 있다.

고전적으로 두 단계에 걸치는 문제를 도이치 알고리즘(Deutsch Algorithm)에서는 한 단계에 해결할 수 있다. 양자 컴퓨터는 가능한 모든 입력값을 병렬로 처리할 수 있지만 이러한 값은 컴퓨터 내에 얽힘 상태로 잠겨 있기 때문에 직접 접근할 수가 없다. 따라서 양자 병렬성(Quantum parallelism)을 사용하려면 몇 가지 요령이 필요하다.

8.1 그로버의 데이터베이스 검색

다음의 이름과 숫자들이 쌍을 이루고 있는 목록을 가정하자.

0 X

1 R

2 P

3 A

목록에 있다면 결과는 1, 없다면 0이 되는 간단한 검색 프로그램 f(x)를 가정하자. 예를 들어, f(P) = 1 이고, f(2) = 1 이며, 목록에 없는 경우는 0이 된다.

여기에 양자 검색 알고리즘을 적용하자. 우선 목록의 모든 대상들이 중첩 상태에서 시작된다. 목록이 N 개라면 2의 n 제곱인 2ⁿ 으로 N 을 표현한다. 목록의 수가 2의 제곱으로 표현하기 어려운 경우, 2ⁿ 의 값 중에서 N 보다 크고 가장 가까운 2ⁿ 을 선택한다.

다음은 n 개의 큐비트로 동시에 암호화하는 작업이다. 예를 들어, 두 개의 큐비트를 가지고 있다면 4가지 가능한 조합은 다음과 같다.

|00>, |01>, |10>, |11>

위 값들은 0 에서 3 까지의 숫자를 이진수로 나타낸 것이다. 이제 두 개의 큐비트들을 모두 중첩 상태 (|0> + |1>) / √2로 놓는다. 두 개의 큐비트가 합성된 상태는 다음과 같이 쓸 수 있다.

((|0> + |1>) / √2 ) * ((|0> + |1>) / √2 )

두 괄호를 풀어 쓰면 다음과 같다.

(1/2)*|00> + (1/2)*|01> + (1/2)*|10> + (1/2)*|11>

다행히 4 개의 상태 중 하나를 측정할 확률을 모두 다 더하면 1을 만족하므로 규격화 조건에도 부합된다. 각 상태의 앞 계수는 1/2 이고, 확률은 계수의 제곱이므로 1/4가 된다. 이 상태가 4개이므로 전체 확률은 4 * (1/4) = 1 이 된다.

이제 f(x) 를 적용할 "오라클"[1]에 위 중첩 상태를 입력한다. f(x) 가 0이면, 오라클은 중첩 상태가 변하지 않도록 유지시키며, f(x) 가 1 이면 위상을 변하게 만든다. 예를 들어, 찾는 항목이 숫자 2 라면, 이진수로 10 이고, 중첩 상태 |10> 은 위상이 반대가 되어 - |10> 이 된다.

중첩 상태에서 찾는 항목이 표시나게 달라보여도 바로 선택할 수는 없다. 해당 항목의 계수가 변하지 않으므로 중첩 상태를 측정한다면 확률은 1/N 이 될 것이다. 그러므로 아무 것도 얻어내지 못한다. 따라서 찾는 대상의 부호가 바뀌었다는 것을 이용하기 위해 '평균 값에 대한 역전환'을 수행한다. 모든 계산은 가역적이어야 하는 것을 기억하자.

먼저 평균 값 m 을 계산한다. 4개 상태의 평균 값은 ((1/2) + (1/2) - (1/2) + (1/2)) / 4 이므로 1/4 이 된다. 이제 각 계수가 평균 값 m 보다 크거나 작은 차이를 계산한다. 그 다음 평균 값 보다 큰 값을 평균 값에서 빼준다. 각 계수 값이 L 이라면, 평균에 대한 역전환 후 계수 L* 는 다음의 공식을 만족한다.

L* = m - (L - m) = 2m - L

평균 값에 대한 역전환 이후 다른 상태들은 계수가 0이 되고, 찾는 상태의 계수는 1이 된다. 다시 말하면 큐비트의 마지막 상태를 측정한다면 항상 올바른 결과인 "10"을 100%로 측정하게 된다.

그림8.1. 그로버의 검색 알고리즘

8.2. 얼마나 빨리 검색할 수 있는가?

4 개의 목록을 검색할 때 최대 4번에 걸쳐 체크하지 않고 한 번에 대상을 발견할 수 있다면, 더 긴 목록은 얼마나 빨라질 수 있을까? 16개의 항목이 있을 때는 4개의 큐비트가 필요하고, 처음의 중첩 상태를 얻기 위해 |0> 상태에 하마다드 게이트를 적용한다. 그리고 세 번째 항목 |0010> 이 검색 대상인 경우에 오라클을 적용하면 이 상태는 아래와 같다.

(1/4) * (|0000> + |0001> - |0010> + ... + |1111>)

검색하고자 하는 상태는 그 앞에 음의 부호가 붙고, 각 계수는 1/4 이므로 전체 확률이 1인 규격화 조건을 만족한다.

위 상태들 중에 한개만 음의 부호를 가지므로 모든 계수의 평균 값은 (15 * 1/4 + 1 * 1/4) / 16 = 7 / 32 이다. 평균에 대한 역전환을 하면 "틀린" 상태의 진폭은 3 / 16 이고, "찾는" 상태의 진폭은 11/16 이라는 결과나 나온다. 틀린 상태가 측정될 확률은 (3/16)² 으로 약 3.5%이며, "찾는" 상태의 확률은 약 47%이다.

아직 100% 가 아니므로, 오라클과 평균 값에 대한 역전환 과정을 반복하여 검색 상태의 확률을 증가시킨다. 두 번째 알고리즘을 시행하면 찾는 상태의 계수가 61/64 이고, 약 91%의 확률이 된다.

양자 병렬성이 검색하고자 하는 것을 빠르게 찾도록 해준다고 하더라도 그로버의 검색 알고리즘(Grover's search algorithm)의 반복 횟수는 목록의 항목수 √N 에 비례하여 증가한다[2]. 검색 목록의 개수가 12개 정도에서는 √N 과 고전적인 평균 검색 횟수인 N/2 의 차이가 크지 않지만 목록의 수가 백만이나 천만 정도인 경우 이 차이는 크다. 예를 들어 십만 개의 목록에서 1초에 한 개씩 검토한다고 하면 고전적인 검색의 경우 11일이 소요되며, 양자 알고리즘은 15분 정도가 소요된다. 이는 검색 시간을 1/1000 정도로 줄이는 효과를 갖는다.

8.3. 쇼어의 소인수분해 알고리즘

8.3.1. 기존의 느린 계산법

7장에서, 양자 컴퓨터가 15 = 3 x 5 를 계산했다는 신문의 표제를 다루었다. 15의 소수를 찾는 문제는 대단히 어렵지는 얺다. 한 개의 소수를 시험해 보고 그 다음 또 다른 수를 시험하고.. 를 반복하며, 이를 시행착오 방법이라고 한다. 이 방법은 큰 수를 만날수록 어려워진다. 두 자리 소수 17 과 23을 곱하는 데 드는 시간은 몇 초에 불과하지만, 두 수의 곱인 391이나, 13을 소인수로 갖는 5083 같은 수를 소인수분해 하는 것은 훨씬 많은 시간이 든다. 자릿수를 4개에서 8개로 늘리면 계산 과정의 수는 대략 70번에서 5000번으로 늘어나며, 5000번의 계산을 4시간이라고 가정할 때 16자리수로 늘어나는 경우의 계산 시간은 약 2년이 된다. 현대의 컴퓨터는 1초 동안 1조 번의 계산을 수행할 수 있는 테라플롭[3] 능력을 가지고 있는 데, 130자릿수를 갖는 어떤 수의 소인수분해는 약 42일이 소요된다. 42일에 130자릿수를 소인수분해 하는 능력을 가지는 컴퓨터로 이 숫자보다 2배가 되는 자릿수를 소인수분해할 경우 대략 100만년 정도의 시간이 걸리고, 자릿수가 몇 개 더 늘어나면 계산시간은 우주의 나이보다 더 길어질 수도 있다.

현재까지는 소인수분해 문제를 해결하기 위해 시행착오 방법을 사용했지만 중첩과 양자병렬성을 이용한 양자컴퓨터로 어떤 수를 소인수분해하면 대단히 빠를 것이라고 예상할 수 있다. 도이치와 그로버 알고리즘에서 중첩상태는 가능한 값의 특정 함수를 병렬로 계산할 수 있게 해준다. 그 다음 양자컴퓨터로부터 출력을 얻는 확실한 방법을 발견해야한다.

8.3.1. 빠른 계산을 위한 멋진 책략

어떤 수의 소수를 발견하는 방법은 어떤 함수의 푸리에 변환(Fourier transform)[4] 식을 발견하는 것과 같다. 푸리에변환은 함수가 어떤 주기성을 갖는지 알려준다. 예를 들어, 다음과 같은 수열이 있을 때,

1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, ...

4 다음에 오는 수가 1 이라는 것을 알 수 있는 데 이 수열은 주기가 4이기 때문이다. 소수 7의 지수로부터 유도되는 수열은 아래와 같다.

7¹ = 7, 7² = 49, 7³ = 343, 7⁴ = 2401, 7⁵ = 16807, 7⁶ = 117649, 7⁷ = 823453, ...

위 수들에 모듈러15 를 적용해보자. 7 mod 15, 7² mod 15, 7³ mod 15 .. 를 나열하면,

7, 4, 13, 1, 7, 4, 13, ...

이 되고, 7, 4, 13, 1 이 반복되는 것을 알 수 있다. 이 수열은 원소가 4개 이므로, 주기는 4가 된다. 즉, 수 a 의 n 제곱 행태의 n 에 따라 커지는 수열을 어떤 수 N 으로 모듈러 연산을 하면 그 수열 aⁿ mod N 은 주기적이다. 어떤 조건에서 수 N 의 소인수는 바로 수열의 주기로부터 구할 수 있다. N 의 소인수 a는 N보다 작아야 하며 N 과 공통 인수를 가져서는 안된다. aⁿ mod N 의 주기를 q 로 놓고 짝수라고 한다면 N 의 소인수는 a^q/2 + 1 과 a^q/2 - 1 이며, 이 수들과 N 의 최대공약수가 N 의 소수가 된다.

위 예제에 이 방법을 적용하여 N = 15, a = 7로 택하면 수열의 주기 4를 얻게 되며, 이 값을 다음의 방정식에 입력하면, a^q/2 + 1 과 a^q/2 - 1 는 50과 48이고, 최대공약수(50, 15)와 최대공약수(48, 15)는 N 의 소수가 된다. 유클리드의 최대공약수 알고리즘[5]을 적용하면, 50 / 5 = 10, 15 / 5 = 3, 48 / 3 = 16, 15 / 3 = 5 이므로 각 최대 공약수는 5와 3이라는 것을 알 수 있다. 결과적으로, 15 의 소수는 5와 3이 된다.

1994년 벨 연구소의 피터 쇼어(Peter Shor)는 양자역학을 이용한 알고리즘에 이를 활용할 수 있다는 것을 알게되었다. 소인수분해를 aⁿ mod N 의 주기를 찾는 방법으로 수행하면 큐비트나 양자 중첩을 사용하여 계산 단계를 고전적인 경우보다 훨씬 줄일 수 있다.

쇼어의 알고리즘 첫 단계에서 0 과 c 사이의 모든 수의 중첩을 큐비트로 등록한다. c 는 2의 지수로서 N 보다 큰 수이다. 두 번째로 입력되는 상태들은 |0>의 큐비트 들이고, 다음으로 N보다 작은 소수 a를 선택한다.

이제 aⁿ mod N 의 모든 값을 계산할 필요가 있는 데, n 은 분리하지 않고 모든 n 값이 포함되도록 입력 레지스터에 중첩상태를 입력하고 오라클로 병렬 처리시킨다. 수식으로 쓰면 중첩 상태에 있는 첫 번째 레지스터는 아래와 같고,

|00...000> + |00...001> + |00...010> + |00...011> + ... + |11...110> + |11...111>

두 번째 레지스터는 |00...000> 이다. 표기를 간략하게 하기 위해 십진수를 사용하여 처음 두 개의 레지스터의 상태는 아래와 같다.

|0>|0> + |1>|0> + |2>|0> + |3>|0> + ... + |c-1>|0> + |c>|0>

오라클은 첫 레지스터로부터 n 값을 취하여 aⁿ mod N 을 계산한 다음 두 번째 레지스터에 결과를 쓴다. 예를 들어 a = 7, N = 15 라면 상태는 |2>|0> 에서 |2>|4> 로 출력된다. 왜냐하면 7² mod 15 = 49 mod 15 = 4 이기 때문이다. 중첩 상태의 모든 상태를 계산하면,

|0>|1> + |1>|7> + |2>|4> + |3>|13> + |4>|1> + |5>|7> + ...

이다. 두 번째 레지스터의 큐비트들은 오라클의 함수 전체 값들이 포함되어 있는 반면 처음 레지스터는 0부터 c까지의 값만을 저장한다. 상기 식의 |1>|7> 과 |5>|7> 을 관찰하면, 두 번째 레지스터에 대응되는 첫 번째 레지스터의 값은 하나가 아닌 여러 개인 것을 볼 수 있다. aⁿ mod N 함수는 주기적이며, 이러한 주기성은 n 의 여러 값들에 대해 같은 함수 값으로 대응된다. 예를 들어 n = 1 로부터 얻은 주기가 q 인 함수들인 x = 1 + q, x = 1 + 2q, x = 1 + 3q 등은 정확히 같은 같은 값을 나태내고, 같은 함수 값을 갖는 두 개의 연속적인 값 사이의 '간격'을 안다면 q 가 얻어지고 알고리즘을 통해 N 의 소수를 발견할 수 있다.

주기 q 를 구하기 위해서 두 번째 레지스터의 특정 값에 대응하는 첫 번째 레지스터의 모든 x 값을 골라내야만 한다. 두 번째 레지스터를 측정하면 마구잡이 결과를 가져오는데 측정 후 두 번째 레지스터는 다음 상태들 중의 하나가 될 것이며, 그 확률은 모두 같다.

|1>, |7>, |4>, |13>, ...

두 번째 레지스터에 대한 측정이 상태 |7> 이었다고 가정하자. 그러면 첫 레지스터는 |7> 을 갖는 모든 상태의 중첩이 되어야 하므로 그 결과는 아래와 같다.

|1>|7> + |5>|7> + |9>|7> + |13>|7> + |21>|7> + ...

첫 번째와 두 번째 레지스터들은 더 이상 얽힘 상태가 아니지만 첫 번째 레지스터는 아직 중첩 상태이다. 위 수열은 주기 q 가 4 이지만, 첫 번째 레지스터를 측정하지 않는다면 1, 5, 9, 13, 17 등은 모두 같은 확률이 되어 어떤 정보도 얻어낼 수가 없다.

8.3.3. 주기값 구하기

주기 값을 구하기 위해 앞서 언급한 푸리에변환에 전체의 중첩 상태를 입력한다. 이때의 알고리즘은 물론 양자 논리여야 한다.

그림8.2. 쇼어의 소인수분해 알고리즘

주기적인 수열은 계속 중첩 상태이므로 하나의 레지스터만으로는 측정할 수가 없다. 따라서 오라클 연산 이후에도 두 개의 레지스터가 얽힘상태에 있다면 서로 다른 상태가 된다. 이 후 두번째 레지스터를 측정해도 처음 상태는 중첩 상태로 남아 있을 수 있다.

aⁿ mod N 의 모든 값은 병렬로 처리되지만 오라클에서는 푸리에변환 후에도 양자병렬성이 작동되므로 주기를 구해내어 계산에 이용할 수 없으며, 만일 주기가 홀수로 나오게 되면 다시 한번 적용한다.

쇼어의 알고리즘에서 N의 소인수를 발견하는 데 필요한 연산의 횟수는 N 의 자릿수에 따라 다항식적으로 증가한다. 반면 고전적 알고리즘은 지수함수적으로 증가한다.

8.3.4. RSA 암호
양자 컴퓨터가 현재의 비밀 암호를 얼마나 무용지물로 만들 수 있는지 알아보자. 비밀은 소인수분해에 있다. 예를 들어 RSA 키를 이용하여 그 비밀을 해독하려고 할 것이다.

RSA는 론 리베스트(ron Rivest), 아디 사미르(Adi Shamir)와 레너드 아들레만(Leonard Adleman) 등에 의해 처음으로 고안된 비대칭 키이며, 수학 연산이 한 방향으로는 쉽고 반대 방향인 경우 매우 어렵게 되는 원리를 이용한다. Alice 로부터 메시지를 받기 원하는 Bob 은 두 개의 큰 소수를 취하여 그들의 곱을 계산하여 Alice 에게 보낸다. Alice 는 그것을 사용하여 메시지를 암호화한다. 암호화된 메시지를 받은 Bob 은 소수에 대한 정보를 사용하여 다시 해독한다. 만일 Eve 가 암호화된 메시지를 가로채면 소수의 곱을 얻게 되지만 그 곱을 소인수분해하지 않는 한 Eve 는 메시지를 해독할 수 없다. Eve 가 가진 그 곱이 너무 큰 수이면 수인수분해하는 것은 영원한 시간이 걸릴지도 모르기 때문이다. 그러나 Eve 가 양자 컴퓨터를 가지고 있다면 빠른 속도로 소인수분해해서 메시지를 해독할 수 있게 된다. 수식을 포함하여 다시 알아보자.

1. Bob 은 2 개의 소수 p 와 q 로 N = p * q 를 생성하고, P = (p - 1) * (q - 1) 계산한다. 이 후 P 와 공약수를 갖지 않는 c 를 선택하고, 아래 식을 만족하는 d 를 계산한다.

cd = 1 mod(p - 1)(q - 1)

상기 식에서 d 는 c 를 곱하고 P 에 의해 나누면 나머지가 1이 된다. Bob 은 곱과 연결되는 3개의 소수를 가지며, 이 소수에 대한 정보가 없는 한, 즉 N 을 소인수화하지 않는 한 도청자들에게는 완전히 쓸모 없는 수들이다.

2. Bob 은 수 N 과 c 를 Alice 에게 공개된 채널로 보낸다. 이러한 두 수들을 공개키(public key)라고 하며, Alice 는 공개키를 이용하여 메시지를 암호화한다. 메시지 m 은 N 보다 작은 수이며, 암호화된 메시지 e 는 다음과 같다.

e = m^c mod N

Alice 는 암호화된 메시지 e 를 다시 공개된 채널로 Bob 에게 보낸다.

3. Alice 의 메시지를 해독하기 위해 밥은 다음의 연산을 수행한다.

m = e^d mod N

작은 수를 예를 들어 사용해보자. p 와 q 로 소수 3과 7을 택하면 그들의 곱 N 은 21이고,  P = (3 - 1) * (7 - 1) = 12 이다. 이제 c 는 5 를 택한다면 5는 12와 공통 인수를 가지지 않는다. 그리고 P = 12 에 의해 5 * d 를 나누어서 나머지가 1이 되는 d 를 시행착오 방법을 통하면 d = 5 가된다. 이제 Alice 의 메시지 m 을 암호화하자. 예를 들어, 메시지가 4 인 경우, Bob 에게 보내는 암호화된 메시지는 다음과 같다.

e = m^c mod N = 4⁵ mod 21 = 1024 mod 21 = 16

16를 받은 Bob 이 원래 메시지를 다음과 같이 복원한다.

m = e^d mod N = 16⁵ mod 21 = 1048576 mod 21 = 4

도청자가 영리하다면 곱 N = 21 을 알기만 하면 메시지를 해독하는데 필요한 d 의 값을 계산해낼 것이다. 만일 도청자가 양자 컴퓨터를 가지고 있다면 수백 자릿수를 갖는 수 N 의 소인수를 구하는 일도 그리 오래 걸리지 않을 것이므로, RSA 코드를 깨기 쉽다.

상기 사항들은 아직은 단순히 이론일 뿐이다. 위와 같이 암호를 깨거나 거대한 데이터베이스를 빠르게 검색하는 일은 반드시 가까운 미래에 이루어질 것이다. 어쩌면 이미 일어나고 있는 일인지도 모른다. 이 것은 다음 9장에서 더 알아보자.

[1] 그로버 검색의 오라클은 아래의 링크 참고.
https://qastack.kr/quantum/175/how-is-the-oracle-in-grovers-search-algorithm-implemented
[2] 책의 주석에, '√N 번 이상 반복한 경우에도 만족할 만한 결과가 나오지 않는 경우도 있으며, 최대값에 도달한 이후 "찾는" 상태에 진폭은 다시 감소한다'는 말이 있다.
[3] GeForce 의 GTX 750 과 Intel 의 i7-5960X 가 약 1테라플롭의 속도를 갖는다. 출처는 나무위키의 아래 링크.
https://namu.wiki/w/%EC%8A%88%ED%8D%BC%EC%BB%B4%ED%93%A8%ED%84%B0#fn-6
[4] 주로 뒤섞여 있는 소리에서 특정 소리를 분리하는 데 사용한다. 뒤섞여 있는 파동을 간단한 파동들로 나눈다. 세부 설명은 아래 나무위키 링크에 있는 동영상 참고.
https://namu.wiki/w/%ED%91%B8%EB%A6%AC%EC%97%90%20%EB%B3%80%ED%99%98
[5] 유클리드 호제(서로 나누는)법이라고 불린다. 아래 위키 링크 참고.
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95