d라이브러리

21세기는 양자기술의 시대라고 한다. 20세기에 닦아놓은 양자과학이 본격적으로 공학에 응용된다는 말이다. 그 중 하나가 바로 양자전산이다. 컴퓨터 분야에서 양자이론이왜 중요하게 받아들이는 것일까.

인류는 물질, 힘, 그리고 에너지와 같은 다양한 물리적인 자원을 활용하는 새로운 방법을 발견하면서 발전해 왔다. 그리고 20세기에는 정보가 활용자원의 하나로 등장하게 됐다. 이 시기에 뇌에서 이뤄졌던 복잡한 정보처리를 대신 해줄 수 있는 컴퓨터가 발명됐기 때문이다. 이로 인해 21세기에는 급속도로 팽창하는 정보를 어떻게 활용하는가가 삶의 질을 결정하는 주요 지표가 되고 있다.

그러나 컴퓨터가 처음 개발됐을 때 사람들은 과연 현재와 같은 변화를 상상할 수 있었을까. 진공관 1만8천개로 구성된 집채만한 장비로 지금의 계산기 수준밖에 되지 않는 컴퓨터를 보고서 이같은 생각을 하기는 쉽지 않았을 것이다. 이후 컴퓨터는 트랜지스터, 집적회로가 개발되면서 점점 소형화돼 왔다. 이것은 컴퓨터 성능 발전에 결정적으로 이바지했고 현재의 정보통신 혁명을 가능하게 해주었다. 그래서 21세기를 시작하는 2000년도 노벨물리학상을 집적회로와 반도체기술 분야에 수여하지 않았던가.

0과 1 두값을 동시에 가진다

지금은 더욱 발전해 1미크론(${10}^{-6}$m) 보다 작은 논리 게이트나 회로를 실리콘칩의 표면에 식각할 수 있다. 그리고 머지 않아 탄소나노튜브와 같은 나노기술의 발달로 단지 몇개의 원자로 구성되는 논리 게이트를 만들 수 있으리라 예상된다.

그런데 이처럼 컴퓨터의 부품이 원자단위로 작아지면 고전역학이 아닌 양자역학의 지배를 받게 된다. 이런 이유로 컴퓨터 분야에서 양자기술이 필요하게 됐다.

왜 양자기술이 컴퓨터에 적용되는 것일까. 양자컴퓨터가 기존의 컴퓨터와 무엇이 그다지도 다르다는 것일까. 이를 이해하기 위해서 비트에 대해 알아보자. 비트는 보통 이진수 0 또는 1 중 하나를 의미하는 가장 기본적인 정보 단위를 의미한다. 그러나 물리적으로는 예와 아니오, 참과 거짓, 또는 0과 1처럼 두개의 논리값을 나타내는 서로 다른 두 상태 중 하나만을 가지는 물리적 시스템이다. 예를 들어 디지털 컴퓨터에서 축전기의 두판 사이의 전압은 물리적으로 한 비트가 될 수 있다. 대전된 축전기는 비트값 1, 그리고 대전되지 않은 축전기는 비트값 0으로 표시할 수 있다. 또 한 비트의 정보는 빛의 두 편광상태나 원자의 두 전자상태로 나타낼 수도 있다.

그러나 만일 원자를 물리적 비트로 택한다면 문제는 달라진다. 양자역학은 원자가 두 전자 상태 외에 두 상태의 ‘결맞는’ 중첩상태(coherent superposition)를 가질 수 있음을 제시한다. 즉 원자는 0과 1 두 상태를 동시에 가진다는 말이다. 이 사실에 익숙해지기 위해서 다음의 실험을 생각해보자.
 

하나의 광자를 빛살 가르개에 통과시키자. 여기서 빛살 가르개는 들어오는 빛의 절반은 반사시키고, 나머지 절반은 통과시킨다(그림 1). 그렇다면 빛살 가르개를 만난 하나의 광자는 어떻게 될까. 반사될까 아니면 투과될까. 실험결과는 두 광검출기에 광자가 50%의 확률로 검출된다. 따라서 광자는 반사 경로와 투과 경로 중 하나를 무작위적으로 택할 것이라고 쉽게 말할 수 있을 것이다.

그러나 이것이 과연 맞는 사실일까. 이를 확인하기 위해 반사되고 투과된 빛을 다시 모아보자. 광자가 빛살 가르개를 통과한 후의 두 경로에 두개의 완전 반사 거울을 놓고 광자가 모이는 지점에 또하나의 빛살 가르개를 배치한다. 그리고 광자가 두번째 빛살 가르개를 통과한 후 지나갈 것으로 예상되는 두 경로에 각각 광검출기를 설치하자(그림 2). 과연 두 광검출기에서 광자는 어떤 확률로 기록될까. 반반일까.
 

저장능력 지수적으로 증가

여기서 실로 놀라운 양자 현상을 관측할 수 있다. 만일 광자가 첫번째 빛살 가르개에 의해서 50%의 확률로 반사되거나 투과된다면, 두 광검출기에 각각 50%의 확률로 광자를 기록할 것이다. 그러나 실험 결과는 전혀 다르다. 만일 두 경로의 길이가 정확히 같다면, 하나의 광검출기에만 100%의 확률로 광자를 기록하고 나머지에는 전혀 광자를 기록하지 않는다. 광자는 반드시 하나의 광검출기에만 도달한다.

이 사실이 어떻게 광자가 동시에 두 경로를 간다는 사실을 입증해준다는 것일까. 이번에는 한쪽 경로에 흡수판을 놓아보자(그림3). 그러면 두개의 광검출기에 각각 50%의 확률로 광자가 기록된다. 따라서 광자가 두 경로를 동시에 지난다고 생각할 수밖에 없다. 즉 두 빛살 가르개 사이에서 광자는 반사 경로와 투과 경로를 모두 지난다고 말하는 것이 타당하다.
 

이같은 사실을 다소 전문적인 표현으로 나타내면, ‘광자가 투과 빔과 반사 빔의 결맞는 중첩상태에 있다’고 말한다. 같은 맥락으로 원자도 서로 다른 두 전자상태의 중첩 상태를 가질 수 있다. 양자역학에서의 이런 두 상태 시스템을 ‘양자 비트’ 또는 ‘큐비트’라고 부른다. 즉 큐비트는 두 논리 상태인 0과 1의 중첩 상태를 가진다. 따라서 한 큐비트는 0과 1을 동시에 나타낼 수 있다.

이제 중첩의 개념을 좀더 확장시켜 보자. 세개의 물리적 비트로 구성된 레지스터를 생각하자. 레지스터는 컴퓨터의 중앙처리장치 중 연산장치 속에 들어 있는 작고 매우 빠른 기억장치이다. 고전적으로 세개의 물리적 비트로 구성된 레지스터는 매 순간 8가지 상태 중 하나만을 저장할 수 있다. 8가지 상태는 (000), (100), (010), (001), (110), (011), (101), (111)를 말한다.

그러나 세개의 큐비트로 구성된 양자 레지스터는 이 8개의 상태 모두를 동시에 저장할 수 있다. 이미 한 큐비트가 동시에 0과 1의 두 상태를 나타낼 수 있으므로, 8가지 상태가 세 큐비트로 구성된 레지스터에 모두 나타난다는 것은 별로 놀라운 일이 아니다.

만약 큐비트 수를 점점 증가시킨다면 레지스터의 저장 능력은 어떤 비율로 증가하게 될까. 1이면 0과 1인 두상태, 2라면 (00), (01), (10), (11)로 4가지 상태, 그리고 3일때는 8가지 상태이므로 L 큐비트는 ${2}^{L}$개의 상태를 동시에 저장할 수 있다. 지수적으로 증가하는 것이다.

따라서 일단 레지스터에 서로 다른 상태의 중첩이 가능하다면, 그 모든 상태에 대한 연산을 동시에 수행할 수 있다. 즉 오직 한번의 전산 단계로 2L개의 서로 다른 입력 상태에 대한 수학적 연산을 수행할 수 있다. 그런데 기존 컴퓨터라면 이를 위해 ${2}^{L}$ 번 반복해야 한다. 따라서 양자컴퓨터는 시간과 메모리 면에서 엄청난 이득을 제공할 수 있다.

곱셈은 빠르지만 분해는 어렵다

그렇다면 이런 측면 때문에만 과학자들이 양자컴퓨터의 개발에 매달리는 것일까. 이 차이라면 기존컴퓨터도 양자컴퓨터가 수행하는 일은 모두 할 수 있다. 단지 보다 많은 시간과 메모리를 필요로 할 뿐이다. 그러나 양자컴퓨터의 진정한 매력은 이것이 아니다. 과연 어떤 점일까.

컴퓨터가 특정문제를 풀기 위해서는 그 문제의 다른 어떤 예시에 대해서도 답을 이끌어내도록 응용될 수 있는 정교한 명령들의 집합을 따라야 한다. 이러한 명령들의 집합에 대한 일련의 열거를 ‘알고리듬’이라고 부른다.

알고리듬의 한 예로는 초등학교에서 배우는 덧셈과 곱셈에 대한 과정이다. 만약 한 학생들이 일단 두자리 수의 덧셈이나 곱셈을 할 수 있다면 그 이상의 수에서도 쉽게 이런 연산을 해낼 수 있다. 그런데 그렇지 못한 연산도 있다.

다음의 소인수분해 문제를 생각해보자.

x × y = 29083

위 식을 만족시키는 두수를 찾아보자. 시간이 얼마나 걸릴까. 아마도 1시간은 족히 걸릴 것이다. 그러나 반대로

127 × 229 = ?

을 푸는 데는 1분도 채 걸리지 않는다. 이는 우리가 곱셈에 대해서는 빠른 알고리듬을 알고 있지만, 분해에 대해서는 그렇지 못하기 때문이다.

표준 정의에 따르면 빠르고 유용한 알고리듬이란 특정한 한쌍의 수를 곱하는데 걸리는 시간이 아니고 같은 방법으로 점점 더 큰 수에 적용했을 때 걸리는 시간이 어떻게 증가하는가로 결정된다.

컴퓨터 과학자들의 경우는 알고리듬에 대해 좀더 명확한 정의를 내리고 있다. 입력의 크기가 증가함에 따라 계산하는데 걸리는 시간이 다항식(입력값의 자리수)으로 늘어날 경우 그 알고리듬은 유용하고 빠르다고, 만일 시간이 지수적으로 늘어난다면 그 알고리듬은 유용치 않고 느리다고 말한다.

만약 컴퓨터가 두개의 세자리 이진수와 두개의 30자리 이진수를 곱셈한다면 두 곱셈 사이에는 시간적으로 별 차이가 없다. 반면 세자리 이진수를 30자리 이진수로 바꿔 분해하게 하면 3자리 수에 비해서 무려 ${10}^{13}$배의 시간과 메모리를 필요로 한다.

따라서 우리는 곱셈의 경우 유용한 알고리듬을 갖고 있지만 분해의 경우 그렇지 못하다. 분해는 어려운 문제에 속하는 것이다. 그러나 어렵다고 해서 불가능하다는 것은 아니다. 단지 실질적 능력 밖의 일임을 의미한다. 즉 분해도 기존컴퓨터로도 풀 수 있다. 하지만 매우 큰 수를 분해하기 위해서는 너무도 많은 시간과 메모리를 요구해서 실제적인 계산을 수행할 수 없다. 예를 들어 기존컴퓨터로 1천자리 이진수를 인수분해한다면 우주의 나이보다 더 긴 시간이 필요하다. 과연 이 문제를 푸는 것이 현실적으로 가능하다고 표현할 수 있을까.

그렇다면 시간과 메모리가 우수하기 때문에 양자컴퓨터에게는 이런 분해가 쉬운 문제에 속하게 될까. 대답은 ‘그렇지 않다’이다. 더욱 중요한 것은 양자기술에 힘있는 새롭고 좋은 알고리듬에 있다. 지수적으로 증가하는 수를 담고있는 양자의 중첩상태를 활용하는 ‘양자 알고리듬’을 말이다. 이것이 바로 전산분야에서 양자기술의 진정한 힘이다. 고전적으로 개념조차 없었던 양자 알고리듬에 의해 양자컴퓨터는 질적으로 새로운 방법의 프로그램을 할 수 있게 된다.

실제로 지금까지 몇가지 양자 알고리듬이 개발돼 응용되고 있다. 가장 대표적인 것으로는 AT&T 벨연구소의 로브 그루버가 1996년에 발표한 것이다. 그가 발견한 알고리듬은 ‘N개의 항목으로 만들어진 목록에서 특정한 항목을 $\sqrt{N}번의 단계만을 거쳐 확률 50%로 찾아낼 수 있다’는 것이다.
 

암호학에서 인정받은 양자 알고리듬

한 예로 가나다 순으로 1백만명의 이름이 수록된 전화명부에서 특정인의 전화번호를 찾아낸다고 하자. 기존컴퓨터는 특정인의 전화번호를 찾을 때까지 전화명부에 수록된 이름을 하나씩 훑어보면서 찾는다. 따라서 평균적으로 50만번 메모리 확인을 필요로 한다.

그러나 양자컴퓨터는 단 한번에 모든 이름을 동시에 조사할 수 있다. 그런데 만일 그 시점에서 결과를 프린트하도록 프로그램한다면, 고전적 알고리듬에 비해서 더 나아진 것은 없다. 왜냐하면 결과에 대한 측정은 그 중 오직 하나만을 보여주기 때문이다. 따라서 1백만개의 경로 중 오직 하나만이 우리가 원하는 이름을 확인할 것이고 컴퓨터는 이들 중 하나만을 측정할 수 있을 뿐이다. 따라서 원하는 전화번호를 얻을 확률은 1백만분의 1에 불과해진다.

그러나 만일 컴퓨터 속의 양자 정보를 측정하지 않는다면, 이어지는 또다른 양자 연산은 그 정보가 다른 경로에 영향을 주도록 만들 수 있다. 이런 방법으로 찾고자 하는 특정인에 대한 정보는 양자 간섭에 의해 확산된다. 이러한 간섭을 일으키는 연산을 1천번 정도 반복하면(일반적으로 $\sqrt{N}$번원하는 전화번호를 50%의 확률로 알아낼 수 있다. 따라서 전체 알고리듬을 몇번 더 수행함으로써 그 확률을 1에 매우 가깝게 증가시킬 수 있다. 기존컴퓨터로 찾아내려면 1에서 1백만번의 범위에서 연산을 수행하게 되지만, 이런 양자 알고리듬을 이용해 양자컴퓨터는 그 수를 단지 수천번으로 압축해준다.

만약 장기게임에서 이런 그루버 알고리듬을 적용하면, 어떤 주어진 위치에서 기존컴퓨터로는 단지 1백만개 정도의 앞수를 내다볼 수 있는 정도의 전산과정으로 무려 조 단위의 앞수를 알아볼 수 있다.

그러나 장기게임보다도 양자 알고리듬이 중요하게 인식된 분야는 암호 분석에 있다. 현대의 암호체계인 DES(Data Encryption Standard)를 해독하기 위해서는 ${2}^{26}$ = 7 × ${10}^{16}$개 중 하나의 암호키를 찾아내야 한다. 만약 기존컴퓨터로 1초에 1백만 키(key)를 훑어보는 속도로 조사한다면 올바른 키를 찾아내는데 무려 1천년이나 걸린다. 그러나 그루버 알고리듬을 사용하면 단 4분만에 이를 해결할 수 있다. 양자컴퓨터의 우월성이 암호학에서 나타난 것이다.

이처럼 양자 알고리듬이 강력한 힘을 가진다는 것을 최초로 보인 사람은 그루버와 같은 연구소에 있는 피터 쇼다. 1994년 쇼는 소인수분해 알고리듬을 발표했는데, 이 알고리듬으로 현대의 암호체제를 알 수 있는 암호 키를 하루 안에 얻을 수 있었다.

이후 쇼와 그루버의 알고리듬의 중요성을 인식한 정부는 양자전산 연구를 지원하기 시작한다. 미국의 경우, CIA, 국가정보국, 국방성 그리고 육해공군이 모두 이 분야에 연구비를 지원하고 있다. 또한 로스알라모스 연구소, NASA, 표준연구소 등 국립 연구소와 벨연구소, IBM 등 쟁쟁한 회사연구소들이 이 연구를 주도하고 있다.

수년 안에 실현될지도

이렇게 양자 현상을 전산에 이용할 수 있는 가능성을 처음으로 제안한 사람은 1982년 그 유명한 물리학자 리처드 파인만에 의해서다. 그는 양자현상을 기존 컴퓨터로 시늉내기가 불가능하다는 것을 알았다. 이는 양자 진화를 기술하기 위해서 필요한 고전적 정보의 양이 같은 정확도로 대응하는 고전적 시스템을 기술하는데 필요한 양보다 지수적으로 훨씬 크기 때문이다.

그러나 파인만은 이러한 난점을 장애물로 생각하기 보다, 장점으로 생각했다. 만일 다중 입자의 간섭 실험에서 일어나는 것을 알아내기 위해 그다지도 많은 계산이 필요하다면, 그런 실험 장치를 설치하고 출력을 측정하는 그 행위는 바로 복잡한 계산을 수행하는 것과 동일하다고 지적했다.

과연 양자컴퓨터는 언제쯤이나 우리 곁에 찾아올 수 있을까. 원리적으로 과학자들은 양자컴퓨터를 구축하는 방법을 알고 있다. 간단한 양자 논리 게이트로 출발해, 이것들을 양자 네트워크로 연결하면 된다. 고전적 게이트와 같이 양자 논리 게이트도 주어진 시각에 두 큐비트에 행하는 하나의 기본적인 양자 연산을 수행하는 전산 장치이다. 물론 양자 논리 게이트는 양자 중첩 상태를 만들어내고 그것에 연산을 작용한다는 점에서 고전적 게이트와 구별된다.

그러나 이론적으로 아는 것과 실제 구현하는 것 사이에는 큰 차이가 있다. 네트워크에서 양자 게이트 수가 증가함에 따라 곧 심각한 현실적 문제에 봉착한다. 우선 단일 원자와 단일 광자를 과연 조종할 수 있느냐의 문제에 부닥친다. 그러나 이것보다 더 중요한 문제는 상호 작용하는 큐비트 수가 증가할수록 양자 간섭에 수반되는 상호 작용을 어떻게 처리할 것인가이다. 보다 많은 성분이 존재할수록 양자 정보가 양자컴퓨터를 벗어나 주위 환경으로부터 영향을 받고 손실돼버려 계산을 망치기 쉽기 때문이다. 이를 가리켜 결맞음성 또는 중첩성이 깨진다고 표현한다. 따라서 매우 작은 시스템을 제어해 큐비트끼리는 서로 영향을 끼쳐도 주위 환경의 영향은 가능한 없애야 한다.

이와 같은 현실적인 어려움에도 불구하고 어떤 물리학자들은 양자전산 기술의 실제적인 발전에 대해 낙관적인 전망을 가진다. 적어도 양자전산의 한두 단계가 수행되는 시간 동안에는 결맞음성이 보존되게 만들 수 있다고 믿기 때문이다.

보다 낙관적인 연구자들은 실용성있는 양자컴퓨터가 수년 안에 등장할 것으로 믿는다. 낙관론자들의 의견을 믿어봄이 어떨까. 양자컴퓨터를 구현하는 과정에서 근본적인 장애물이 없고, 관련 실험을 수행하는 연구자들의 재능과 능력을 믿으며, 그리고 무엇 보다도 때때로 낙관이 일을 만든다면 가능하지 않을까.