양자컴퓨팅 그로버 알고리즘 원리: 큐비트와 상태벡터로 본 제곱근 가속의 정체와 흔한 오해

핵심 메시지

• “모든 경우의 수를 동시에 계산한다”는 대중적 요약은 오해를 낳는다. 상태벡터는 직접 들여다볼 수 없고, 메모리에서 읽는 순간 값 하나로 확률이 몰린다.
• n개 후보 중 정답 하나를 찾는 문제에서 양자컴퓨터의 최선은 O(√n)이다. 유튜브 설문에 답한 10만 명, 스탠퍼드 학생, 국제수학올림피아드 참가자 모두에게서 가장 흔했던 답 O(1)은 오답이다.
• 큐비트는 길이가 1인 벡터이고, 각 성분의 크기를 제곱한 값이 그 비트열이 관측될 확률이 된다. 이를 보른 규칙이라 부른다.
• 그로버 알고리즘은 정답 성분의 부호를 뒤집는 연산과 균등 중첩 방향을 축으로 하는 대칭이동을 번갈아 반복해 상태벡터를 정답 쪽으로 조금씩 회전시킨다. 최적 반복 횟수는 약 (π/4)√n이다.
• 제작자 그랜트 샌더슨은 이 가속의 출처를 “병렬 계산”이 아니라 “피타고라스”, 즉 대각선 이동이 허용된 공간이라는 비유로 설명한다.

쉽게 이해하기

영상은 퀴즈 하나로 시작한다. 0부터 n-1 사이의 값 중 단 하나에만 참을 돌려주는 함수가 있고, 내부를 들여다볼 수는 없으며 값을 넣어 보는 것만 허용된다. 고전 컴퓨터라면 하나씩 찍어 보는 수밖에 없어 평균 n/2번, 즉 O(n)이 걸린다. 그렇다면 양자컴퓨터에서는 어떨까. 유튜브 설문에 답한 10만 명, 강연장의 스탠퍼드 학생들, 국제수학올림피아드 참가자들 모두에게서 가장 흔한 답은 O(1)이었지만 정답은 O(√n)이다.

오답이 몰리는 이유를 짚기 위해 제작자는 비유 대신 수학으로 양자컴퓨팅을 정의한다. 양자 프로그램은 특정 출력을 정하는 것이 아니라 가능한 모든 출력에 대한 확률분포를 정한다. k개의 큐비트가 있으면 2의 k제곱 개의 성분을 가진 상태벡터가 있고, 각 성분의 크기를 제곱한 값이 해당 비트열을 읽을 확률이다. 이 분포는 암묵적이어서 직접 볼 수 없고, 한 번 읽으면 그 값에 확률이 전부 몰리도록 상태가 바뀐다. 성분의 부호가 음수여도 확률은 같지만, 그것은 엄연히 다른 상태다.

그로버 알고리즘의 재료는 두 가지다. 첫째, 정답을 빠르게 검증할 수 있는 문제라면 그 검증 회로를 양자 게이트로 옮길 수 있고, 그 결과 정답 비트열에 해당하는 성분의 부호만 뒤집는 연산이 만들어진다. 스도쿠 풀이, 인접 지역이 같은 색을 갖지 않는 지도 색칠, 암호학의 키 탐색이 모두 이 범주에 들어간다. 둘째, 모든 성분이 같은 값을 갖는 균등 중첩 상태를 만들 수 있고, 그 방향을 축으로 벡터를 뒤집는 것도 가능하다.

설명의 핵심은 기하학이다. 알고리즘이 진행되는 동안 상태벡터는 정답 방향과 균등 중첩 방향이 만드는 2차원 평면 안에서만 움직인다. 이 평면에서 균등 상태와 정답 축이 이루는 작은 각 θ는 sinθ = 1/√n을 만족한다. 서로 다른 두 축에 대한 대칭이동을 연달아 적용하면 그 효과는 두 축 사이 각의 두 배만큼의 회전이 되므로, 한 번의 반복이 2θ만큼 벡터를 돌린다. 초기 상태를 90도 조금 못 미치게 돌리면 되니 필요한 반복 횟수는 약 (π/4)√n이다. 후보가 2의 20제곱, 즉 약 100만 개라면 약 804번이다.

마지막으로 제작자는 두 가지를 덧붙인다. 하나는 설명을 위해 생략한 사실, 즉 상태벡터의 성분은 일반적으로 복소수이며 크기와 위상을 함께 담는다는 점이다. 그로버 알고리즘에서는 양수와 음수만 나타나 무시해도 안전하지만, 소인수분해의 쇼어 알고리즘 같은 다른 알고리즘에서는 위상이 결정적이다. 다른 하나는 가속의 출처다. 정육면체의 한 모서리에서 반대편 모서리로 갈 때 변만 따라가면 n칸을 걸어야 하지만 대각선이 허용되면 √n이면 된다는 비유로, 양자컴퓨팅은 고전적 상태에 해당하는 좌표축 방향 외에 수많은 대각선 방향을 함께 쓸 수 있는 세계라고 정리한다.

주요 인사이트

• 지수 수준의 가속은 소인수분해의 쇼어 알고리즘 같은 특수한 문제에 한정된다. 대부분의 문제에서 기대할 수 있는 이득은 제곱근 수준이며, 이쪽이 더 대표적인 그림이다.
• 상태벡터는 원리적으로 볼 수 없다. 양자 알고리즘의 가치는 확률을 원하는 한 성분에 몰아줄 수 있느냐에 달려 있고, 그 성분이 실제로 궁금한 질문의 답이어야 한다.
• 그로버 알고리즘은 정답 검증이 빠른 모든 문제, 곧 NP 문제 전반에 적용되는 범용 수단이다. 제곱근 가속이라도 이런 포괄성을 갖는 절차가 존재한다는 사실 자체가 흥미로운 지점이다.
• 반복 횟수는 미리 계산해 정해 두어야 한다. 도중에 벡터를 들여다볼 방법이 없으므로 언제 멈출지는 오직 기하학적 추론으로 결정된다.
• 결과가 100% 보장되지는 않는다. 다만 애초에 검증이 쉬운 문제이므로 고전 컴퓨터로 답을 확인하고, 빗나갔다면 다시 돌리면 된다. 여러 번 재실행이 필요할 확률은 극히 낮다.

자주 묻는 질문

관련 AI 소식