장 24 양자 회로

이제 큐비트에 대해 논의했으므로, 이를 회로에서 사용하는 방법에 대해 이야기할 수 있습니다. 핵심적인 변화 — 그리고 양자 회로가 고전 회로로는 할 수 없는 일을 할 수 있는 이유 — 는 우리가 $0$ 과 $1$ 의 선형 결합을 허용한다는 사실입니다.

24.1 고전 논리 게이트

고전 논리에서는 몇 개의 비트를 입력으로 받아 몇 개의 비트를 출력으로 내놓는 회로를 만듭니다. 이러한 회로는 개별 논리 게이트들로 구성됩니다. 예를 들어, AND 게이트는 다음과 같이 그림으로 나타낼 수 있습니다.

AND 게이트는 “진리표”를 사용해서도 나타낼 수 있습니다:

\begin{array}[]{|cc|c|}\hline\cr A&B&A\text{그리고}B\\ \hline\cr 0&0&0\\ 0&1&0\\ 1&0&0\\ 1&1&1\\ \hline\cr\end{array}

마찬가지로, OR 게이트와 NOT 게이트가 있습니다:

\begin{array}[]{|cc|c|}\hline\cr A&B&A\text{또는}B\\ \hline\cr 0&0&0\\ 0&1&1\\ 1&0&1\\ 1&1&1\\ \hline\cr\end{array}\qquad\begin{array}[]{|c|c|}\hline\cr A&\text{부정}A\\ \hline\cr 0&1\\ 1&0\\ \hline\cr\end{array}

또한 비트를 복제하는, 이른바 COPY 게이트도 있습니다.

물론, 이러한 게이트들에 대해 배우게 되는 첫 번째 정리는 다음과 같습니다:

정리 24.1.1 (AND, OR, NOT, COPY는 보편적입니다).

AND, OR, NOT, COPY라는 네 개의 게이트 집합은, 임의의 불 함수 $f\colon\{0,1\}^{n}\to\{0,1\}$ 을 오직 이 게이트들만을 사용한 회로로 구현할 수 있다는 의미에서 보편적입니다.

증명.

다소 시시하긴 하지만: 본질적으로 $f^{\text{pre}}(1)$ 에 속하는 모든 입력 문자열에 대해 OR를 취하는 회로를 적어 내려가면 됩니다. 예를 들어, $n=3$ 이고 $f(011)=f(110)=1$ 이며 나머지는 $0$ 인 함수 $f(abc)$ 를 시뮬레이션하고자 한다고 합시다. 그러면 $f$ 에 대응하는 불 표현식은 단순히 다음과 같습니다

f(abc)=\left[\text{($a$가 아님) 그리고 $b$ 그리고 $c$}\right]\text{또는}\left[\text{$a$ 그% 리고 $b$ 그리고 ($c$가 아님)}\right].

분명히, 다른 어떤 $f$ 에 대해서도 같은 방식을 적용할 수 있으며, 이 논리를 회로로 구현할 수 있습니다. ∎

비고 24.1.2.

$x\text{그리고}y=\text{부정}((\text{$x$가 아님})\text{또는}(\text{$y$ 아님}))$ 이므로, 실제로 AND 게이트를 없앨 수 있다는 결론이 따릅니다.

24.2 가역 고전 논리

대표적인 예: CNOT 게이트, Toffoli 게이트.

양자역학의 목적을 위해서는, 이것만으로는 충분하지 않습니다. 이 유비를 끝까지 이어가려면, 사실 가역인 게이트가 필요합니다. 즉 이 게이트들이 입력 공간에서 출력 공간으로 가는 전단사여야 한다는 뜻입니다. 특히, 그러한 게이트는 입력 비트 수와 출력 비트 수가 같아야 합니다.

예제 24.2.1 (가역 게이트).

(a)

AND, OR, COPY 게이트는 차원상의 이유로 모두 가역이 아닙니다.
(b)

그러나 NOT 게이트는 가역입니다: 이는 $\{0,1\}\to\{0,1\}$ 인 전단사입니다.

예제 24.2.2 (CNOT 게이트).

제어형-NOT 게이트, 즉 CNOT 게이트는 다음과 같은 진리표를 갖는 가역 $2$ 비트 게이트입니다.

\begin{array}[]{|rr|rr|}\hline\cr\vrule\lx@intercol\hfil\text{입력}\hfil% \lx@intercol\vrule\lx@intercol&\vrule\lx@intercol\hfil\text{출력}\hfil% \lx@intercol\vrule\lx@intercol\\ \hline\cr 0&0&0&0\\ 1&0&1&1\\ 0&1&0&1\\ 1&1&1&0\\ \hline\cr\end{array}

다시 말해, 이 게이트는 첫 번째 비트는 그대로 둔 채 두 번째 비트에 첫 번째 비트를 XOR합니다. 이는 다음과 같이 나타낼 수 있습니다.

첫 번째 점은 “제어(control)”라고 불리며, $\oplus$ 는 “부정(negation)” 연산입니다: 첫 번째 비트가 두 번째 비트를 뒤집을지 말지를 제어합니다. 따라서 전형적인 적용 예는 다음과 같을 수 있습니다.

그러므로, 두 비트에 대한 자명하지 않은 가역 게이트는 NOT과 CNOT뿐입니다.

이제 우리의 가역 게이트에 대해 보편적이라는 개념을 다르게 정의할 필요가 있습니다.

정의 24.2.3.

가역 게이트들의 집합이 불 함수 $f(x_{1}\dots x_{n})$ 을 시뮬레이션할 수 있다는 것은, 다음을 받아들이는 회로를 구현할 수 있는 경우를 말합니다

•

입력으로, $x_{1}\dots x_{n}$ 과 더불어 $0$ 또는 $1$ 로 고정된 몇몇 비트를 사용하는데, 이를 보조 비트¹¹1영어 단어 ”ancilla”는 ”하녀”를 의미합니다.라고 부릅니다.
•

출력으로는, 입력 비트 $x_{1},\dots,x_{n}$ 과 출력 비트 $f(x_{1},\dots,x_{n})$ , 그리고 경우에 따라 몇몇 추가 비트(이를 쓰레기 비트라고 부릅니다)가 있습니다.

어떤 임의의 불리언 함수든 시뮬레이션할 수 있다면 그 게이트(들)를 보편적이라고 합니다.

예를 들어, CNOT 게이트는 단 하나의 보조 비트 $1$ 을 사용하여 다음 회로에 따라 NOT 게이트를 시뮬레이션할 수 있습니다.

안타깝게도, 이는 보편적이지 않습니다.

명제 24.2.4 (CNOT $\not\Rightarrow$ AND).

CNOT 게이트는 불리언 함수 ” $x\text{그리고}y$ ”를 시뮬레이션할 수 없습니다.

증명 스케치.

CNOT 게이트만을 사용하여 시뮬레이션되는 어떤 함수든 다음 형태여야 함을 알 수 있습니다

a_{1}x_{1}+a_{2}x_{2}+\dots+a_{n}x_{n}\pmod{2}

왜냐하면 CNOT은 사상 $(x,y)\mapsto(x,x+y)$ 이기 때문입니다. 따라서 보조 비트를 사용하더라도, 고정된 $a$ , $b$ , $c$ 에 대해 $ax+by+c\pmod{2}$ 형태의 함수만 만들 수 있습니다. AND 게이트는 이 형태가 아닙니다. ∎

그러므로, 최소한 3-큐비트 게이트가 필요합니다. 가장 흔히 사용되는 것은 다음과 같습니다:

정의 24.2.5.

CCNOT 게이트라고도 불리는 3비트 토폴리 게이트는 다음과 같이 주어집니다

그래서 토폴리 게이트는 두 개의 제어 비트를 가지며, 두 제어 비트가 모두 $1$ 일 때에만 마지막 비트를 뒤집습니다.

이 대체로 충분합니다.

정리 24.2.6 (토폴리 게이트는 보편적입니다).

토폴리 게이트는 보편적입니다.

증명.

우리는 토폴리 게이트가 AND, NOT을 가역적으로 시뮬레이션할 수 있고, 따라서 OR도 시뮬레이션할 수 있음을 보일 것인데, 이는 보편성을 보이기에 충분함을 우리는 알고 있습니다. (가역성 덕분에 COPY는 필요하지 않습니다.)

AND 게이트에 대해서는, 다음 회로를 그립니다

하나의 보조 비트를 사용하며, 쓰레기 비트는 없습니다.

NOT 게이트에 대해서는, 두 개의 보조 비트 $1$ 과 하나의 쓰레기 비트를 사용합니다:

이로써 증명이 완료됩니다. ∎

따라서 이론적으로는 토폴리 게이트만을 사용하여 우리가 원하는 어떤 고전 회로든 만들 수 있습니다. 물론, 이는 가장 단순한 함수에 대해서조차 지수적으로 많은 게이트를 필요로 할 수 있습니다. 다행히도, 이는 전혀 문제가 되지 않는데, 왜냐하면 저는 수학 전공자이고, $2^{n}$ 개의 게이트를 갖는 문제는 컴퓨터공학 전공자들에게 맡겨두는 것이 가장 좋은 문제이기 때문입니다.

24.3 양자 논리 게이트

양자역학에서는 기저 원소들의 선형결합을 가질 수 있기 때문에, 우리의 논리 게이트는 대신 선형 사상으로 구성될 것입니다. 더욱이, 양자 계산에서는 게이트가 항상 가역적인데, 이것이 바로 앞 절에서 우리가 시간을 들여 가역 게이트로 제한하더라도(예를 들어 토폴리 게이트를 사용하여) 여전히 어떤 함수든 시뮬레이션할 수 있음을 보인 이유입니다.

먼저, 몇 가지 선형대수 내용입니다:

정의 24.3.1.

$V$ 를 유한 차원 내적 공간이라 합시다. 그러면 사상 $U\colon V\to V$ 에 대해, 다음은 서로 동치입니다:

•

$x,y\in V$ 에 대해 $\left<U(x),U(y)\right>=\left<x,y\right>$ 입니다.
•

$U^{\dagger}$ 는 $U$ 의 역원입니다.
•

$x\in V$ 에 대해 $\left\lVert x\right\rVert=\left\lVert U(x)\right\rVert$ 입니다.

사상 $U$ 가 이 동치인 조건들을 만족하면 유니터리라고 부릅니다.

그러면

양자 논리 게이트는 유니터리 행렬입니다.

특히, 고전적인 상황과 달리 양자 게이트는 항상 가역적입니다(따라서 입력 비트와 출력 비트의 개수가 항상 같습니다).

예를 들어 CNOT 게이트를 생각해봅시다. 이것의 양자 유사체는 유니터리 사상 $U_{\mathrm{CNOT}}\colon H\to H$ 여야 하며, 여기서 $H=\mathbb{C}^{\oplus 2}\otimes\mathbb{C}^{\oplus 2}$ 이고, 기저 원소들에 대해 다음과 같이 주어집니다.

U_{\mathrm{CNOT}}(\ket{00})=\ket{00},\quad U_{\mathrm{CNOT}}(\ket{01})=\ket{01}

U_{\mathrm{CNOT}}(\ket{10})=\ket{11},\quad U_{\mathrm{CNOT}}(\ket{11})=\ket{10}.

그림으로 나타내면 양자 CNOT 게이트는 다음과 같이 주어집니다.

그래서 어떻다는 말입니까? 양자역학의 요점 전체는 선형 큐비트가 $\ket{0}$ 과 $\ket{1}$ 의 선형결합 상태에 있는 것도 허용한다는 것이며, 이는 흥미로운 결과를 만들어냅니다. 예를 들어 $\ket{\leftarrow}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$ 을 취해 위쪽에 넣고 아래쪽에는 $\ket{1}$ 을 넣어 어떤 일이 일어나는지 살펴봅시다.

U_{\mathrm{CNOT}}\left(\ket{\leftarrow}\otimes\ket{1}\right)=U_{\mathrm{CNOT}}% \left(\frac{1}{\sqrt{2}}(\ket{01}-\ket{11})\right)=\frac{1}{\sqrt{2}}\left(% \ket{01}-\ket{10}\right)=\ket{\Psi_{-}}

이것은 완전히 얽힌 단일항 상태입니다! 그림:

따라서 혼합 상태를 양자 게이트에 입력하면, 원래 입력이 얽혀 있지 않더라도 출력은 종종 얽힌 상태가 됩니다.

예제 24.3.2 (양자 게이트의 더 많은 예시).

(a)

이전에 접했던 모든 가역 고전 게이트는 CNOT과 같은 방식, 즉 기저 원소들에 대한 값을 지정함으로써 얻어지는 양자 유사체를 가집니다. 예를 들어 양자 토폴리 게이트가 있는데, 이는 예컨대 다음을 보냅니다.
(b)

한 큐비트에 대한 아다마르 게이트는 다음과 같이 주어지는 회전입니다.

$\begin{bmatrix}\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}\end{bmatrix}.$

따라서 이는 $\ket{0}$ 을 $\ket{\rightarrow}$ 으로, $\ket{1}$ 을 $\ket{\leftarrow}$ 으로 보냅니다. 아다마르 게이트는 그 자신의 역원임에 유의하십시오. 이것은 ” $H$ ” 상자로 표시됩니다.
(c)

더 일반적으로, $U$ 가 $2\times 2$ 유니터리 행렬(즉, 사상 $\mathbb{C}^{\oplus 2}\to\mathbb{C}^{\oplus 2}$ )이라면, 이전 것과 유사한 $U$ -회전 게이트가 있으며, 이는 입력에 $U$ 를 적용합니다.

예를 들어 고전 NOT 게이트는 $U=\sigma_{x}$ 로 표현됩니다.
(d)

제어형 $U$ -회전 게이트는 CNOT 게이트를 일반화합니다. $U\colon\mathbb{C}^{\oplus 2}\to\mathbb{C}^{\oplus 2}$ 를 회전 게이트라 하고, $H=\mathbb{C}^{\oplus 2}\otimes\mathbb{C}^{\oplus 2}$ 를 $2$ -큐비트 공간이라 합시다. 그러면 제어형 $U$ 게이트는 다음과 같은 회로도를 가집니다.

따라서 제어 비트가 $1$ 일 때 $U$ 가 적용되며, CNOT은 $U=\sigma_{x}$ 인 특수한 경우입니다. 이전과 마찬가지로, 제어가 혼합 상태이면 흥미로운 동작을 얻게 됩니다.

그리고 이제, 좀 더 직관에 반하는 양자적 동작을 살펴봅시다. CNOT을 다음과 같은 진리표를 가진 복사기로 사용하려 한다고 가정합시다.

\begin{array}[]{|rr|rr|}\hline\cr\vrule\lx@intercol\hfil\text{입력}\hfil% \lx@intercol\vrule\lx@intercol&\vrule\lx@intercol\hfil\text{출력}\hfil% \lx@intercol\vrule\lx@intercol\\ \hline\cr 0&0&0&0\\ 1&0&1&1\\ 0&1&0&1\\ 1&1&1&0\\ \hline\cr\end{array}

이 게이트의 요점은 아래쪽에 쓰레기값 $0$ 을 넣어 ”복사” 연산을 시뮬레이션하려는 데 있습니다. 실제로 다음을 확인할 수 있습니다.

따라서 우리는 $\ket{0}$ 과 $\ket{1}$ 을 복사할 수 있습니다. 하지만 이미 보았듯이 $\ket{\leftarrow}\otimes\ket{0}$ 을 $U$ 에 입력하면, 우리가 원했던 $\ket{\leftarrow}\otimes\ket{\leftarrow}$ 이 결코 아닌 얽힌 상태 $\ket{\Psi_{-}}$ 를 얻게 됩니다. 그리고 실제로 이른바 복제 불가 정리는 임의의 $\ket{\psi}$ 를 복제하는 것이 불가능함을 함의합니다. 우리가 할 수 있는 최선은 고전적인 경우처럼 특정한 직교 상태들을 복사하는 것뿐입니다. 문제 24B도 참조하십시오.

24.4 도이치-조사 알고리즘

도이치-조사 알고리즘은 고전적으로 수행할 수 없는 자명하지 않은 양자 알고리즘의 첫 번째 예시로, 이는 훗날 그로버의 탐색 알고리즘과 쇼어의 소인수분해 알고리즘에 영감을 준 ”개념 증명”입니다.

문제는 다음과 같습니다: 함수 $f\colon\{0,1\}^{n}\to\{0,1\}$ 가 주어졌고, 함수 $f$ 가 다음 중 하나임이 보장됩니다.

•

상수 함수이거나, 혹은
•

균형 함수, 즉 정확히 절반의 입력이 $0$ 으로, 절반의 입력이 $1$ 로 대응되는 함수입니다.

함수 $f$ 는 NOT 게이트의 제어인 가역 블랙박스 $U_{f}$ 의 형태로 주어지며, 따라서 다음과 같은 회로 도식으로 나타낼 수 있습니다.

즉, $f(x_{1},\dots,x_{n})=0$ 이면 게이트는 아무 일도 하지 않으며, 그렇지 않으면 게이트는 아래쪽의 $y$ 비트를 뒤집습니다. $n$ 이 붙은 슬래시는 입력의 위쪽이 실제로는 그려진 하나의 큐비트가 아니라 $n$ 개의 큐비트로 이루어져 있음을 나타내며, 따라서 블랙박스 $U_{f}$ 는 $n+1$ 개의 큐비트에 대한 사상입니다.

문제는 블랙박스 $U_{f}$ 에 대한 호출을 가능한 한 적게 사용하여 $f$ 가 균형인지 상수인지를 판별하는 것입니다.

질문 24.4.1.

고전적으로는, 최악의 경우 질문에 답하기 위해 함수 $f$ 에 대한 호출이 최대 $2^{n-1}+1$ 번까지 필요할 수 있음을 보이십시오.

따라서 고전적인 도구만으로는 $f$ 가 균형인지 상수인지를 판별하는 데 $O(2^{n})$ 번의 질의가 필요합니다. 하지만,

정리 24.4.2 (도이치-조사).

도이치-조사 문제는 블랙박스에 대한 단 한 번의 호출만으로 양자 회로에서 판별할 수 있습니다.

증명.

구체성을 위해 $n=1$ 인 경우를 명시적으로 다루겠습니다; 일반적인 경우는 문제 24C에 포함되어 있습니다. 필요한 회로는 다음과 같음을 주장합니다.

여기서 $H$ 들은 아다마르 게이트이며, 맨 오른쪽 선 끝의 계측기는 통상적인 $\ket{0}$ , $\ket{1}$ 기저를 따라 측정을 수행함을 나타냅니다. 이는 오타가 아닙니다! 고전적으로는 위쪽 선이 단지 입력 정보를 반복하는 것에 불과하지만, 우리가 측정하고자 하는 것이 바로 이 위쪽임을 곧 보게 될 것입니다.

두 번의 아다마르 연산 이후 얻어지는 상태는 다음과 같음에 주목하십시오.

	$\displaystyle\ket{01}$	$\displaystyle\xmapsto{H^{\otimes 2}}\left(\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})% \right)\otimes\left(\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})\right)$
		$\displaystyle=\frac{1}{2}\Big{(}\ket{0}\otimes\big{(}\ket{0}-\ket{1}\big{)}\;+% \;\ket{1}\otimes\big{(}\ket{0}-\ket{1}\big{)}\Big{)}.$

따라서 $U_{f}$ 를 적용한 후, 우리는 다음을 얻습니다.

\frac{1}{2}\Big{(}\ket{0}\otimes\big{(}\ket{0+f(0)}-\ket{1+f(0)}\big{)}\;+\;% \ket{1}\otimes\big{(}\ket{0+f(1)}-\ket{1+f(1)}\big{)}\Big{)}

여기서 모듈로 $2$ 는 암묵적으로 생략되었습니다. 이제, $\ket{0}-\ket{1}$ 에서 $\ket{0+f(x)}-\ket{1+f(x)}$ 로 넘어가는 것의 효과는 단지 상태를 그대로 유지하거나( $f(x)=0$ 인 경우) 부호를 반전시키는( $f(x)=1$ 인 경우) 것에 불과함을 관찰하십시오. 따라서 우리는 다음과 같이 단순화하고 인수분해할 수 있습니다.

\frac{1}{2}\left((-1)^{f(0)}\ket{0}+(-1)^{f(1)}\ket{1}\right)\otimes\left(\ket% {0}-\ket{1}\right).

따라서, 지금까지의 그림은 다음과 같습니다:

특히, 결과 상태는 얽혀 있지 않으며, 우리는 단순히 마지막 큐비트를 버릴 수 있습니다(!). 이제 다음을 관찰하십시오:

•

$f$ 가 상수이면, 가장 위쪽 상태는 $\pm\ket{\rightarrow}$ 입니다.
•

$f$ 가 균형이면, 가장 위쪽 상태는 $\pm\ket{\leftarrow}$ 입니다.

따라서 단순히 $\sigma_{x}$ 를 따라 측정하는 것만으로 답을 얻을 수 있습니다. 이와 동등하게, $H$ 게이트를 한 번 더 적용하여( $H\ket{\rightarrow}=\ket{0}$ , $H\ket{\leftarrow}=\ket{1}$ 이 되도록) 통상적인 $\ket{0}$ , $\ket{1}$ 기저에서 $\sigma_{z}$ 를 따라 측정할 수 있습니다. 따라서 $n=1$ 인 경우 오라클에 대한 호출이 단 한 번만 필요합니다. ∎

24.5 생각해 볼 만한 조금 더 어려운 문제

문제 24A (프레드킨 게이트).

프레드킨 게이트(제어 스왑, 즉 CSWAP 게이트라고도 불림)는 다음과 같은 진리표를 갖는 3비트 게이트입니다.

\begin{array}[]{|rrr|rrr|}\hline\cr\vrule\lx@intercol\hfil\text{입력}\hfil% \lx@intercol\vrule\lx@intercol&\vrule\lx@intercol\hfil\text{출력}\hfil% \lx@intercol\vrule\lx@intercol\\ \hline\cr 0&0&0&0&0&0\\ 0&0&1&0&0&1\\ 0&1&0&0&1&0\\ 0&1&1&0&1&1\\ 1&0&0&1&0&0\\ 1&0&1&1&1&0\\ 1&1&0&1&0&1\\ 1&1&1&1&1&1\\ \hline\cr\end{array}

따라서 이 게이트는 첫 번째 비트가 $1$ 일 때마다 마지막 두 입력 비트를 교환합니다. 이 게이트 역시 가역적이며 보편적임을 보이십시오.

힌트. 한 가지 방법은 몇 개의 프레드킨 게이트를 사용하여 CCNOT을 만드는 것입니다.

풀이. 프레드킨 게이트가 보편적임을 보이려면 이를 이용해 가역적으로 CCNOT 게이트를 만드는 것으로 충분합니다. 다음과 같이 시스템을 씁니다

$\displaystyle(z,\neg z,-)$ $\displaystyle=\operatorname{Fred}(z,1,0)$

$\displaystyle(x,a,-)$ $\displaystyle=\operatorname{Fred}(x,1,0)$

$\displaystyle(y,b,-)$ $\displaystyle=\operatorname{Fred}(y,a,0)$

$\displaystyle(-,c,-)$ $\displaystyle=\operatorname{Fred}(b,0,1)$

$\displaystyle(-,d,-)$ $\displaystyle=\operatorname{Fred}(c,z,\neg z).$

직접 계산하면 $d=z+xy\pmod{2}$ 임을 알 수 있습니다.

문제 24B (기본적인 복제 불가 정리).

두 큐비트 위의 유니터리 사상 $U$ 중 임의의 큐비트 $\ket{\psi}$ 에 대해 $U(\ket{\psi}\otimes\ket{0})=\ket{\psi}\otimes\ket{\psi}$ 를 보내는 것이 존재하지 않음을 보이십시오. 즉, 다음의 회로 도식이 불가능함을 보이십시오.

힌트. $\ket{\psi}=\ket{0}$ , $\ket{\psi}=\ket{1}$ , $\ket{\psi}=\ket{\rightarrow}$ 를 대입하여 모순을 이끌어내십시오.

문제 24C (도이치-조사).

도이치-조사 알고리즘에서 설명한 블랙박스 $U_{f}$ 가 주어졌을 때, 다음 회로를 고려합니다.

즉, $\ket{0}$ 의 $n$ 개 사본을 취하여 이들 모두에 아다마르 회전을 적용하고, $U_{f}$ 를 적용한 후, $n$ 개의 입력 비트 모두에 아다마르를 역으로 적용하고(마지막 비트는 다시 버림), 그런 다음 $n$ 개의 비트 전부를 $\ket{0}$ / $\ket{1}$ 기저에서 측정합니다(예제 23.4.4에서와 같이).

$f$ 가 상수 함수이면 $\ket{0\dots 0}$ 을 측정할 확률이 $1$ 이고, $f$ 가 균형 함수이면 $0$ 임을 보이십시오.

힌트. 먼저 이 상자가 $\ket{x_{1}}\otimes\dots\otimes\ket{x_{n}}\otimes\ket{\leftarrow}$ 을 $(-1)^{f(x_{1},\dots,x_{n})}(\ket{x_{1}}\otimes\dots\otimes\ket{x_{n}}\otimes% \ket{\leftarrow})$ 으로 보냄을 보이십시오.

풀이. $\ket{\leftarrow}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$ 로 둡니다. 그러면 $U_{f}$ 가 다음과 같이 보냄을 알 수 있습니다

$\ket{x_{1}}\dots\ket{x_{n}}\ket{0}-\ket{x_{1}}\dots\ket{x_{n}}\ket{1}\xmapsto{% U_{f}}\pm\ket{x_{1}}\dots\ket{x_{n}}\ket{0}\mp\ket{x_{1}}\dots\ket{x_{n}}\ket{1}$

부호는 $f(x_{1},\dots,x_{n})=1$ 일 때 정확히 $+$ , $-$ 가 됩니다.

이제 $\ket{0}\dots\ket{0}\ket{1}$ 을 입력하면, $H^{\otimes n+1}$ 이 이를 다음으로 사상함을 알 수 있습니다

$2^{-n/2}\sum_{x_{1},\dots,x_{n}}\ket{x_{1}}\dots\ket{x_{n}}\ket{\leftarrow}.$

그러면 $U_{f}$ 아래에서의 상은 다음과 같습니다

$2^{-n/2}\sum_{x_{1},\dots,x_{n}}(-1)^{f(x_{1},\dots,x_{n})}\ket{x_{1}}\dots% \ket{x_{n}}\ket{\leftarrow}.$

이제 마지막 큐비트를 버리면 다음이 남습니다

$2^{-n/2}\sum_{x_{1},\dots,x_{n}}(-1)^{f(x_{1},\dots,x_{n})}\ket{x_{1}}\dots% \ket{x_{n}}.$

여기에 $H^{\otimes n}$ 을 적용하면 다음을 얻습니다

$2^{-n/2}\sum_{x_{1},\dots,x_{n}}(-1)^{f(x_{1},\dots,x_{n})}\cdot\left(2^{-n/2}% \sum_{y_{1},\dots,y_{n}}(-1)^{x_{1}y_{1}+\dots+x_{n}y_{n}}\ket{y_{1}}\ket{y_{2% }}\dots\ket{y_{n}}\right)$

$H\ket{0}=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$ 이고 $H\ket{1}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$ 이므로, $x_{i}=1$ 이고 $y_{i}=1$ 이 동시에 성립할 때 정확히 음의 부호가 나타나며, 따라서 $(-1)^{x_{1}y_{1}+\dots+x_{n}y_{n}}$ 항이 생깁니다. 합의 순서를 바꾸면 다음을 얻습니다

$2^{-n}\sum_{y_{1},\dots,y_{n}}C(y_{1},\dots,y_{n})\ket{y_{1}}\ket{y_{2}}\dots% \ket{y_{n}}$

여기서 $C(y_{1},\dots,y_{n})=\sum_{x_{1},\dots,x_{n}}(-1)^{f(x_{1},\dots,x_{n})+x_{1}y% _{1}+\dots+x_{n}y_{n}}$ 입니다. 이제 마지막으로 두 경우를 고려합니다.

•

$f$ 가 상수 함수라면, 다음을 알 수 있습니다

$C(y_{1},\dots,y_{n})=\begin{cases}\pm 1&y_{1}=\dots=y_{n}=0\\ 0&\text{그 외의 경우}.\end{cases}$

이를 확인하려면, $y_{1}=\dots=y_{n}=0$ 인 경우 결과가 명백함에 주목하십시오. 그렇지 않고 일반성을 잃지 않고 $y_{1}=1$ 이라 하면, $x_{1}=0$ 에 대한 항들이 쌍을 이루어 $x_{1}=1$ 에 대한 항들과 정확히 상쇄됩니다. 따라서 이 상태에서는 측정 결과가 모두 $\ket{0}\dots\ket{0}$ 이 됩니다.

•

반면 $f$ 가 균형 함수라면, 다음을 유도할 수 있습니다

$C(0,\dots,0)=0.$

따라서 측정 결과가 $\ket{0}\dots\ket{0}$ 이 되는 경우는 전혀 없습니다.

이런 방식으로 $f$ 가 균형 함수인지 아닌지를 알 수 있습니다.

문제 24D (Barenco et al, 1995; arXiv:quant-ph/9503016v1).

다음과 같다고 합시다

P=\begin{bmatrix}1&0\\ 0&i\end{bmatrix}\qquad Q=\frac{1}{\sqrt{2}}\begin{bmatrix}1&-i\\ -i&1\end{bmatrix}

양자 토폴리 게이트가 다음 회로를 통해 제어 회전만으로 구현될 수 있음을 확인하십시오

이는 발견 당시 연구자들에게 큰 놀라움을 주었는데, 고전적인 가역 논리는 3비트 게이트(예: 토폴리, 프레드킨)를 필요로 하기 때문입니다.

힌트. 이는 직접 계산입니다.

	$\displaystyle(z,\neg z,-)$	$\displaystyle=\operatorname{Fred}(z,1,0)$
	$\displaystyle(x,a,-)$	$\displaystyle=\operatorname{Fred}(x,1,0)$
	$\displaystyle(y,b,-)$	$\displaystyle=\operatorname{Fred}(y,a,0)$
	$\displaystyle(-,c,-)$	$\displaystyle=\operatorname{Fred}(b,0,1)$
	$\displaystyle(-,d,-)$	$\displaystyle=\operatorname{Fred}(c,z,\neg z).$