정보엔지니어 (맥스웰의 도깨비, 양자컴퓨터)

사실 양자 컴퓨터의 존재에 대해 많은 기사가 쏟아져 나오는데, 실질적인 양자 컴퓨터의 등장 여부를 알 수 있는 가장 좋은 방법은 예전에 진행했던(지금은 매년 시행이 중단되었지만) RSA 소수 분해 숙제가 풀렸는지 확인하는 것이다. 오래전에 중단되어 상금은 없어졌지만, 그 문제는 흔히 회자되는 양자 컴퓨터의 성능 경쟁에서 역사적으로 가장 기사 쓰기 좋은 challenge라고 볼 수 있다. 분해해야할 큰 숫자는 공개되어 있지만, 실제 분해되어 곱해지는 소수값은 초기 그것을 만들었을때 파기해 버려 실제 정답은 아무도 모르는 숫자이기 때문이다. 개인적으로는 상당히 기대되는 기사 발표다.

https://en.wikipedia.org/wiki/RSA_Factoring_Challenge

양자 컴퓨터가 할 수 있는 연산은 현재 피터 쇼어의 소인수분해 알고리즘이 대표적이기 때문에 이를 통하는게 가장 좋은 것이다. 별도로 IBM은 자사의 양자 컴퓨터를 사용해 연산할 수 있는 클라우드 API를 제공하고 있지만(15 qubit) 아직까지 이를 통해 역시 위 RSA문제를 풀었다고 알려진 사례는 없으므로 유의미하게 제공하고 있는지는 의문이다. 물론 D-Wave에서 다루어지고 있다는 optimization문제에 최적화된 양자 컴퓨터 같은 것들에게는 좀 유효하지 않을 수는 있다.(그녀석들은 쇼어 알고리즘을 수행하는 형태의 양자컴퓨터가 아닌 것으로 알려져 있다)

https://developer.ibm.com/dwblog/2017/quantum-computing-api-sdk-david-lubensky/

혹시 실제 이 수가 어떤 것인지 궁금해하시는 분이 있을것 같아 간단히 남겨둔다.

과연 아래 수를 수시간안에 소인수 분해할 수 있는 컴퓨터는 언제 등장할 수 있을까? (지금 일반 컴퓨터로는 아마 엄두도 나지 않는 계산일것이다)

RSA challenge :

RSA-1024 = 13506641086599522334960321627880596993888147560566702752448514385152651060485953383394028715057190944179820728216447155137368041970396419174304649658927425623934102086438320211037295872576235850964311056407350150818751067694629205563685529475213500852879416377328533906109750544334999811150056977236890927563

RSA-2048 = 25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357

왜 정보엔지니어가 소수에 관심이 있을까?

소수는 수에서의 최소 단위 역할을 한다. 즉, 모든 수는 소수의 곱으로 유일하게 나타내어질 수 있다. 바꾸어 말하면 수는 소수에 의해 인코딩되고 디코딩되어 질 수 있다. 이것은 진법과 무관하고 수 자체의 바뀌지 않은 성질이다.

수학자들이 수학을 신봉하는 이유는 다양하지만, 그것이 순수학문으로서 우주를 기술할 수 있다는 사실과 그리고 마음껏 확장해서 사용할 수 있다는 점에서 우주를 능가한다는 사실이다. 명실공히 공학이건 학문이건 논리적인 정량적인 기술을 위해서는 수학은 피할 수가 없는데,

소수는 특히나 이 숫자의 원자같은 역할을 종종하게 된다.

그리고 이 블로그에서 다루는 큰 주제인 양자 컴퓨터의 제1 응용분야로 지적되는 것이 바로 소수분해를 고속화 한다는 점과도 상통된다. 또한 양자암호에서 다루는 암호의 가장 큰 경쟁자가 바로 이 소수분해를 활용한 RSA라는 점도 연결되어 있다.

이쯤에서 책을 한권 소개해보자(아래 링크의 판매자와는 무관하다)

http://www.yes24.com/Product/Goods/2498234

소수의 역사를 이해하기 위해서 일반인에게 가장 잘 설명하는 책 중에 하나라고 생각한다.

오늘은 소개만 시작하고 차근차근 이 책의 내용들을 중심으로 소수에 대해 알아보자 

 지난 번에는 양자 컴퓨터라는 것이 사실은 이런 작은 입자를 이리 저리 관측하지 않으며(결잃음을 방지하며) 변화시키다가 마지막에 관측하여 확정시키는 기계라는 사실을 설명했다. (예컨데 기술이 허락하는 범위에 따라 여러개의 입자를 얽히게 만들고 위상을 바꾸고 원격전송하고 등 원하는 대로 그 변화과정을 일반 컴퓨터의 논리 게이트처럼 구성한 다음에 마지막에 관측하여 실제 값을 측정하면 된다. 그리고 결을 잃지 않을 수 있다면, 사실 전자이건 광자이건 분자이건 양자 컴퓨터의 기본 큐빗으로서 역할을 할 수 있다. 따라서 다양한 H/W 방식이 존재할 수 있다. 초저온이 아니라 상온을 이야기하는 것도 그 때문이다. 예를들면 어지간해서 관측당하지 않는 빛은 상온에서도 회절무늬를 생산하긴 한다.)

그런데 왜 이것이 고속계산을 가능하게 하는가?

 이에 대해 다양한 설명이 이루어지는데 TED 강의나 여러가지를 보면 모든 경우의 수를 한꺼번에 탐색한다던가 하는 설명을 한다. 이 설명은 일부는 맞기도 하고 어떤 면에서 오해를 불러일으킬 수 있기도 하는데, 왜냐하면 관측시 그 모든 탐색의 경우의 수에도 불구하고 관측 결과는 하나일 뿐이기 때문이다. 결 잃기전 중첩이 되어있다고는 하지만 결국 관측하면 하나로 확정된다.

 그러나 다행히도(?) 이때 그 관측은 가장 높은 확률의 것이 나타나겠다. 매우 낮은 확률의 일은 잘 발생하지 않기 때문이다. 여기에 양자 컴퓨터의 가치가 존재한다.

 잠깐, 글만 난무하는 이 설명에 빛을 밝혀줄, 본인이 최근에 찾은 짧은 설명 영상을 보자 (영문, 4분부터 7분 30초까지)

https://www.youtube.com/watch?v=PzL-oXxNGVM

 이는 전산을 전공하는 사람이라면 기억할 몬테카를로 시뮬레이션 방법과 어떤 면에서 비슷하다. 어떤 복잡한 구조에서의 계산이 어려우면, 해당 구조를 만들어 놓고 실제 입력을 주었을때 여러번 반복해서 실제 분포를 알아내면 된다. 즉 실제로 몇번 돌려봐가면서 계산하기 어려운 문제의 답을 찾는 것이다.

 자 그러면 어떻게 구성을 해서 관측을 했을때 이 측정값으로 연산을 빠르게 할 수 있는가? 가장 유명한 알고리즘 두 개는 위 영상에서도 언급된 수학자 피터 쇼어의 알고리즘(Peter W. Shor, 1994)과 로브 그로버의 검색 알고리즘(Lov Kumar Grover, 1996)이다. 쇼어의 알고리즘은 큰 수를 소수로 곱으로 나누는데 응용될 수 있고, 그로버의 알고리즘은 정렬 안되어 있는 데이터를 찾는 알고리즘이다. 이 알고리즘에 대한 설명을 여기에서 하지 못하는 것은 아쉽지만(워낙 전문분야이다보니 그 설명을 쉽게 해놓은 자료는 없다는 것이 변명이다.), 이렇게 간접 설명해 볼 수 있다.

 예컨데 검색 알고리즘을 예를 들어 보면, 어떤 입자의 구성에 의해서 관측을 해서 그 찾은 데이터를 실제 확인해보면 정답을 찾았는지 아닌지 알 수 있다. 사실은 이렇게 맨 처음 찾지는 못했을 테고, 곧바로 다음번 관측을 다시해서, 또다른 탐색 시도를 하면 된다. 즉 이런 관측이 이 데이터의 탐색을 확률적으로 높게 유도할 수만 있다고 해도, 이 검색은 하는 수 없이 해야하는, 처음부터 검색해나가는 것보다 훨씬 더 빠르게 진행된다.

 그리고 만약에 이런 과정에서 계속 이 입자의 구성을 바꿔서 더 확률을 높일 수 있다고 한다면, 계산을 좀더 가속화 할 수 있을것이다. (간단한 설명에서는 이렇게들 표현한다. 참고로 수학자인 쇼어는 양자 알고리즘 불모지인 상태에서 이 알고리즘 고안에 꼬박 1년이 걸렸는데, 본인의 정규 작업이 아니었다고 한다. 어딜가나 이런 잉여의 승리가 존재한다. 이분은 이렇게 양자컴퓨터 역사에 영원히 이름을 남겼다.)

 아래가 쇼어의 알고리즘과 일반 컴퓨터의 d의 자리수를 소수로 분해하는 계산에 필요한 연산수 이다. 뒤로 갈수록 연산 절약은 어마어마하다. 그렇다 이 알고리즘은 어떤 연산을 함에 있어서 확률적으로 정답에 가깝게 무언가를 알려준다. 더럽게 운이 없으면 엄청 오래 걸리겠지만 확률적으로 더 먼저 찾는다. 자연이라는 엄청난 연산기를 해킹해서 특수 목적에 쓰는 모습이라고 상상해본다.

 그러면 아예 좀더 범용적인 알고리즘을 찾아보면 어떨까? 이런 특수한것말고 아예 근본적으로 모든 튜링 머신을 대체할만한 기적의 IBM PC 호환 양자 컴퓨터를! 그러나 불행히도 그런 범용적인 알고리즘은 아직 없다. 분야별로 양자 역학 현상을 이용해 연산을 빠르게 하는 방법을 많은 이들이 찾고 있으나 아직은 좀 시간이 걸리는 형상이다.

 최근에 뉴스에서 IBM에서 5 qubits의 양자 컴퓨터 연산을 할 수 있는 클라우드 환경을 제공한다고 하는데, 위 처럼 몇가지 구성을 해서 관측 값을 얻을 수 있는 API를 제공한다고 볼 수 있겠다. 다르게 말하면, 어떤 알고리즘을 통해 이 큐빗의 관측 값을 가지고 계산을 고속화 할지는 내 몫인 셈이다. 만약에 양자 컴퓨터가 더 기술적으로 보편화되면 이러한 코딩에 대한 전문가가 필요한 시대가 올지 모르겠다. 고전컴퓨터에서 양자 컴퓨터를 호출해 지속 상호작용하면서 무언가 빠른 답을 내는 형태의 알고리즘을 분야별로 구현하는 작업이 필요하니까.

 이제 좀더 현실적인 이야기를 해보자. 그러면 지금 양자 컴퓨터는 존재하는가? 미국 NSA가 이미 만들어놓고 숨기고 있는 것인가?

 맨 먼저 앞서 언급했던 결 잃음(decoherence) 방지의 어려움에 대한 이해가 필요하다. 양자컴퓨터의 qubit과 연계한 입자는 우주의 어떤 것과도 상호작용하면 결을 잃게 된다. 따라서 절대 0도에 가까운 온도에, 광자도 없는 어둠 속에 격리될 필요가 있다. 그런데 또 그러다가 필요할때는 관측해서 전송해야 한다. 이 말은, 무언가 열을 가진 장비가 옆에 필요하다는 말이다. 끊임없이 주변과 통신하면서 결을 잃지 말아야하는 이런 특성 때문에, 실제 시작후 작동 가능 시간은 매우 순간적(0.0001초?) 이라고 한다. 차갑게 식히고 뭔가 시작해서 관측하면 아마 다시 온도를 내려야 하는 형태일것 같다.

 만약에 이렇게 성공해서 동시에 다룰 수 있는 각각의 입자 수가 50 qubits이 되면 기존 고전 컴퓨터로 거의 계산 불가능한 것들을 달성하기 시작하는데, 불행히도 지금은 이 한 qubit이 제대로 작동하는 것을 보정하기 위해서 실제로는 수많은 qubit이 필요하다고 한다(에러 보정용). 많은 회사들이 투자해서 다양한 방식으로 격리하고(광자를 이용하거나 전자를 이용하거나 또다른 무언가를 사용하는) 개선하고 있지만 아직은 없는 것도 있게 보이게 하는 마케팅의 힘이 더 우세한 모양새이다.

 이 즈음에서 구글에서 최근 배포한 영상을 보자. 후반부에는 양자 컴퓨터의 실물을 자세히 구경할 수 있다.

https://www.youtube.com/watch?v=k-21vRCC0RM

언급된 여러가지 어려움에도 불구하고, 희망적으로 보는 이들은 1988년도 국내 슈퍼컴퓨터의 성능(크레이-2S : 2 GFlops) 이 현재 애플 워치(3 GFlops)만도 못했다는 것을 상기시키고 싶어한다. GTX 1050 Ti 그래픽 카드의 연산능력은 2,100 GFlops이다. 지금으로부터 30년후에 양자 컴퓨터에 기술적으로 어떤 아이디어들이 보태어질지는 아무도 모른다.

 그리고 최근에 자주 인용되는 양자 컴퓨터인 D-wave는 optimization에 특화된(global minumum을 찾는) 양자 컴퓨터로 양자와 관련된 현상을 이용하지만 일반적으로 기술되는 양자 연산 알고리즘(예컨데 쇼어 알고리즘)을 구현하기는 어려운 것으로 언급되고 있다. 따라서 실제로 온전히 사용하는 qubit이 몇개인 것인지, 그리고 어떠한 곳에 응용이 가능한 양자 컴퓨터인지를 잘 구별해야만, 앞으로 나올 양자 컴퓨터에 대한 기사들의 옥석을 가려낼 수 있다. 당장은 200 qubits정도의 쇼어 알고리즘을 구현할 수 있는 양자 컴퓨터가 상용화되면, 일단 과거의 공인인증서들은 차례차례 뚫리는 상황이니 이를 기준으로 삼으면 어떨까 싶다. (그런데 그 200 qubits이 실제로는 거의 다 에러를 보정하기위한 qubits이면 역시 난감해지겠다)

 아직까지는 양자 컴퓨터는 희망과 냉소가 난무하는 분야라고 볼 수 있다. 냉소를 따라가다보면 양자 컴퓨터는 현실적이지 못하다고 주장하는 이론가들도 꽤 있다(결 잃음 관리가 어렵다는 얘기겠다). 따라서 당장 수년은 좀더 두고봐야한다. 얼마동안은 그것은 특수 냉각장치와 함께하는 커다란 것일 소지가 높고 대부분 기업들을 위한 것일테고 상용화되어도 팔러 오기 보다는 클라우드 형태로 제공되게 된다.

 또한 많은 일반인 들이 오해하듯이 우리가 가지고 있는 PC를 대치하여 특수한 OS를 설치해 집에 놓아야 하는 존재는 더 당분간 아니겠다.

여기까지 보았다면 마지막으로 아래 비디오로 검증해보자. (영문) 

https://www.youtube.com/watch?v=JhHMJCUmq28