2. 양자 알고리즘

이번 페이지는, 양자 컴퓨팅의 핵심이라고 할 수 있는 양자 알고리즘에 대해서 알아보겠습니다. 내용이 많고 복잡할 수 있지만, 최대한 간단하고 이해하기 쉽게 설명하기 위해 노력해보겠습니다.

우선 알고리즘이란, 특정한 문제를 해결하기 위한 절차를 말합니다. 컴퓨터는 주어진 문제를 해결하기 위해서, 정해진 절차를 따라가며 계산을 합니다. 여기서 문제는 어떤 것이든 될 수 있습니다.

양자 알고리즘에 대해서 보기 전에, 고전 컴퓨터의 알고리즘에 대해서 먼저 알아보도록 하겠습니다.

아주 간단한 문제를 하나 볼까요? 0부터 7까지의 정수 중에서 무작위하게 하나를 고르고, 컴퓨터에게 고른 숫자가 무엇인지 맞춰보라는 문제를 내봅시다. 고전 컴퓨터로는 이 문제를 어떻게 접근할 수 있을까요?

아쉽게도 숫자의 범위 말고는 주어진 힌트가 하나도 없으므로, 그냥 때려맞추는 방법 밖에 없습니다.

예를 들어 정답 숫자가 3이라고 해봅시다. 첫번째 시도에서는 숫자 1을 나타내는 비트 001을 넣어보겠습니다. 버튼을 눌러서 직접 확인해보세요!

그러면 문제 기계가 들어온 입력 비트를 관측하고, 정답과 비교합니다. 정답은 3인데 1로 관측되었으니 틀렸다고 하겠죠?

두번째 시도입니다. 두번째 시도에서는 숫자 5을 나타내는 비트 101을 넣어보겠습니다.

역시 틀렸다고 나옵니다.

세번째 시도입니다. 이번에는 숫자 3을 나타내는 비트 011을 넣어보겠습니다.

그러면 들어온 비트를 관측하고, 정답과 일치하니 맞았다고 해줍니다. 세번째 시도만에 맞췄네요!

고전 컴퓨터는 이 문제를 이런 방식으로 접근하는 것이 최선입니다. 아무런 정보가 없는 상태에서 랜덤한 숫자를 맞추라고 하니 그냥 하나씩 넣어보는 방법 밖에는 없는 것입니다. 각 시도에서 정답을 맞출 확률은 1/8 이겠죠.

그나마 아까 보여드린 예시에서는 세번째 시도만에 맞추었지만, 운이 정말 안좋다면 7번만에 맞추었을 수도 있습니다. 숫자의 범위가 커지면 커질수록 각 시도에서 정답을 맞출 확률은 줄어듭니다. 만약 숫자의 범위가 1 부터 1,000,000이었다면? 로또를 사는 것이 차라리 나아보입니다.

자, 그럼 이제 양자 컴퓨터의 경우를 보도록 하겠습니다. 양자 컴퓨터는 입력으로 고전적인 비트 대신 큐비트를 넣습니다. 양자 컴퓨터는 이 문제를 어떻게 해결할까요? 과연 고전 컴퓨터보다 효율적으로 해결할 수 있을까요?

양자 컴퓨터의 효율성에 대해서는 오해가 많습니다. 가령, "큐비트는 모든 상태가 중첩되어 있기 때문에 가능한 상태를 모두 병렬적으로 동시에 확인해볼 수 있다" 라고 생각하시는 경우가 있습니다. 이 말이 맞다면, 양자 컴퓨터는 숫자 맞추기 문제를 항상 첫번째 시도만에 해결할 수 있을 것입니다. 0부터 7까지 중첩된 상태를 넣으면 그 중 하나는 정답일테니까요!

...하지만 불행하게도 이는 사실이 아닙니다. 한 번 직접 넣어보도록 하겠습니다.

버튼을 눌러서 모든 상태가 같은 확률로 중첩되어있는 상태의 큐비트를 넣어보세요. 그러면 문제 기계 내부에서 입력을 정답과 비교하기 위해서 "관측"을 합니다. 바로 이 관측 단계에서 문제가 발생합니다.

양자 중첩 상태는 관측을 하는 순간 하나의 상태로 결정되며, 중첩인 상태가 풀린다고 했었죠. 중첩 상태인 큐비트를 넣어봤자 정답과 비교하기 위해 관측을 하는 이상 하나로 결정된 상태를 넣은 것이나 다름 없습니다.

지금 이 상황을 이전에 보여드렸던 파동함수(의 절댓값의 제곱) 그래프로 나타내면 이렇습니다.

틀린 답안을 관측하게 될 확률이 더 높고, 맞는 답안을 관측하게 될 확률은 현저하게 작습니다. 즉, 중첩이 되었건 어쨌건 마지막에 관측을 했을 때 정답이 나오게 될 확률은 여전히 1/8인 것입니다. 나머지 7/8 확률로는 오답을 관측하게 됩니다.

그럼, 결국에는 고전 컴퓨터랑 똑같을 뿐인데 대체 양자 컴퓨터가 왜 효율적이라는 것이며, 어떤게 혁신적이라는 것일까요?

양자 컴퓨터의 혁신성은 양자 알고리즘에 있습니다. 양자 알고리즘은, 양자역학의 원리를 이용해서 틀린 답안이 관측될 확률을 줄이고 맞는 답안이 관측될 확률을 높입니다. 실제로 관측을 하기 전에 말이죠.

그렇게 되면, 관측을 했을 때 더 높은 확률로 맞는 답안이 나오게 될 것이고, 궁극적으로는 전체적인 알고리즘 실행 시간이 줄어들게 되는 것입니다. 정답을 맞추기 위해 무작위하게 때려 맞추는 횟수가 훨씬 더 줄어들기 때문입니다.

대체 어떤 원리를 이용하길래 관측을 하기도 전에 정답을 맞출 확률을 올릴 수 있는 것일까요?

특정한 양자 상태를 관측할 확률은 파동 함수로부터 구할 수 있다고 말씀 드렸었죠? 파동 함숫값의 크기에 제곱을 하면 됩니다. 짤막하게 언급을 하기도 했지만, 지금까지 보여드린 파동 함수의 시각화는 사실 원본 파동 함수가 아니라 "파동 함수의 크기에 제곱"을 한 함수를 나타낸 것입니다.

그래서 0 또는 양수의 값을 가지는 그래프가 그려졌던 것입니다. 상식적으로 생각해보면 당연합니다. 우리가 기존에 알고 있던 확률 체계에서 '음의 확률'이라는 것은 말이 안되기 때문입니다. 기상 예보에서 캐스터가 내일 눈이 올 확률이 -15% 라고 하는 걸 들어보신 적이 있나요?

실제로 파동 함수는 원래 복소 함수, 즉 허수를 포함하는 복소수 값을 가지는 함수입니다. 즉, 양자역학에서의 확률 진폭은 0과 양수 뿐만 아니라 음수, 심지어는 허수까지 가능하다는 것입니다.

이 말은, 두 개의 확률이 파동처럼 서로 간섭하여 증폭되거나 상쇄될 수 있음을 의미합니다. 예를 들어서...

'정답 관측'을 나타내는 양의 확률 파동 2개가 서로 만나 증폭되어서 진폭이 커질 수 있습니다. 정답을 관측할 확률 파동의 진폭이 커졌다는 것은, 정답을 관측할 확률이 커졌다는 것이므로 "알고리즘의 효율이 증가했다"라고 할 수 있습니다.

반대로, '오답 관측'을 나타내는 음의 확률 파동과 양의 확률 파동이 서로 만나 상쇄되어서 진폭이 줄어들 수도 있습니다. 이는 오답을 관측할 확률이 줄었다는 것이므로 이 역시 "알고리즘의 효율이 증가했다"라고 할 수 있습니다.

양자 컴퓨터는 바로 이런 방식을 이용해서 고전 컴퓨터에 비해 알고리즘을 훨씬 더 효율적으로 실행합니다. 고전 컴퓨터는 고전 확률 체계 기반이기 때문에, 음의 확률 파동과 같은 성질을 알고리즘 계산에 사용할 수 없습니다. 어떤 사람들은 양자 컴퓨팅을 '음의 부호가 있는 확률론'이라고 부르기도 합니다.

하지만, 모든 알고리즘을 양자 컴퓨터가 고전 컴퓨터보다 더 빠르게 실행할 수 있는 것은 아닙니다. 확률 파동의 간섭 현상을 적절하고 효율적으로 활용할 수 있는 양자 알고리즘이 새로 개발되어야하기 때문입니다. 그리고 이는 굉장히 어려운 일입니다.

실제로 개발된 양자 알고리즘 중에는, 처음에 예시로 들었던 '숫자 맞추기' 문제를 효율적으로 해결할 수 있는 알고리즘이 있습니다. 바로 그로버의 알고리즘(Grover's algorithm)입니다.

그로버의 알고리즘은, 임의의 함수 f에 대해서 찾고자 하는 함숫값 a가 있으면 f(c) = a를 만족하는 c를 효율적으로 찾을 수 있게 해주는 알고리즘입니다. 숫자 맞추기 문제의 경우 'f(c) = 정답'을 만족하는 비트 c를 찾는 것이 목표였죠.

고전적인 알고리즘은 N개의 숫자 중에서 정답을 찾아내기까지 걸리는 시간이 N에 비례하지만, 그로버의 알고리즘은 N의 제곱근에 비례합니다. 예를 들어서, 1,000,000개의 숫자 중에서 정답을 찾으려면 고전적인 알고리즘으로는 1,000,000에 해당하는 연산량이 필요했습니다. 하지만 그로버의 알고리즘을 사용하면 대략 1,000만큼의 연산량으로 해결할 수 있습니다.

그로버의 알고리즘 외에도 함수의 종류를 판별하는 도이치-조사 알고리즘, 소인수 분해를 빠르게 처리할 수 있는 쇼어 알고리즘 등이 있습니다. 아직은 많은 종류가 개발된 상태는 아니며, 과학자들은 양자 컴퓨터로 더 효율적으로 해결할 수 있는 문제와 알고리즘이 존재하는지 연구하고 있습니다.

양자 컴퓨터가 고전 컴퓨터보다 더 빠르게 해결할 수 있는 문제가 많아지면 많아질수록 양자 컴퓨터의 범용성은 올라갈 것이고, 과학 연구 분야에 유용하게 사용될 수 있을 것입니다.