Shor 알고리듬

 

양자 정보이론은, 양자 역학을 이용하여 양자 정보를 처리하는 이론 분야이다. 고전적인 정보이론은 Shannon이라는 천재가 1948년 정리한 정보이론 (information theory)에서 시작한다. 그는 평생에 몇편의 논문을 쓰지 않았으나, 단 3개의 논문으로 디지털 신호 처리에 관한 근본적인 질문들에 모두 답변한다. 정보란 무엇인가, 정보를 얼마만큼 줄일 수 있느냐, 정보를 얼마나 신뢰성있게 전송할 수 있느냐가 그 질문들이다. 정보이론이 무엇인지는 몰라도 MP3, MP4, mpeg, jpeg를 모르는 이는 최소한 이밴드에는 없을 것이다.

 

정보란 무엇인가, 간단히는 정보는 어떠한 사실을 알기 위해서 던져야 하는 질문의 개수이다. 예를 들어, 앞뒤면이 나올 확률이 1/2인 동전을 던졌다. 앞면일까, 혹은 뒷면일까? 한번의 질문이면 족하다. 따라서 정보량은 1bit이다. 만약 동전의 앞면이 나올 확률이 1/4이면? 대답하기가 쉽지 않을 것이다. 질문의 갯수는 -1/4log(1/4)-3/4log(3/4)이다. 엔트로피만큼 질문의 개수를 줄일 수 있다. 어떻게? 그것은 정보이론을 공부해 보시기 바란다. 오래전 나의 전공 분야 중 하나이기에, 이 분야에 관한 질문은 언제든 시원시원하게 답할 수 있다.

 

양자 정보는 Qbit에 의해서 표현된다. Qbit는 a|0>+b|1>과 같이 표현되는 양인데, 실제로 이것은 basis 상태 |0>과 |1>만이 bit일 뿐, 실제로 Qbit가 표현하는 내용은 아날로그 정보, 즉, a와 b는 |a|^2+|b|^2=1을 만족하는 모든 복소수가 가능하다는 점에서 고전적인 정보이론과는 근본적인 차이가 있다. a=a1+ja2, b=b1+jb2 이고, a1^2+a2^2+b1^2+b2^2=1이므로, 실제로 하나의 Qbit는 3차원 구면상의 모든 점들을 표현할 수 있으며 이것을 Bloch sphere라고 부른다.

 

양자 정보이론은 순수하게 이론적으로만 학계에서 연구되었다. 물론, 파인만이 양자 컴퓨터의 실현 가능성을 잠시 언급하였지만, 실제로 아무도 양자 컴퓨터를 만드는 것이 현실적으로 가능하거나, 가능하다고 하더라도 그것으로 의미있는 결과를 만들어낼 것이라고는 예측하지 않았다. 

 

그러나, 1994년 Peter Shor라는 칼텍 출신의 AT&T 엔지니어가 아주 큰 수를 소인수 분해하는 양자 알고리듬을 발표하면서부터 얘기는 완전히 달라진다. 큰 수를 소인수 분해하는 것으 무엇이 그리 중요할까? 그 의미를 아는 분들은 암호학에 대한 기초 지식이 있는 분이다. 항상 해커들이 우리의 정보를 호시탐탐 노림에도 우리가 약간은 안심할 수 있는 것은, 대부분의 금융거래가 암호화된 정보를 주고받기 때문이다. 암호화를 위해서는 통신하는 양측에서 동의하는 정보를 가지고 있어야 하는데, 이 과정에서 아주 큰 (무지무지 큰) 숫자의 소인수 분해가 고전적인 컴퓨터로는 불가능하다는 가정이 도입된다. 만약, 양자 컴퓨터가 이 가정을 무너뜨린다면.. 현재의 암호 체계는 모두 버려야 하고 금융 시스템을 완전 재설계해야 한다.

 

 

Shor 알고리듬을 이해하려면 먼저, 중국인 나눗셈 정리, Chienese remainder theorem을 이해해야 한다. 5세기 중국 고서 "손자산경"에 다음과 같은 재미있는 문제가 나온다. 

 

"3으로 나우었을 때 2가남고 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가?"

 

이것을 일반화하여, 좀 더 현대적인 표현으로 바꾸면 다음과 같은 정리로 표현된다. 어떤 수 n이 pq라는 서로소인 두 정수의 곱으로 표현된다면, 정수 x를 n으로 나눈 나머지와, (x 를 p로 나눈 나머지, x를 q로 나눈 나머지)는 1:1대응관계에 있다는 어떻게 보면 쉬운 얘기를 하고 있다. 그 증명은 유클리드 호제법을 알고 있다면 10줄 이내로 쉽게 보일 수 있다.