정보의 속도 한계와 양자컴퓨터: 이진 탐색과 섀넌 엔트로피로 이해하는 log₂n의 벽

핵심 메시지

• 빛의 속도가 우주의 속도 제한이라면, 정보에도 제한이 있다. 예/아니오 질문 하나로 얻을 수 있는 정보는 최대 1비트다.
• 1부터 8 중 하나를 맞힐 때 하나씩 묻는 방법은 평균 4.375번이 필요하지만, 절반씩 나누는 이진 탐색은 언제나 3번이면 끝난다. 3은 곧 8의 밑 2 로그다.
• 가능성을 n개에서 b개로 줄이려면 최소한 n을 b로 나눈 값의 밑 2 로그만큼 질문해야 하며, 양자컴퓨터도 이 한계 아래로는 못 간다.
• 양자컴퓨터가 빠른 이유는 한계를 깨서가 아니라, 고전 컴퓨터보다 그 한계에 더 가까이 다가가기 때문이다.
• 동전 두 개가 같은 면인지 알아내는 문제에서 고전 컴퓨터는 두 번 봐야 하지만, 자석과 소리를 쓰면 단 한 번의 관찰로 답이 나온다.

쉽게 이해하기

강의는 정보의 속도 제한이라는 개념에서 출발한다. 1부터 8 사이의 수를 예/아니오 질문으로 맞힌다고 해보자. 1인지, 2인지 하나씩 물어 가는 방법은 평균 4.375번이 필요하다. 반면 '앞쪽 절반에 있느냐'를 반복해 묻는 이진 탐색은 운과 상관없이 언제나 3번이면 끝나는데, 8이 2를 세 번 곱한 수, 즉 밑 2 로그가 3이기 때문이다.

이 3이라는 숫자가 바로 한계다. 어떤 전략을 짜도 평균 질문 수를 3보다 줄일 수는 없다. 일반화하면 가능성이 n개일 때 최소 log₂n번, 가능성을 n개에서 b개로 줄일 때는 최소 log₂(n/b)번의 질문이 필요하다. 물론 질문은 답이 둘뿐인 것이어야 한다. '몇 번째 자리 숫자냐'처럼 열 가지 답이 가능한 질문은 반칙이다. 이 개념을 정리한 사람이 엔트로피와 정보 이득을 세운 클로드 섀넌이다.

핵심은 양자컴퓨터도 이 제한을 넘지 못한다는 점이다. 우주에 있는 모든 원자를 끌어모아 양자컴퓨터를 만들어도, 1비트를 얻으려면 예/아니오 관찰 한 번이 필요하다. 그렇다면 양자컴퓨터는 왜 필요한가. 고전 컴퓨터가 이 한계에 한참 못 미치는 문제들에서, 양자 알고리즘은 한계에 훨씬 가까이 가거나 아예 도달하기 때문이다. 강의에서 예고한 도이치 알고리즘은 한계에 도달하는 쪽이고, 그로버 알고리즘은 고전의 n에 비례하던 비용을 √n으로 줄이지만 한계에는 못 미치는 쪽이다.

차이를 보여주는 예가 동전 두 개다. 두 동전이 앞뒤 중 무엇인지 각각 알아내려면 두 번 봐야 하고, 이는 한계와 일치한다. 그런데 질문을 '두 동전이 같은 면인가'로 바꾸면 가능성이 넷에서 둘로 줄어드는 것뿐이니 한 번이면 충분해야 한다. 그럼에도 눈으로 보는 방식은 여전히 두 번을 요구한다. 각각을 확인한 뒤 머릿속에서 비교해야 하기 때문이다.

발표자는 감각을 바꾸는 실험으로 이 벽을 넘는다. 동전 대신 앞면이 N극, 뒷면이 S극인 자석을 상자에 넣고 보이지 않는 상태에서 하나를 다른 하나 위에 포갠다. 두 면이 같으면 서로 다른 극이 마주 보게 되어 달라붙는 소리가 나고, 다르면 밀어낸다. 보지 않고 듣기만 해도 한 번의 관찰로 답이 나오는 것이다. 고전 컴퓨터는 계산 전에 변수를 모두 관찰해야 하지만, 양자컴퓨터는 값을 관찰하지 않은 채 조작한 뒤 마지막에 한 번만 관찰할 수 있다는 것이 이 비유가 가리키는 차이다.

주요 인사이트

• '양자컴퓨터는 아주 빠른 고전 컴퓨터'라는 표현은 틀렸다. 고전 컴퓨터는 두 번의 관찰을 아주 빠르게 해치우는 것이고, 양자컴퓨터는 한 번의 관찰로 끝내는 것이다. 속도가 아니라 필요한 관찰 횟수가 다르다.
• 이진 탐색이 최적인 이유가 로그 계산에서 저절로 따라 나온다. 질문 하나가 가능성을 반으로 자르므로, k번 질문으로 구별할 수 있는 경우의 수는 2의 k제곱이다.
• 가능성의 수가 2의 거듭제곱이 아니면 완벽한 이진 트리를 만들 수 없어 평균 질문 수가 로그값보다 커진다. 그래서 이 값은 정확한 개수가 아니라 넘을 수 없는 하한이다.
• 문제를 다시 정의하면 필요한 관찰 수가 달라진다. '각 동전이 무엇인가'와 '두 동전이 같은가'는 답의 가짓수가 다르고, 후자는 앞의 정보를 알지 못한 채로도 답할 수 있다.
• 중첩을 만들어 함수를 한 번만 적용한다는 아이디어는 말로는 간단하지만, 큐비트를 조작하는 일은 물리적으로도 수학적으로도 까다롭고 관찰하는 순간 많은 정보가 사라진다.

자주 묻는 질문

관련 AI 소식