양자역학적 정보처리
글: 지동철 교수 (수리과학부)
20세기에 이루어진 물리학 발견 중 양자역학과 상대성이론이 그 심오함이나 영향력에서 가장 두드러진 것이라 하겠다. 상대성이론은 천재 아인슈타인 개인이 이룬 업적인데 비해 양자역학은 플랑크, 보어, 아인슈타인, 슈뢰딩거, 디랙, 하이젠베르크 등에 의하여 이루어졌다. 이 중 우리의 일상생활에 미친 영향은 양자 역학이 훨씬 더하다. 컴퓨터, TV, 휴대전화 등 현대 문명의 이기대부분이 양자역학과 밀접한 관계가 있다. (그러나 이들의 정보처리 기반 논리는 아직도 고전적이다.) 양자역학이 우리의 생활 여러 방면에 이렇게 많은 기여를 하고 있지만 양자역학 세계는 우리의 직감과 너무 동떨어져 이를 이해하는 것은 아직 우리의 능력을 넘어서고, 대부분의 물리학자들도 양자역학을 사용할 뿐 이해하려고 하지 않는다. 일찍이 파인만도“이 세상 어느 누구도 양자 역학을 이해할수 없다”라고 하였다.
최근 소형화에서 극소형화로 발전하고 있는 반도체 기술의 발전은 멀지 않아 1비트(bit, 0이나 1의 정보)에 필요 한 원자수가 수개 내외로 될 것이다. 이때에는 정보 처리에 있어서 양자현상을 피할 수 없게 된다(지금까지 반도체 칩설계에 있어서 양자 현상을 피하여 왔음). 그런데 양자 현상은 고전 현상과는 아주 달라 지금 사용하고 있는 0과 1을 기본으로 하는 고전적 정보처리 방법으로는 그 목적을 이룰 수 없다. 따라서 미시세계의 원리인 양자역학에 기반을 둔 새로운 정보처리 방법을 만들어야 한다.
20세기에 들어와서 이루어진 또 다른 과학 혁명은 정보의 계량화이다. 그 전까지는 정보의 가치를 그저 감성적으로 이해하던 것을 1945년경 미국의 섀넌(Shannon)은 정보의 가치를 엔트로피(entropy)라는 것으로 계량화하였다. 어떤 정보의 엔트로피란 주어진 정보를 될 수 있는 데로 압축하여 0과 1로 표현할 때 필요한 비트 수이다. 엔트로피를 통하여 정보를 질량이나 에너지, 운동량과 같은 수량화된 물리량으로 만들었다. 정보의 계량화는 양자역학이나 상대성이론 같이 현란하지는 않으나 암호기술, 데이터 압축기술, 커뮤니케이션 등 현대의 컴퓨터 과학 중많은 부분에 필수적이며 우리의 정보 지식 기반사회에 많은 영향을 주고 있다. 최근 이론에 의하면 우주의 근본이나 블랙홀을 연구할 때에도 엔트로피가 중요한 물리적 양으로 이해되고 이들의 형성이나 미래가 엔트로피에 크게 의존한다. 어떤 물리학자는 우주 자체를 정보로 이해하려는 시도를 하고 있다 (It from Bit).
지금부터 이야기할 양자 정보, 양자 계산이란 바로 20세기에 탄생된 두 개념, 양자역학과 정보의 종합적인 한 형 태라고 할 수 있다. 정보처리나 계산이 궁극적으로는 물리적 계에서 수행되기 때문에 물리학의 근본인 양자역학 과 정보이론이 결합하는 것은 당연한지 모른다. 양자역학에서는 물리계에 대한 정보 취득 행위는 필연적으로 그 계를 흐트러트리므로 양자역학적 정보는 완벽하게 복사될 수 없다(만일 완벽하게 복사할 수 있으면 원본 대신 복 사본을 가지고 측정을 함으로서 원래 계를 흐트러트리지 않고 측정을 한 셈이 된다. 이는 양자역학의 기본 공리에 어긋난다). 이는 복사(copy) 명령으로 파일(file)을 마음대로 복사할 수 있는 우리들 PC의 정보처리와는 전혀 다르다.
고전계를 기술하는 공간의 차원이 물체 수에 따라 일차적으로 증가하는 반면 양자계에서는 지수적으로 증가한다. 따라서 고전적 계산으로는 양자 현상을 효과적으로 기술할수 없다. 바로 이 점에 착안한 파인만은 거꾸로 양자역학을이용하여 고전계산을 효과적으로 할 수 있지 않을까 하는 제안을 하였다.
이와 같이 양자 정보처리가 고전 정보처리와는 전혀 달라 양자역학적 정보처리나 양자계산에서 획기적 산물이 나올 것을 기대하게 한다. 대표적인 예가 1994년 미국 MIT 수학부의 피터 쇼어 (Peter Shor)에 의한 다항식시간 양자 소인수분해(factorization) 계산법이다. 소인수 분해란 주어진 수를 소수의 곱으로 나타내는 것을 말한다. 소인수 분해 문제는 해가 주어지면 쉽게 확인할 수 있으나 그 해를 찾는 것은 아주 힘든 문제이다. 예를 들어 두 수 1,043과 16,453의 곱이 17,160,479가 됨을 쉽게 알 수 있으나 거꾸로 곱해서 17,160,479가 되는 두 수를 찾는 것은 무척 힘들다. 소인수 분해에 대하여 지금까지 알려진 제일 좋은 고전적 계산 방법으로도 주어진 수의 자릿수에 대하여 지수적으로 많은 시간이 필요하며, 이는 현재의 기술로 130자리 수의 약수를 찾아내는 데 많은 워크스테이션을 이용하여 병렬 계산하더라도 1개월 정도의 시간이 필요하다. 또한 400자리 수의 약수를 찾아내는 데에는 약 1010년 (우주 나이 정도)이 걸려, 현재의 컴퓨터 기술이 아무리 발달하여도 400 자리 수를 소인수 분해하는 일은 얼마 동안 인간 능력 밖이다. 소인수 분해 문제는 수학적으로만 중요한 문제가 아니라 현재은행 거래나 인터넷 거래에서 가장 널리 쓰이는 RSA 공개키 암호체계의 기본이다. 따라서 쇼어가 발견한 다항식 시간 양자 소인수 분해법은 RSA 암호 체계의 붕괴를 의미한다. 만일 양자 계산기가 쇼어 계산법을 사용하여 130 자리 숫자를 1시간에 소인수 분해하면 400 자리 숫자를 소인수 분해하는 데에는 24 시간 정도 걸릴 것이다. 이는 아직 긴 시간이지만 우주의 나이 보다 훨씬 짧은 시간이다.
A와 B가 어떤 양자상태를 공유하면 이것을 이용하여 A가 가지고 있던 또 다른 양자상태를 B에 보낼 수 있다. 이는 우리가 흔히 사용하는 FAX와 비슷하나 여기에서는 원본이 직접 B에게 전달된다는 것이다. 이것을 양자전송(Quantum teleportation)이라고 하는데 혹시 여러분 중 SF인 스타트랙을 보신 분이 있으면 우주선에서 땅위로 또는 땅위에서 우주선으로 'energize'해서 옮기는 것을 기억하실 것이다. 바로 이런 꿈같은 일이 양자역학세계에서는 가능하다. 그리고 이는 사람같이 큰 물체는 아니나 최근 전자 상태나 광자상태를 약 150 km 떨어진 다른 곳으로 보내는 실험에 는 성공을 거두었다.
쇼어(Shor)의 소인수분해 알고리즘과 더불어 양자계산이 수행할 수 있는 또 다른 이상한 경이적인 계산에는 데이터베이스 찾기가 있다. 가령 병 안에 돌 99개, 사탕 1개가 있다고 할 때 사탕을 꺼내기 위하여 약 50번 이상 찾아보아야 할 것이다. 일반적으로 N개의 테이터 중 원하는 것이 1개일 때 약 번 정도 찾아보아야 할 것이다. 그런데 양자역학은 약 번 정도에 거의 확률 1로 찾기를 수행할 수 있는 계산법을 마련해 준다. 앞에서 나온 사탕 찾기 경우 약 10번 정 도 찾으면 사탕으로 찾는다는 이야기다. 이는 그렇게 큰 이 득이라고 생각하지 않을 수 있으나 만일 원하는 데이터가 100만개중 하나일 때 50만 번과 1000번은 아주 큰 차이이다. 그런데 양자역학 세계에서도 시행 회수를 보다는 더 낮출 수 없다는 것이 증명되었다. 자료 중에서 원하는 자료 의 수가 4분의1 이상인 경우는 원하는 것을 찾기 위하여 평균적으로 2번, 최악의 경우 4번까지 찾기를 해야 한다. 본 연구팀은 단 한번의 시도로 원하는 자료를 찾는 양자 알고리즘을 만들었다.
우리들이 사용하는 PC 보다 슈퍼컴이 훨씬 빨리 계산하고 더 많은 일을 수행한다. 그러나 슈퍼컴이 하는 일은 어느 것 이나 느리지만 우리의 PC를 가지고도 할 수 있다. 또한 어 떤 계산 과정이 우리의 PC에서 자리 수에 따라 지수적으로 시간이 걸리면 슈퍼컴에서도 그렇고, 슈퍼컴에서 다항식 정 도의 시간이 걸리면 우리의 PC에서도 그렇다. 다시 말하면 문제의 난이도, 즉 답을 구하는 데 걸리는 시간이 자리 수에 따라 증가하는 모습은 기계에 무관한 문제 고유의 성질이 다. 따라서 계산 문제를 입력 비트 수가 증가함에 따라 답을 구하는 데 걸리는 시간이 증가하는 정도에 따라 분류할 수 있다(이를 복잡성 문제라고 한다). 시간이 다항식 정도 걸리 는 문제를 Ρ, 그보다 더 많은 시간이 걸리는 문제를 ΝΡ라 고 한다. (여기서 ΝΡ란 아무리 좋은 알고리즘을 찾아 해 보아도 다항식 시간에 할 수 없다는 것이지 이론적으로 증명되었다는 것은 아니다). Ρ문제와 ΝΡ문제가 다르다는 것을 수학적으로 증명하는 것이 정보과학이나 수학에서 가 장 유명한 문제로 남아있다.
물리세계에서의 정보처리나 계산이 근본적으로는 양자역학적이더라도 양자계산기를 고전계산기로 다항식 정도에 시늉내기를 할 수 있으면 복잡성 관점에서 보면 양자계산이 그렇게 흥미로운 것이라 할 수 없다. 그러나 파인만이 일찍 인지하였고 쇼어의 양자계산법에서 알다시피 일반적으로 양자 현상을 고전계산기로 다항식 시간정도로 시늉 내기하는 것은 불가능하다(소인수 분해문제는 고전계산으로는 ΝΡ이지만 쇼어 계산법은 양자계산으로는 ΝΡ라는 것을 보여 준 것이다). 따라서 고전계산에 의한 복잡성의 분류와 물리적, 더 구체적으로 양자계산적 분류는 서로 다르다는 이야기가 된다. 이는 계산학의 바탕을 뒤흔드는 일이고 미래의 기술에 큰 충격을 주는 것이다. 물리적으로는 간단한 양자계의 계산도 고전계산으로는 효과적으로 수행 할 수 없다는 것을 말해 주며, 거꾸로 간단한 양자계산도 우리에게 많은 환상적인 결과를 줄 것을 시사한다(고전적 계산은 항 상 같은 난이도로 양자 계산적 시늉내기가 가능하다).
위와 같은 경이적인 능력을 가지는 양자 계산을 실제로 구현하는 일은 아직 유치한 단계이다. 그러나 지금 사용하고 있는 계산기는 곧 한계에 다다를 것이고 과학 발전이 인간 의 근본 속성이건데 이 한계를 이기게 될 것이다.
* 위 글은 수리과학부 지동철 교수가 <자연대 이야기> 11호에 기고한 글입니다.