지난주에 양자 컴퓨팅을 소개하는 영상을 올렸는데, 마지막 섹션에서 그로버의 알고리즘(Grover's algorithm)이라고 알려진 것을 단계별로 살펴보았습니다. 그리고 제가 본 댓글들을 바탕으로 볼 때, 핵심적인 부분을 설명하는 데 제가 분명히 더 잘할 수 있었던 매우 흔한 혼란 지점이 있었다고 생각합니다. 그래서 여기에 약간의 명확성을 추가하기를 바라며 아주 간단한 보충 자료를 만들고자 합니다. 전제는 큰 선택지 묶음 중에서 어떤 고유 값(unique value)에 의해 어떻게든 트리거되는 함수가 있다는 것이었고, 이 퍼즐은 기본적으로 다양한 입력값에 그 함수를 적용하는 것만으로 그 고유 값을 어떻게 찾아낼 수 있는지 알아내는 것입니다.

원래 클래식한 환경에서는 그다지 흥미로운 질문이 아닙니다. 할 수 있는 최선은 추측하고 확인(guess and check)하는 것이지만, 우리가 다룬 것은 양자 컴퓨터의 환경에서 가능해지는 완전히 다른 접근 방식이었습니다. 이 과정을 진행했을 때, 제가 댓글을 올바르게 이해하고 있다면, 핵심적인 단계가 마치 이 단계를 적용하려면 이미 찾고 있는 값을 알고 있어야 하는 것처럼 보였는데, 이는 물론 알고리즘 전체 목적을 무효화할 것입니다.

더 구체적으로는, 우리는 매우 고차원 벡터 공간(high dimensional vector space)을 가지고 있었고, 그 공간의 축 중 하나가 우리가 찾고 있는 값에 해당했으며, 이 알고리즘 단계는 마치 그 축을 따라 뒤집기(flipping along that axis), 즉 그 방향으로 벡터의 어떤 성분이라도 -1을 곱하는 것처럼 보였습니다. 그런데 시청자들은 본질적으로 '잠깐만요, 잠깐만요'라며, 이미 어떤 축을 찾고 있는지 모르는 상태에서 어떻게 그것을 할 수 있냐고 질문했습니다. 저는 진심으로 그 반론을 막으려고 노력했지만, 실패한 것 같습니다. 그래서 되돌아가서, 만약 우리가 스도쿠(sudoku)를 푸는 것과 같은 매우 구체적인 예시에 초점을 맞춘다면 전체 논의가 더 명확할 것이라고 생각합니다.

일반적인 고전 컴퓨터(classical computer)에서, 제안된 해결책이 모든 스도쿠 규칙을 따르는지 확인하고 퍼즐을 푸는 함수를 작성하는 것은 어렵지 않습니다. 아시다시피, 행, 열, 사각형 내의 중복 등을 확인하는 식이죠. 하지만 이런 함수를 작성했다고 해서, 단지 해결책을 검증하는 방법을 안다는 사실만으로는 애초에 그 해결책이 무엇인지 전혀 명확해지지 않습니다. 결국 이것이 스도쿠가 퍼즐인 이유입니다. 규칙만으로는 정답을 드러내지 못하니까요. 이와 유사하지만 실제로는 훨씬 더 강력한 가정이 적용되는 다른 상황들도 있습니다.

예를 들어, SHA-256 함수는 암호학적 해시 함수 (cryptographic hash function)라고 불리는 것입니다. 이는 기본적으로 특정 출력을 내놓는 입력값이 무엇인지 찾고 싶을 때, 함수가 어떻게 구현되었는지를 살펴보는 것만으로는 별다른 통찰을 얻을 수 없다고 강력하게 믿어지는 것을 의미합니다. 만약 누군가가 이를 역공학 (reverse engineer)할 수 있다면, 전 세계의 모든 비트코인을 채굴하고 수많은 다른 암호화 체계들을 깨뜨릴 수 있을 것입니다. 하지만 특정 출력을 찾기 위해 할 수 있는 최선의 방법은 추측하고 확인하는 (guess and check) 것뿐이라고 여겨집니다.

따라서 키 값 (key value)이 어떤 커튼 뒤에 함수 안에 숨겨져 있는 것이 아니라, 함수 자체에서 발생하는 찾기 어려운 창발적 현상 (emergent phenomenon)에 더 가깝습니다. 이제 그로버 알고리즘 (Grover's algorithm)의 아이디어는, 어떤 어려운 문제에 대해 이러한 종류의 검증 함수 (verifier function)를 가지고 있고 이를 양자 컴퓨팅 (quantum computing)의 언어로 변환한다면, 모든 가능성에 대해 단순히 추측하고 확인하는 것보다 더 적은 단계로 유효한 해결책을 걸러내는 방법이 존재한다는 것입니다. 분명히 말씀드리자면, 이것이 극적으로 빠른 것은 아닙니다. 단지 이차적 가속 (quadratic speedup)일 뿐이며, 양자 컴퓨팅을 작동시키기 위한 오버헤드 (overheads)를 고려하면 솔직히 그 유용성에는 의문이 있습니다.

사실, 이 부분에 대해서는 마지막에 조금 더 자세히 이야기해 보겠습니다. 우선, 명확히 하자면, 만약 여러분에게 이러한 스도쿠 검증 함수 (Sudoku verifying function)가 있다고 해서, 그것을 단순히 양자 컴퓨터에서 실행할 수 있는 것은 아닙니다. 결국, 양자 컴퓨터는 완전히 다른 언어를 사용하며, 벡터 조작 (vector manipulation)과 훨씬 더 유사해 보이는 완전히 다른 컴퓨팅 프레임워크를 사용하기 때문입니다. 이 검증 함수를 새로운 맥락으로 이식하기 위한 첫 번째 단계는, 여러분의 검증기 (verifier)를 AND, OR, NOT과 같은 일련의 논리 게이트 (logic gates)로 컴파일했다고 상상하는 것입니다.

따라서 제안된 어떤 스도쿠 해답에 대해서도, 그것을 모두 이진수 (binary)로 표현하면, 그 모든 비트 (bits)들이 논리 게이트의 망을 통해 처리될 것이며, 유효한 스도쿠 해답이라면 출력값은 1이 되고, 유효하지 않은 모든 경우에는 0이 될 것입니다. 그리고 다시 말씀드리지만, 이러한 논리 게이트를 조립할 수 있다는 것은 어떤 입력이 퍼즐을 해결할지 미리 알 필요가 없음을 의미합니다. 논리 게이트는 게임의 규칙을 추출할 뿐, 전략을 추출하는 것이 아니기 때문입니다. 이제 모든 분이 메인 영상을, 특히 상태 벡터 (state vector)의 기초에 관한 핵심 섹션을 시청했다고 가정하겠습니다만, 빠르게 요약하자면, 결론은 모든 가능한 비트 문자열 (bit string)을 어떤 고차원 공간의 좌표축을 따르는 단위 벡터 (unit vector)로 생각한다는 것입니다.

선형 대수학 (linear algebra)의 언어로 말하자면, 여러분은 이것들을 좌표계의 기저 벡터 (basis vectors)라고 부를 것입니다. 예를 들어, 2-큐비트 (2-qubit) 양자 컴퓨터의 경우, 4개의 가능한 비트 문자열을 갖게 되며, 이것들은 모두 어떤 4차원 공간에서의 기저 방향처럼 보일 것입니다. 이러한 상태 벡터들은 매우 빠르게 거대해집니다. 만약 $k$-큐비트 양자 컴퓨터를 가지고 있다면, $2^k$개의 가능한 비트 문자열을 갖게 되며, 여러분은 그 각각을 매우 높은 차원의 벡터 공간에서의 좌표 방향으로 생각하게 됩니다.

이제 양자 컴퓨터 (quantum computer)에서의 연산은 여러분이 고전 컴퓨터 (classical computer)에서 볼 수 있는 방식처럼 참(true) 또는 거짓(false)을 내뱉지 않습니다. 대신, 벡터 (vector)를 입력받아 동일한 공간에 존재하는 새로운 벡터를 내뱉습니다. 그리고 지난 영상에서 말씀드렸듯이, 여러분은 종종 이러한 연산을 해당 공간 내에서 벡터를 뒤집거나 회전시키는 것으로 생각하곤 합니다. 자, 바로 이 지점이 혼란의 핵심입니다. 저는 만약 여러분에게 1 또는 0을 내뱉는 스도쿠 검사기와 같은 고전적인 검증 함수 (classical verifier function)가 있다면, 다음과 같은 동작을 하는 양자 컴퓨터 상의 연산으로 이를 번역하는 것이 가능하다는 점을 언급했습니다.

만약 고전적인 경우에서 어떤 비트 문자열 (bit string)이 참(true)에 대해 1을 반환한다면, 양자적인 경우에서는 그에 대응하는 기저 벡터 (basis vector)에 -1을 곱하게 되며, 이는 사실상 180도를 뒤집는 것과 같습니다. 그리고 고전적인 경우에서 어떤 비트 문자열이 거짓(false)에 대해 0을 출력한다면, 양자 번역에서는 그에 대응하는 기저 벡터가 변하지 않습니다. 저는 이 단계가 혼란을 야기했을 수 있는 세 가지 이유를 찾을 수 있었습니다. 무엇보다도, 저는 이것이 실제로 어떻게 작동하는지 설명하지 않았습니다. 번역 과정을 단계별로 짚어보지 않았죠. 제가 그 영상에서 바랐던 점은, 고전 세계에서 참과 거짓을 반환하는 것과 양자 세계에서 벡터에 -1 또는 1을 곱하는 것 사이에 원칙적으로 이러한 대응 관계가 존재한다는 사실을 여러분이 너무 큰 도약 없이 받아들여 주기를 바랐던 것입니다.

하지만 그것이 무리한 비약일 수도 있습니다. 저는 그 번역이 어떤 모습인지 미리 보여드릴 수도 있습니다. 여기서 관련된 검색어는 양자 컴파일 (quantum compilation)이지만, 솔직히 말씀드리면, 덧셈을 구현하는 논리 게이트 (logic gates)를 안다고 해서 두 숫자를 더하는 법을 크게 배우지 못하는 것과 마찬가지로, 이것이 명확성을 크게 더해주지는 않을 것이라고 생각합니다. 정확히 일치하지는 않지만, 느슨하게 말하자면, 여러분이 AND 게이트를 볼 때마다 그것을 일종의 AND와 유사해 보이는 양자 연산으로 번역하는 것과 같습니다. NOT 게이트를 볼 때마다, 그것과 유사한 동작을 수행하는 양자 대응물 (quantum analogue)이 존재하는 것과 같습니다.

혼란의 진짜 원인은 저수준 (low-level) 세부 정보의 부족이 아니라, 제가 전체적인 설정을 어떻게 구성했는지에서 비롯된 것이라고 생각합니다. 저는 그 영상의 도입부에서 우리가 찾고 있는 어떤 미스터리한 숫자가 있다고 상상하도록 유도했습니다. 그리고 한 댓글 작성자가 유익하게 지적해 주었듯이, 이 방식은 마치 컴퓨터가 정답을 미리 알고 있으면서 우리에게 숨기고 있는 것처럼 보이게 만들었습니다. 또한, 입력값이 12인지 확인하는 예시 함수를 잠시 보여주며 우리가 그 함수를 블랙박스 (black box)로 취급할 것이라고 말한 점이 이러한 오해를 거의 확실하게 악화시켰습니다.

그것은 제 잘못입니다. 그것은 오해를 불러일으킬 수 있는 시작 방식이었습니다. 제가 암시하고 싶었던 것은, Grover의 알고리즘을 사용할 때 새로운 양자 함수를 사용하는 유일한 방법은 그것을 역공학 (reverse engineering) 하는 것이 아니라 입력값에 대해 시도해 보는 것뿐이라는 점이었습니다. 그런 의미에서 그것은 블랙박스로 취급됩니다. 하지만 분명히 말씀드리자면, 고전적 검증기 (classical verifier)를 양자 버전으로 변환하기 위해서는 반드시 함수의 내부 구조 (guts)를 파고들어야 합니다. 그리고 이것이 설득력 있는 예시가 되려면, 함수가 하는 일이 단순히 입력값이 어떤 숨겨진 숫자와 일치하는지 확인하는 것뿐이라면 매우 어리석은 일이 될 것입니다.

Sudoku 예시가 훨씬 더 나으며, SHA-256과 같은 암호화 해시 (cryptographic hash)라면 훨씬 더 좋을 것입니다. 이러한 맥락에서는 함수를 작동시키는 단 하나의 값이 존재하며 우리는 그것이 무엇인지 모르지만, 컴퓨터 또한 그것이 무엇인지 모릅니다. 키 값이 소스 코드 안에 그냥 숨겨져 있는 것이 아닙니다. 함수를 작동시키는 것이 'true'를 반환하는 것을 의미하는 고전적 (classical) 설정에 있든, 함수를 작동시키는 것이 -1을 곱하는 것을 의미하는 양자 (quantum) 설정에 있든, 어떤 특정 키 입력이 이를 수행할지는 찾기 어려운 문제이며 해당 논리 게이트 (logic gates)들의 창발적 속성 (emergent property)입니다.

이는 사전에 미리 내장되어 있는(baked in) 것이 아닙니다. 제가 생각하는 또 다른 혼란의 원인은, 선형성 (linearity)이라는 개념을 적절히 강조하지 못했다는 점입니다. 사실, 이것은 양자 컴퓨팅 (quantum computing)과 양자 역학 (quantum mechanics)에서 매우 핵심적인 특징이기 때문에, 제가 이 후속 영상을 제작하게 된 이유의 절반은 이에 대해 이야기하기 위한 핑계라고 할 수 있을 정도입니다. 따라서 대부분의 벡터는 순수한 기저 방향 (pure basis direction)처럼 보이지 않으며, 모든 서로 다른 기저 벡터 (basis vectors)들의 가중치 합 (weighted sum)처럼 보입니다. 이를 표현하는 한 가지 방법은 열 벡터 (column vector)를 사용하는 것이며, 여기서 각 성분 (component)은 가능한 비트 문자열 (bitstrings) 중 하나와 연관된 것으로 간주합니다.

물리학자들 사이에서 더 일반적인 관습은 일반적인 벡터를 모든 기저 방향의 명시적인 가중치 합으로 작성하는 것이며, 이때 각 방향은 켓 (ket)으로 표현됩니다. 컴퓨터의 상태 벡터 (state vector)가 이와 같은 형태를 띨 때, 여러분은 그것이 중첩 (superposition) 상태에 있다고 말하며, 이는 여러 개의 서로 다른 비트 문자열과 연관된 0이 아닌 성분을 가지고 있음을 의미합니다. 이는 누군가가 북동쪽으로 걷고 있다면, 그들의 속도 (velocity)는 북쪽과 동쪽의 중첩이며, 두 방향으로 동시에 이동하고 있다고 말하는 것과 매우 유사합니다. 지난 영상에서의 핵심 아이디어는, 여러분이 이러한 중첩 상태에 있는 상태 벡터의 좌표를 실제로 결코 볼 수 없다는 것입니다.

컴퓨터로부터 읽기 (read out)를 수행할 때, 여러분이 보는 것은 무작위로 선택된 하나의 비트 문자열뿐이며, 그것을 볼 확률은 해당 값과 연관된 상태 벡터 성분의 크기 (magnitude)의 제곱과 같습니다. 여기서 절댓값 기호를 사용하여 크기 (magnitude)라고 말하는 이유는, 일반적으로 이러한 성분들이 복소수 (complex numbers)일 수 있기 때문이지만, 단순함을 위해 저는 실수 (real values)만을 보여드릴 것입니다. 양자 컴퓨터에서의 연산이 선형적 (linear)이라고 말할 때, 제 의미는 만약 여러분이 서로 다른 기저 방향들의 이러한 가중치 합, 즉 중첩 상태를 입력으로 넣는다면, 출력은 각 벡터의 변환된 버전들에 대한 동일한 가중치 합의 형태로 나타난다는 것입니다.

여기 아주 작은 예시가 있습니다. 단일 큐비트 (single qubit) 상에서, 우리는 z-게이트 (z-gate)라고 부르는 연산이 있습니다. 이 연산이 하는 일은 0 방향은 변경하지 않고, 수직인 1 방향에 -1을 곱하는 것입니다. 이것들은 무수히 많은 가능한 상태 벡터 (state vectors) 중 단 두 개뿐이지만, 여러분이 알아야 할 전부는 이것들입니다. 만약 이 두 상태의 중첩 (superposition), 즉 0이 조금 있고 1이 조금 있는 상태를 입력으로 넣는다면, 여러분은 z-게이트가 각 부분을 각각 어떻게 변화시키는지 살펴본 다음, 그것들을 모두 더하면 됩니다.