도이치 알고리즘

도이치 알고리즘은 $n = 1$ 인 특수한 경우의 패리티 문제를 해결합니다. 양자 컴퓨팅의 맥락에서는 이 문제를 도이치 문제라고 부르기도 하며, 이 강의에서도 해당 명칭을 따르겠습니다.

좀 더 정확히 말하면, 입력은 1비트에서 1비트로 가는 함수 $f:\Sigma \rightarrow \Sigma$ 로 표현됩니다. 이러한 함수는 네 가지가 있습니다.

$$\rule[-10mm]{0mm}{10mm} \begin{array}{c|c} a & f_1(a)\\ \hline 0 & 0\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_2(a)\\ \hline 0 & 0\\ 1 & 1 \end{array} \qquad \begin{array}{c|c} a & f_3(a)\\ \hline 0 & 1\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_4(a)\\ \hline 0 & 1\\ 1 & 1 \end{array}$$

이 중 첫 번째와 마지막 함수는 상수 함수이고, 가운데 두 함수는 균형 함수입니다. 균형 함수란 입력 전체에 걸쳐 두 가지 가능한 출력값이 동일한 횟수만큼 나타나는 함수를 뜻합니다. 도이치 문제는 입력 함수가 상수 함수와 균형 함수 중 어느 범주에 속하는지를 판별하는 문제입니다.

Deutsch's problem

입력: 함수 $f:\{0,1\}\rightarrow\{0,1\}$
출력: $f$ 가 상수 함수이면 $0$, 균형 함수이면 $1$

도이치 문제의 입력 함수 $f$ 를 문자열에 대한 임의 접근을 표현하는 것으로 본다면, 우리는 2비트 문자열 $f(0)f(1)$ 을 다루고 있는 셈입니다.

$$\begin{array}{cc} \mathsf{function} & \mathsf{string}\\ \hline f_1 & 00 \\ f_2 & 01 \\ f_3 & 10 \\ f_4 & 11 \end{array}$$

이러한 관점에서 보면, 도이치 문제는 두 비트의 패리티(동등하게는 배타적 논리합, XOR)를 계산하는 문제입니다.

이 문제를 올바르게 해결하는 모든 고전 질의 알고리즘은 $f(0)$ 과 $f(1)$ 두 비트를 모두 질의해야 합니다. 예컨대 $f(1) = 1$ 이라는 사실을 알게 되었다고 해도, 정답은 $f(0) = 1$ 인지 $f(0) = 0$ 인지에 따라 각각 $0$ 이 될 수도 있고 $1$ 이 될 수도 있습니다. 다른 경우들도 마찬가지입니다. 두 비트 중 하나만 알아서는 그 패리티에 대해 아무런 정보도 얻을 수 없습니다. 따라서 이전 절에서 설명한 불리언 Circuit은 이 문제를 해결하는 데 필요한 질의 횟수 측면에서 우리가 할 수 있는 최선입니다.

양자 회로 기술

도이치 알고리즘은 단 한 번의 질의로 도이치 문제를 해결하며, 이로써 고전적 계산에 대한 양자 계산의 정량적 우위를 보여줍니다. 두 번이 아닌 한 번의 질의라는 다소 소박한 우위일 수 있지만, 어딘가에서는 시작해야 합니다. 과학적 진보는 때때로 겉보기에 보잘것없는 기원에서 비롯됩니다.

다음은 도이치 알고리즘을 기술하는 양자 Circuit입니다.

분석

도이치 알고리즘을 분석하기 위해, 위 Circuit의 동작을 따라가면서 다음 그림이 가리키는 시점마다 Qubit의 상태를 파악해 보겠습니다.

초기 상태는 $\vert 1\rangle \vert 0 \rangle$ 이며, Circuit 왼쪽에 있는 두 개의 Hadamard 연산은 이 상태를 다음과 같이 변환합니다.

$$\vert \pi_1 \rangle = \vert - \rangle \vert + \rangle = \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 0\rangle + \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 1\rangle.$$

(항상 그렇듯, 여기서는 위쪽 Qubit을 오른쪽에, 아래쪽 Qubit을 왼쪽에 배치하는 Qiskit의 Qubit 순서 규약을 따르고 있습니다.) 이 곱 상태를 부분적으로만 분배한 채로(Qubit 1의 상태는 공통 인수로 밖에 빼둔 상태) 표기하는 것이 다소 직관적이지 않게 느껴질 수 있지만, 이렇게 하면 이후의 식을 더 간결하게 나타낼 수 있습니다.

다음으로 $U_f$ Gate가 수행됩니다. $U_f$ Gate의 정의에 따라, 위쪽/오른쪽 Qubit의 고전적 상태에 대한 함수 $f$ 의 값이 아래쪽/왼쪽 Qubit에 XOR되며, 이에 따라 $\vert \pi_1\rangle$ 은 다음 상태로 변환됩니다.

$$\vert \pi_2 \rangle = \frac{1}{2} \bigl( \vert 0 \oplus f(0) \rangle - \vert 1 \oplus f(0) \rangle \bigr) \vert 0 \rangle + \frac{1}{2} \bigl( \vert 0 \oplus f(1) \rangle - \vert 1 \oplus f(1) \rangle \bigr) \vert 1 \rangle.$$

다음 공식을 관찰하면 이 식을 단순화할 수 있습니다.

$$\vert 0 \oplus a\rangle - \vert 1 \oplus a\rangle = (-1)^a \bigl( \vert 0\rangle - \vert 1\rangle \bigr)$$

이 공식은 $a\in\Sigma$ 의 가능한 두 값 모두에 대해 성립합니다. 좀 더 자세히 살펴보면, 두 경우는 다음과 같습니다.

$$\begin{aligned} \vert 0 \oplus 0\rangle - \vert 1 \oplus 0\rangle & = \vert 0 \rangle - \vert 1 \rangle = (-1)^0 \bigl( \vert 0\rangle - \vert 1\rangle \bigr)\\ \vert 0 \oplus 1\rangle - \vert 1 \oplus 1\rangle & = \vert 1 \rangle - \vert 0\rangle = (-1)^1 \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \end{aligned}$$

따라서 $\vert\pi_2\rangle$ 을 다음과 같이 표현할 수도 있습니다.

$$\begin{aligned} \vert\pi_2\rangle & = \frac{1}{2} (-1)^{f(0)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 0 \rangle + \frac{1}{2} (-1)^{f(1)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 1 \rangle \\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

흥미로운 일이 일어났습니다! $U_f$ Gate는 표준 기저 상태에 작용할 때 위쪽/오른쪽 Qubit은 그대로 두고 함수 값을 아래쪽/왼쪽 Qubit에 XOR하지만, 여기서는 위쪽/오른쪽 Qubit의 상태가 (일반적으로) 변하는 반면 아래쪽/왼쪽 Qubit의 상태는 그대로 유지됨을 볼 수 있습니다. 구체적으로는 $U_f$ Gate가 수행되기 전과 후 모두 $\vert - \rangle$ 상태를 유지합니다. 이 현상은 *위상 킥백(phase kickback)*이라고 알려져 있으며, 곧 이에 대해 더 자세히 다루겠습니다.

마지막으로 $(-1)^{f(0)}$ 인수를 합 바깥으로 빼내는 단순화를 한 번 더 거치면, 상태 $\vert\pi_2\rangle$ 에 대한 다음 표현을 얻습니다.

$$\begin{aligned} \vert\pi_2\rangle & = (-1)^{f(0)} \vert - \rangle \biggl( \frac{\vert 0\rangle + (-1)^{f(0) \oplus f(1)} \vert 1\rangle}{\sqrt{2}}\biggr) \\ & = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert + \rangle & \text{if $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert - \rangle & \text{if $f(0) \oplus f(1) = 1$}. \end{cases} \end{aligned}$$

여기서 $-1$ 의 지수에 $f(1) - f(0)$ 이 아니라 $f(0) \oplus f(1)$ 이 등장한다는 점에 주목해 주세요. 순수하게 대수적인 관점에서 보면 전자가 더 자연스러워 보일 수 있지만, 어느 쪽으로 계산해도 결과는 같습니다. 그 이유는 임의의 정수 $k$ 에 대해 $(-1)^k$ 의 값은 $k$ 가 짝수인지 홀수인지에만 의존하기 때문입니다.

마지막 Hadamard Gate를 위쪽 Qubit에 적용하면, 다음 상태가 됩니다.

$$\vert \pi_3 \rangle = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert 0 \rangle & \text{if $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert 1 \rangle & \text{if $f(0) \oplus f(1) = 1$}, \end{cases}$$

이 상태에서 오른쪽/위쪽 Qubit을 측정하면 확률 $1$ 로 올바른 결과가 나옵니다.

위상 킥백에 관한 추가 논의

다음으로 넘어가기 전에, 위상 킥백 현상에 대해 새로운 통찰을 줄 수 있는 약간 다른 각도에서 위 분석을 살펴보겠습니다.

먼저, 다음 공식이 비트 $b,c\in\Sigma$ 의 모든 선택에 대해 성립한다는 점에 주목합니다.

$$\vert b \oplus c\rangle = X^c \vert b \rangle$$

이 공식은 $c = 0$ 과 $c = 1$ 두 값에 대해 확인함으로써 검증할 수 있습니다.

$$\begin{aligned} \vert b \oplus 0 \rangle & = \vert b\rangle = \mathbb{I} \vert b \rangle = X^0 \vert b \rangle\\ \vert b \oplus 1 \rangle & = \vert \neg b\rangle = X \vert b \rangle = X^1 \vert b \rangle. \end{aligned}$$

이 공식을 사용하면 다음과 같은 결과를 얻습니다.

$$U_f \bigl(\vert b\rangle \vert a \rangle\bigr) = \vert b \oplus f(a) \rangle \vert a \rangle = \bigl(X^{f(a)}\vert b \rangle\bigr) \vert a \rangle$$

이는 비트 $a,b\in\Sigma$ 의 모든 선택에 대해 성립합니다. 이 공식이 $b=0$ 과 $b=1$ 에 대해 성립하므로, 선형성에 의해 다음이 성립함을 알 수 있습니다.

$$U_f \bigl( \vert \psi \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)}\vert \psi \rangle\bigr) \vert a \rangle$$

이는 모든 Qubit 상태 벡터 $\vert \psi\rangle$ 에 대해 성립하며, 따라서

$$U_f \bigl( \vert - \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)} \vert - \rangle \bigr) \vert a \rangle = (-1)^{f(a)} \vert - \rangle \vert a \rangle.$$

이것이 성립하는 핵심은 $X\vert - \rangle = - \vert - \rangle$ 이라는 사실입니다. 수학적 용어로 표현하면, 벡터 $\vert - \rangle$ 은 행렬 $X$ 의 고유벡터이며 고윳값이 $-1$ 인 경우에 해당합니다.

고유벡터와 고윳값에 대해서는 앞으로 다룰 위상 추정과 인수분해 강의에서 더 자세히 다룰 예정이며, 거기에서는 위상 킥백 현상이 다른 유니터리 연산으로 일반화됩니다.

스칼라가 텐서곱을 자유롭게 통과한다는 점을 유념하면, 위 분석에서 연산 $U_f$ 가 $\vert \pi_1\rangle$ 을 $\vert \pi_2\rangle$ 로 어떻게 변환하는지에 대한 또 다른 추론 방식을 찾을 수 있습니다.

$$\begin{aligned} \vert \pi_2 \rangle & = U_f \bigl( \vert - \rangle \vert + \rangle \bigr)\\ & = \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 0\rangle \bigr) + \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 1\rangle \bigr)\\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

Qiskit에서의 구현

이제 Qiskit에서 도이치 알고리즘을 어떻게 구현할 수 있는지 살펴보겠습니다. 버전 확인부터 시작한 뒤, 이 구현에만 필요한 임포트를 수행하겠습니다. 이후에 이어지는 다른 알고리즘의 구현에서는 모듈성을 더 높이기 위해 필요한 임포트를 각각 별도로 수행하겠습니다.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-aer

from qiskit import __version__

print(__version__)

2.1.1

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

먼저, 앞서 설명한 1비트에서 1비트로 가는 네 가지 함수 $f_1,$ $f_2,$ $f_3,$ $f_4$ 중 하나에 대한 질의 Gate를 구현하는 양자 Circuit을 정의하겠습니다. 이미 언급했듯이, 질의 Gate의 구현은 사실 도이치 알고리즘 자체의 일부가 아닙니다. 여기서는 질의 Gate의 Circuit 구현 형태로 입력을 준비하는 한 가지 방법을 보여줄 뿐입니다.

def deutsch_function(case: int):
    # This function generates a quantum circuit for one of the 4 functions
    # from one bit to one bit

    if case not in [1, 2, 3, 4]:
        raise ValueError("`case` must be 1, 2, 3, or 4.")

    f = QuantumCircuit(2)
    if case in [2, 3]:
        f.cx(0, 1)
    if case in [3, 4]:
        f.x(1)
    return f

draw 메서드를 사용하면 각 Circuit이 어떻게 생겼는지 볼 수 있습니다. 다음은 함수 $f_3$ 에 대한 Circuit입니다.

display(deutsch_function(3).draw(output="mpl"))

다음으로 도이치 알고리즘의 실제 양자 Circuit을 만들되, 질의 Gate는 인자로 전달되는 양자 Circuit 구현으로 대체하겠습니다. 잠시 후 앞서 정의한 deutsch_function 함수가 정의하는 네 가지 Circuit 중 하나를 여기에 연결할 것입니다. 질의 Gate 구현과 Circuit의 나머지 부분을 시각적으로 구분하기 위해 배리어가 포함되어 있습니다.

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in Deutsch's algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)

    qc.x(n)
    qc.h(range(n + 1))

    qc.barrier()
    qc.compose(function, inplace=True)
    qc.barrier()

    qc.h(range(n))
    qc.measure(range(n), range(n))

    return qc

마찬가지로 draw 메서드를 사용하면 Circuit이 어떻게 생겼는지 확인할 수 있습니다.

display(compile_circuit(deutsch_function(3)).draw(output="mpl"))

마지막으로, 앞서 정의한 Circuit을 한 번 실행하고 적절한 결과인 "constant" 또는 "balanced"를 출력하는 함수를 만들겠습니다.

def deutsch_algorithm(function: QuantumCircuit):
    # Determine if a one-bit function is constant or balanced.

    qc = compile_circuit(function)

    result = AerSimulator().run(qc, shots=1, memory=True).result()
    measurements = result.get_memory()
    if measurements[0] == "0":
        return "constant"
    return "balanced"

이제 위에서 정의한 네 가지 함수 중 어느 것에 대해서든 도이치 알고리즘을 실행할 수 있습니다.

f = deutsch_function(3)
display(deutsch_algorithm(f))

'balanced'