양자 컴퓨터

 

 

현재 많은 회사들이 양자 컴퓨터를 구현하기 위하여 불철주야 노력중이다. Google, Intel, Microsoft, IBM, blablabla... 수많은 IT 회사들이 양자역학의 진수, 슈뢰딩거의 고양이를 구현하고 있는 것이다. 만약 대규모 양자 컴퓨터가 실재로 양자 우월성을 증명한다면, 그것은 존재론적으로도 큰 의미를 가진다. 거시 세계에서 슈뢰딩거 고양이와 같은 존재, 하나의 시공간에서 유령같은 양자적 병렬 신호 처리가 이루이지는 것이다. 양자적 병렬성이 존재하는 시공간은 어떤 의미에서는 우리 공간과 평행하게 진행하는 또하나의 차원처럼 해석할 수도 있다.

 

그러나, 양자 컴퓨터에 대한 아이디어가 나온지 오랜 시간이 지났지만, 여전히 아주 많은 기술적 난제가 남아 있고, 혹자들은 양자 컴퓨터는 계산 과정의 오류를 극복하지 못하고, 끝내 실현 불가능한 꿈으로 남을 것이라, 부정적으로 바라보는 학자들도 있다. 아직, 그 판단을 내리기는 어렵지만, 만약에 양자 컴퓨터가 개발된다면, 최초로 개발한 국가는 다른 나라 대비 엄청난 산업적 진보를 이룰 것이 틀림없기에 거의 모든 나라가, 차세대 핵심 기술중 하나로 인공지능과 더불어 양자 컴퓨터를 꼽고 있다.

 

아래는 Shor 알고리듬이란 것을 나름대로 공부하고 정리한 내용이다. 아래 내용을 끝가지 쫓아갈 분은 밴드에는 거의 없을 것이다. 사실, Shor 알고리듬에 대해서 처음부터 끝까지 정확히 쉽게 정리된 자료를 찾기는 쉽지 않다. Horizon의 김한영 박사가 정리한 자료도 있지만, 그 방대한 내용에서도 detail 부분은 빠져 있다. 

 

==========================

 

두 수의 최대 공약수는 중고등학교 때 배운 유클리드 호제법을 사용한다. 간단히 수식으로는 다음과 같다. 오래전 일이지만 기억이 어렴풋이 날 것이다. 먼저, 두 수중 큰 숫자를 찾아서 작은 숫자로 나눈 나머지를 적는다. 그 나머지와 작은 숫자와의 최대 공약수를 같은 요령으로 구한다. 이러한 과정을 반복하다가 나머지가 0이 되는 수가 나타나면 그 수가 최대 공약수이다. 아래 예제를 보면 8이 gcd(106,48)임을 알 수 있다.

 

수식적으로 표현하면 아래와 같이 쓸 수 있다.

 

이제 아주 큰 수 n을 소인수 분해하는 quantum algorithm, 쇼어 알고리듬을 적어보면 아래와 같다.

 

1. Choose a random a<n

2. Find order r(somehow) such that a^x=1 mod n

3. Compute p,q=gcd(a^(x/2)+-1,n) if  r  is even, otherwise goto 1.

4. If gcd is 1, then goto 1, otherwise p or q is the factor we want to solve.

 

1번과 3번은 고전 컴퓨터로도 비교적 쉽게 구할 수 있다. 문제는 2번, 즉, x의 차수, 즉 x를 몇번곱하면 n으로 나눈 나머지가 1이 되는가 혹은 f(x)=a^x mod n 이라는 함수의 주기(period)는 무엇인가를 찾는 문제인데, 이것은 고전 컴퓨터로는 절대로 빠르게 구할 수 없다. Shor는 2번 알고리듬을 양자 컴퓨터로 쉽게 계산할 수 있는 방법을 제시하였다. 그것은 quantum FFT (Fast Fourier Transform)이라는 방법으로 해결한다.

 

만약 어떤 수 a가 주어진 경우, a^x=1 mod n인 x를 쉽게 찾을 수 있다고 하자. f(y)=a^y로 정의하는 경우, f(y+x)=a^(y+x)=a^y a^x=a^y=f(y)가 되어, f(y)의 주기를 쉽게 구할 수 있다는 가정과 동일하다. 그러면 당연히 a^x-1=0 mod n이고, 만약 x가 짝수라면 즉, x=2z라면 (a^x-1)=(a^z+1)(a^z-1)로 인수분해가 되고 만약 각각의 어느것도 n의 배수가 아니라면, 예를 들면 a^z+1 mod n=0이 아니라면, gcd(a^z-1, n)이 n의 factor일 것이다. 물론, gcd가 1이면 나가레.. 다시 시작해야 한다. 왜 그런가? 이것을 이해하려면 이전에 게시한 Chienese Remainder theorem (CRT) 를 이해하면 된다.

 

CRT에 따르면 x^2=1 mod n(=pq)는 4개의 답중 하나를 가진다. 즉 x = yz, y= +-1 mod p, z= +-1 로 구성되는 네 값이다. 따라서 이 문제에서 a^z-1은 p 또는 q의 배수일수 밖에 없고, 따라서 gcd(n, a^z-1)은 p 또는 q일수 밖에 없다.

 

그러나 문제는 어떤 수 a의 차수(order), 즉 a^x=1 mod n을 만족하는 x를 적인 컴퓨터로는 쉽게 구할 수 없다는 데에 있다. 그냥 다 대입해 봐야 하는데, 일단 n이 무지막지하게 큰 값이고 x는 0과 n사이의 어떤 값도 될 수 있기에, 모두 대입하자면 아마 이 생에 끝마치지 못할 가능성이 99%이상일 것이다.

 

앞서 설명한 데로, 이 문제는 f(x)라는 주기 함수의 주기 p를 찾는 문제이다. 즉 f(x)=f(x+p)인 p를 찾는 문제이다. 만약, 어떤 함수가 주기함수라면, 그 함수를 Fourier 변환하면 주기의 배수에 해당하는 주파수에만 값이 존재하고, 나머지 주파수의 값은 거의 0이다. 주기함수는 Fourier series로 전개가 가능하기 때문이다.

 

그러나, 양자역학에서는 n bit의 Qbit는 중첩을 허용하기에 일단 가능한 모든 중첩 상태를 생성하는 것은 크게 어렵지 않다. 먼저, Hardmard 변환연산자를 이해하자. 그것은 아래와 같이, 0 또는 1 상태를 그 둘의 중첩 상태로 만드는 연산자이다.

 

이러한 연산을 n번 적용하게 되면 아래와 같이 모든 상태를 포함하는 중첩된 상태를 만들 수 있다.

 

이제, Hardmard 변환과, QFT를 결합하여 Quantum parallelism 을 이용하여 연산량을 줄이는 방법을 알아보자. 아래에서 부터는 Prekill 교수의 강의록을 따라서, 적기에 표기법을 변경한다

 

위의 과정은 아래 그림과 같은 과정을 n bit 까지 확장함으로써 계산할 수 있다. 즉, 계산량이 O(n)=O(logN) 이다.

 

H는 앞서 설명한 Hardmard 연산자이고, R_d은 (1 0; 0 exp(ipi/2^d), 즉 1> basis를 일정한 각도만큼 회전하는 unitary operator이다.

 

이제 여기에 f(x)=a^x mod n을 구현하는 unitary 연산만 추가하면 QFT를 계산하는 모든 과정을 기술한 것이다. 얼핏 보면 모든 x에 대해서 즉 예를 들어 N=10^200의 모든 x에 대해서 f(x)를 계산해야 하기에, 구하는 것이 거의 불가능한 연산처럼 보인다. 그러나, 실제로는 quantum parallelism을 적용할 수 있기에 이 연산도 복잡하지 않다. 다음과 같이 먼저 a, a^2, a^4, a^8 등 n개의 값만 일반 컴퓨터로 계산한다. 그 다음에는 x의 각 bit로 그 값들을 control 하면 된다.

 

 

이제 이 과정들을 모두 종합하면 Shor 알고리듬을 quantum computer로 구현한 것이다. Shor 알고리듬이 나온지가 어언 26년이 넘었다. 그러나, 15의 소인수 분해를 Shor 알고리듬으로 성공한 후, 더 이상 진보가 없다. Quantum computer에 대한 낙관적인 전망과 비관적인 전망이 현재 상존하고 있다. 많은 미국 회사들이 QC를 구현하기 위해서 노력중이나, 실제로 크게 의미 있는 결과는 나온 것이 별로 없다. 왜 그럴까? 왜 양자적이론은 복잡하지 않은데, 그 구현이 이렇게 어려운 것일까? 그것을 이해하려면, quantum gate가 어떻게 동작하는지를 이해해야 할 것이다.