장 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 게이트, 토폴리 게이트.

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

예제 24.2.1 (가역 게이트).

(a)

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

그러나 NOT 게이트는 가역적입니다. 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합니다. 이 게이트는 다음과 같이 나타냅니다.

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

따라서 두 비트에 작용하는 자명하지 않은 가역 게이트는 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$ 가 이 동치 조건들을 만족하면 $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}$ 은 복사할 수 있습니다. 그러나 이미 보았듯이 $U$ 에 $\ket{\leftarrow}\otimes\ket{0}$ 을 입력하면 얽힌 상태 $\ket{\Psi_{-}}$ 가 나오며, 이는 우리가 원했던 $\ket{\leftarrow}\otimes\ket{\leftarrow}$ 이 결코 아닙니다. 실제로 이른바 복제 불가 정리에 따르면 임의의 $\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 (Deutsch-Jozsa).

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

증명.

구체적으로 보이기 위해 $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 (기초적인 복제 불가 정리).

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

힌트. $\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 외, 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).$