양자 컴퓨터와 블록체인 보안 이야기. 큐비트를 이용한 양자 정보 처리

양자 컴퓨터와 블록체인 보안 이야기. 큐비트를 이용한 양자 정보 처리

큐비트를 이용한 양자 정보 처리에서는 양자 정보의 기본 단위인 큐비트를 이용한 양자 정보 처리에 대하여 다뤄보겠습니다.

큐비트! 양자 정보의 기본 단위

양자(quantum)의 어두에 고전 정보의 기본 단위인 비트(bit)를 결합하여 탄생한 단어 큐비트(qubit)는 양자 정보의 기본 단위입니다. 0 아니면 1 둘 중 하나로만 이루어진 비트와 달리 큐비트는 적절한 양자역학적 계를 채택하여 0과 1을 동시에 가질 수 있는 새로운 정보 단위를 이용합니다. 큐비트의 정보는 수학적으로는 복소수에 대한 2차원 벡터 공간인 2단계 양자역학계 안의 상태로 기술되는데요. 어려운 말만 가득하지요? 말보다는 공간 기하로 설명하는 편이 이해가 빠르답니다.

가능한 모든 사건이 일어나는 경우를 확률적으로 표현한 블로흐 구에서 구의 표면은 두 가지 결과에 대한 확률값의 합이 1인 점들로 이루어져 있습니다. 고전적인 비트는 구의 '북극'과 '남극'에 해당하는 1과 0 값만 지닐 수 있는데 반하여 큐비트는 구의 어느 곳에도 동시에 존재할 수 있답니다. 그동안 설명해왔던 양자 중첩과 얽힘을 제대로 이해하셨다면 북극과 남극을 제외한 나머지 표면에서는 1과 0 두 가지 사건에 대한 확률이 공존한다는 것을 짐작하셨을 겁니다.

이처럼 큐비트는 0과 1을 동시에 가질 수 있음을 이용하여 연산 과정에서 마치 0인 경우와 1인 경우를 동시에 훑어가는 효과를 줄 수 있는 것이지요. 이를 이용하면 현재의 슈퍼 컴퓨터도 엄두를 내지 못하는 문제를 쉽게 풀 수 있습니다. 큰 수의 소인수 분해가 매우 어렵다는 사실을 기반으로 한 공개키 암호 방식마저 말입니다. 이에 관해서는 지난 시간에 잠깐 언급했었죠?

단 한 번의 연산으로 평균값을 찾아낸다!

단, 여기서 주의할 점이 있습니다. 수 천만 가지 경우의 연산을 통해 평균값을 알아내려는 경우 양자 병렬성을 지닌 큐비트를 이용하면 단 한 번의 연산으로 평균값을 바로 찾아낼 수 있다는 의미일 뿐, 수 천만 가지 각각의 개별 연산 값을 한 번에 찾는다는 의미가 아니라는 것을 명심해야 합니다. 이 점을 이해하기 위해서는 확률 계산과 양자 계산의 차이를 비교해볼 필요가 있습니다.

예를 들어, n개의 상자가 있고 n개의 상자 중에서 단 하나의 상자에 공이 들어있는 경우를 생각합시다. 고전적인 방법으로 공이 들어있는 상자를 찾기 위해서는 n번의 상자를 열어야만 하겠죠. 한편, 양자 병렬성을 이용하면 상자를 단 한 번만 열어보면 된답니다. 가령, 열어볼 상자의 번호를 적어서 그 번호에 해당하는 상자를 골라서 열어볼 수 있는 것이지요. 다만, 여는 동작 이전에 가능한 n개의 번호들을 양자 중첩/얽힘 상태로 만들어야 하는 번거로움이 있습니다.

하지만 이런 일은 꼭 양자 알고리즘을 이용하지 않고도 확률 알고리즘을 통해 비슷하게 수행할 수 있는데요. 동전을 n번 던져서 상자의 번호를 모두 결정한 뒤에, 결정된 번호의 상자를 여는 방식입니다. 각 번호의 상자를 여는 행위가 확률적으로 중첩되어 있고, 각각의 상자에 대해서 그 상자를 열고 공을 발견할 확률이 0보다 크니까 별 차이가 없다고 생각할 수 있죠. 그러나 이렇게 할 경우 상자의 개수가 많아지면 상자를 열어서 공을 발견할 확률도 기하급수적으로 작아지기 때문에 사실상 못 찾는다고 봐야합니다.

정확히 같은 반박을 양자 컴퓨터에 대해서도 적용할 수 있는데요. 확률 알고리즘도 가능한 모든 상태의 확률적 중첩을 만들어낼 수 있지만 그렇게 하면 각각의 상태가 갖는 확률이 기하급수적으로 작아져서 의미 없는 알고리즘이 되듯이, 양자 알고리즘 또한 가능한 모든 상태의 큐비트를 만들어낼 수 있지만 그렇게 하면 각각의 상태가 갖는 확률 진폭이 기하급수적으로 작아져서 의미 없는 알고리즘이 되어버립니다. 애초에 그만큼의 양자 중첩/얽힘 상태의 큐비트를 기술적으로 구현하는 것은 먼 미래의 일이긴 하지만요.

양자 컴퓨터는 오답을 상쇄시키고 정답을 증폭시킬 수 있다.

양자 알고리즘과 확률 알고리즘의 가장 근본적인 차이점을 단적으로 말해보겠습니다. 확률은 절대 음수일 수 없지만 양자역학의 확률 진폭은 음수일 수 있을 뿐만 아니라, 심지어 실수가 아닌 복소수일 수도 있습니다. 양수끼리는 상쇄될 수 없지만 양수와 음수는 상쇄될 수 있죠. 거기다 확률 진폭의 절대값의 제곱이 확률이 되는데 확률의 총합은 1로 보존되어야 하므로 어떤 상태의 진폭이 상쇄되어 0이 된다면, 무엇인가 다른 상태의 진폭은 총합이 보존되기 때문에 커져야만 합니다.

위 예시 속 상자 문제에 대하여 상자를 양자적으로 열어 보면 공이 어느 상자에 있는지를 유의미한 확률로 맞힐 수 있습니다. 물론 고전적인 결과에 비하면 엄청난 개선이지만, 여전히 지수적인 속도 향상이 아니라 다항식적인 속도 향상에 불과한 것인데요. 이처럼 풀어야 할 문제 자체에 규칙성이 별로 없는 경우 정답의 확률 진폭을 최대화시키고, 오답의 확률 진폭을 최소화시키는 작업이 필요하므로 이런 문제에 대해서는 양자 컴퓨터가 기술적으로 비효율적이라고 할 수 있습니다.

그러나 풀어야 할 문제 자체에 규칙성이 존재하여 상쇄를 가능하게 하는 좋은 구조들이 있는 경우 이야기가 달라집니다. 큰 수의 소인수 분해가 대표적인 것으로, 이 경우 양자 알고리즘을 이용하면 고전적으로 알려진 최선의 알고리즘보다 지수적인 속도 향상이 있습니다. 따라서 높은 기술적인 비용이 소모되는 양자 컴퓨터가 모든 면에서 무조건 만능이 아니라 지수적인 속도 향상을 기대할 수 있는 부분에서 활약할 수 있음을 알고 가시면 좋겠습니다.

양자 컴퓨터가 적은 수의 큐비트로도 많은 경우의 수를 표현할 수 있을 뿐 아니라 큐비트의 행동 자체가 비결정론적이라 여러 가지 결과에 대한 값을 한 번에 얻어낼 수 있음을 이해하셨나요? 또한 양자를 확률 파동함수로 표현했을 때 상반되는 상태가 상쇄되어 오답을 재빨리 제거할 수 있는 점도 빼놓을 수 없겠습니다. 그러나 이렇듯 풀어야 할 문제에 상반되는 상태를 상쇄할 수 있는 규칙성이 존재하여 지수적인 속도 향상을 기대할 수 없다면 기술적인 비용 소모가 큰 양자 컴퓨터에 대해 일면 회의적인 생각을 하실 수도 있겠습니다.

그러나 양자 컴퓨터의 빠름은 우리가 컴퓨터에 기대하는 빠름과는 그 적용분야나 성격에 큰 차이가 있음을 받아들인다면 양자 컴퓨터에 대한 이해도가 한층 더 올라가실 것입니다. 특정 연산에서 기존 컴퓨터와 속도 차이가 별로 없거나 부족한 결과를 보여주었다고 양자 컴퓨터에 실망할 필요는 없는 셈이지요. 따라서 양자 컴퓨터가 개발되더라도 당장 우리가 사용하고 있는 일반 컴퓨터가 모두 무용지물이 되는 것이 아니라 각자의 기술적 효율성이 극대화되는 면에서 서로 돕고 경쟁하는 관계로 출발하리라 예상합니다.