양자가 깨트린 고전, 컴퓨터

최근 빅테크들이 양자컴퓨터 플랫폼을 오픈하면서, 양자컴퓨터의 상용화 가능성·시점이 이슈이다. 2019년 구글이 양자우월성을 달성한 후 5년도 채 되지 않은 시점의 성과로, 양자우월성(quantum supremacy)는 양자컴퓨터가 기존의 슈퍼컴퓨터의 성능을 능가한는 가설이다. 하지만 여전히 상용화까지는 5~30년이라는 큰 범위 내에서 견해차가 크다. 2025년 2월 마이크로소프트(MS )에서 기존 주류와 다른 위상초전도체를 사용한 마요라나1을 개발하면서, 상용화 시점이 빨라질 거라는 기대가 높아졌다.

 

암호화 기술을 기반하는 가상화폐와 양자컴퓨터는 비슷한 구석이 많게 느껴지는데, 일단 현 시점에서 가상화폐·양자컴퓨터는 각각 방패·창의 입장에서 기술발전을 꾀하고 있다. 양자컴퓨터가 지닌 암호해독력이 가상화폐의 암호화를 무력화할 가능성이 남아 있기 때문이다. 물론 남은 시간 동안 가상화폐도 암호해독을 방어할 다양한 대책을 강구하고 있다. 암튼 공상과학처럼 다가오는 두 분야의 기술은 실용가치에 비해 과도한 평가가치(밸류에이션)을 부여받고 있는데, 시장이 옳다고 믿는 사람들은 꾸준한 관심·공부가 필요하다.

 

한계가 명확한, 고전컴퓨터

 

양자컴퓨터는 기존 고전컴퓨터(슈퍼컴퓨터 포함)과 전혀 다른 특징을 가지고 있다. 우선 고전컴퓨터는 트랜지스터를 이용한 비트(bit)를 최소연산단위로 사용하는데, 0과 1을 표현하기 위해 전기흐름을 활용한다. 전기가 통하면 도체상태이고, 전기가 통하지 않으면 부도체상태이다. 반도체가 트랜지스터 회로의 중간부품의 사용된 이유는 전기흐름에 따라 도체·부도체 상태의 변환이 가능했기 때문이다.

 

최근까지 반도체산업은 칩에 집적할 수 있는 트랜지스터의 수를 증가시키는 방향으로 발전해왔는데, 1948년 벨연구소에서 발명된 트랜지스터는 PN(Positive-Negative)접합으로 구성되며, 3개의 단자(이미터·베이스·콜렉터)를 가진다. 트랜지스터의 기능은 증폭기·스위치이다. 증폭기로서의 기능은 전기신호를 증폭시켜 작은 전류로 큰 전류를 제어할 수 있고, 스위치로서의 기능은 전류흐름은 on/off 할 수 있다. 초기 트랜지스터는 게르마늄으로 만들었지만, 오늘날 더 높은 온도에서도 안정적인 실리콘으로 만든다.

 

기술발전으로 트랜지스터의 크기가 원자 규모에 가깝게 작아지면서 문제가 발생했다. 양자역학에 의해 트랜지스터 내 전자가 다른 곳으로 누설되는 양자터널링이 발생한 것이다. 그 외에도 하나의 칩에 과도하게 많은 트랜지스터가 집적되면서 생긴 발열, 레이저의 빛파장의 영향으로 정확한 식각이 불가능한 회절한계 문제를 겪어왔다. 양자터널링(quantum tunneling)은 낮은 에너지를 가진 입자가 에너지 장벽을 통과하는 현상으로, 고전물리학으로는 설명이 되지 않는다. 고전물리학에서는 입자가 에너지장벽을 통과(터널링)하기 위해서는 장벽높이보다 높은 에너지를 가져야 한다고 설명한다.

 

터널다이오드(Tunnel Diode)는 매우 높은 도핑(doping) 농도를 사용하여 양자터널링을 활용하는 전자소자로, 이는 전자가 PN접합을 통해 터널링하면서 독특한 전류·전압 특성을 가지는 전기소자를 형성한다. 태양 중심에서는 양성자들이 원자핵의 장벽을 터널링하면서 핵융합 반응을 일으키고, 그 결과로 에너지를 방출한다. 방사성원소의 핵붕괴에서도 알파입자가 원자핵의 장벽을 터널링을 통해 방출된다.

 

파인만에서 시작된, 양자컴퓨터

 

먼 훗날 알게 되는 천재들의 창의력·통찰력은 경이롭다. 1981년 리처드 파인만은 미국 MIT에서 개최된 물리학 컨퍼런스에서 양자얽힘의 메커니즘을 알고리즘으로 이용할 수 있다는 내용의 발표를 하였고, 이를 근거로 1994년 피터 쇼어가 쇼어알고리즘을 개발했다. 쇼어알고리즘(Shor's algorithm)은 트랜지스터로는 한계가 있는 소인수분해를 하는 최초의 큐비트 알고리즘이었다.

 

소인수분해(Prime/Integer factorization)는 합성수를 소인수들의 곱으로 나타낸 것을 의미하는데, 학창시절 수학시간에 소수와 함께 명칭이 어렵게 다가왔었다. 素(소, 근본·본디·희다·비다)는 갓 뽑아낸 실을 매달아 놓은 것으로, 색·무늬·장식이 없다. 암호학의 핵심이 소인수분해이다. 큐비트 개수가 증가하면 암호화폐를 해킹할 수도 있다는 가설이 있는데, 이는 소인수분해를 통해 RSA(공개키 암호화 방식)에서의 상대방 키를 찾을 수 있다는 생각에서 나왔다.

 

1977년 3명의 연구자(Rivest·Shamir·Adleman)가 개발한 RSA(공개키 암호화)는 강한 보안성을 지니는데, 이는 소인수분해의 난수성에 기반한다. N값을 알더라도, 매우 큰 소수 2개를 찾는 작업은 고전컴퓨터로는 천문학적인 시간이 요구된다. 이러한 이유로 RSA는 지금까지도 암호화폐, 데이터암호화, 전자서명, SSL/TLS 등에 널리 사용되고 있다. RSA는 다음 2개의 키쌍을 생성·이용하여 데이터를 암호화·복호화하는 방식으로, 공개키가 유출되어도 개인키를 사용하지 못하면 데이터 복화화가 어렵다.

공개키(public key) : 데이터 암호화에 사용
개인키(private key, 비밀키) : 암호화된 데이터를 복호화에 사용

 

고딩의 추억, 시간복잡도

 

다항시간(Polynomial Time)은 알고리즘의 문제해결시간이 입력값(N)의 다항식함수로 표현될 수 있는 경우를 의미하는데, 알고리즘 복잡도 이론에서 중요한 개념이다. 시간복잡도(Time Complexity)는 컴퓨터프로그램의 N값과 연산수행시간의 상관관계를 나타내는 척도로, 다음의 형태에서 아래로 갈수록 N값이 커지면 알고리즘 수행시간이 급증한다.

 

상수(constant)
로그(logarithmic)
선형(linear)
선형로그(linear-logarithmic)
다항(polynomial, 다차)
지수(exponential)
팩토리얼(factorial)

시간복잡도 그래프 [ⓒSave My Exams]

 

시간복잡도 수치가 작을수록 효율적인 알고리즘임이다. 전체 수행시간에 영향을 크게 미치지 않는 상수부분은 무시할 수 있고, 더 나아가 주어진 함수에서 가장 빠르게 증가하는 항을 제외한 나머지를 버리는 대문자O표기법(Big-O Notation)이 사용되고 있다. 

 

양자컴퓨터의 주특기, NP문제

 

21세기 들어 D-Wave 등에서 실험적인 양자컴퓨터가 개발되어 오다가, 2019년 양자컴퓨터의 소인수분해 계산속도가 슈퍼컴퓨터를 능가하게 되었다. 양자컴퓨터는 중첩현상에 기반한 큐비트(qubit, 양자비트)가 사용되며, 0과 1이 확률적으로 존재하면서 측정하는 순간에 한 상태로 확정된다. 물론 큐비트들이 얽힘상태를 유지하고 있어야 한다. 다시 말해 양자컴퓨터는 중첩상태의 큐비트로 인해 확률적 특성을 가지며, 고전컴퓨터에서의 결과값이 나올 가능성이 높은 큐비트 조합을 도출해낸다. 이전 글 <양자와 외계인이 말하는, 영혼>에서는 양자역학에 근거하여 의식에 대해 언급했었다.

양자의 중첩과 얽힘을 표현한 그래픽

양자적 알고리즘은 연산속도·처리용량을 기하급수적으로 향상시킬 수 있는데, 고전컴퓨터에 무어(Moore)의 법칙이 있다면, 양자컴퓨터에는 네븐(Neven)의 법칙이 있다. 2019년 하르트무트 네븐(구글양자AI연구소 책임자)는 양자컴퓨터의 계산능력이 이중지수함수적으로 성장한다는 원리를 주장했다.

 

고전컴퓨터는 입력값에 따라 출력값이 선형적으로 정확하게 결정되는 P문제에 적합하며, P(Polynomial) 문제는 다항시간 내에 주어진 문제 자체를 해결(답)할 수 있는 알고리즘이 존재하는 문제이다. NP(Non-deterministic Polynomial, 비결정적 다항) 문제는 여러 가능성들을 고려해야 하는 비결정적 병렬연산으로, 이는 주어진 하나의 정답에 대하여 검산시간이 다항시간만큼 걸리는 문제이다. NP문제는 N이 증가할수록 문제해결시간은 기하급수적으로 증가하지만, 특정한 정답이 참·거짓 여부를 판별하는데 걸리는 시간은 산술적으로 증가한다.

 

P문제(답 도출) : 결정론적 튜링기계 사용

NP문제(검산) : 비결정론적 튜링기계 사용

 

다항시간 내에 문제를 해결할 수는 있다는 부분이 헷갈릴 수 있지만, 비결정적 튜링기계는 답 자체를 찾기보다는 주어진 답을 검증(검산)하는 역할을 한다. 결정론적 튜링기계는 정해진 명령표에 따라 원하는 작업을 정확히 수행하는 가상의 기계로, 한 순간에 한 가지 상태만을 가지면서 입력에 대해 항상 같은 결과를 도출한다. 비결정론적 튜링기계는 한 순간에 여러 상태를 가질 수 있어, 병렬처리로 NP문제를 다룰 수 있다. 비결정론적 튜링기계는 이론적 모델인 반면, 양자컴퓨터는 실제로 구현된 시스템이다. 양자컴퓨터는 출력값의 형태가 확률·비결정적으로 도출되기 때문에 결정론적 문제에는 적합하지 않은 대신, NP문제의 해결에 적합하다.

 

고전컴퓨터는 폰 노이만 구조에 기반하고 있는데, 튜링기계의 개념을 활용하여 설계되었다. 1936년 앨런 튜링은 계산의 기본개념으 설명하기 위해 가상의 튜링기계(Turing Machine)를 제시했는데, 이 기계는 무한한 테이프와 읽기·쓰기 헤드로 구성되어 있다. 특정 규칙에 따라 테이프의 기호를 읽고 쓰는 방식으로 작동한다. 고전컴퓨터는 비트값을 얻기 위해 각 자리마다 전기신호를 보내면서 연산을 수행해야 하는데, 인간 입장에서는 노가다가 따로 없다. 다만 그 컴퓨팅 속도가 너무 빠르다보니, 인간의 입장에서도 빠르다고 느껴지는 것일 뿐이다.

 

확률적 특성은 불확실성·오류율이 상대적으로 높을 수 있음에도 불구하고, 양자컴퓨터가 필요한 이유는 특정문제(주로 NP문제)에 대한 연산속도에 있다. 양자컴퓨터는 비결정론적 튜링기계의 이론적 병렬성을 실제로 구현하게 될 것이며, 이는 특정문제에 최적화된 알고리즘을 갖추게 된다. 얽혀있는 큐비트 수가 많을수록, 양자컴퓨터의 연산속도는 고전컴퓨터와 비교할 수 없이 빨라진다.

 

하나의 큐비트만 상태를 바꿔도 그 큐비트와 얽혀있는(강한 상호작용을 하는) 다른 큐비트의 상태도 결정되며, 이러한 특성을 바탕으로 목적에 맞게 큐비트를 얽혀 놓으면, 짧은 시간에 많은 양의 정보처리가 가능하다. 중첩상태의 큐비트를 이용하여 동시에(거의 시간차 없이) 여러 숫자(상태)를 표현하게 된다. 일반인의 입장에서는 이해조차 어려운 양자컴퓨터가 미래의 여러 분야(암호화·최적화·시뮬레이션·의약 등)에 획기적인 변화를 가져다 주다니 지켜볼 일이다.