[Note] Quantum Computation and Quantum Information - Chapter 4: Quantum Circuits

上課筆記，原文書:

Quantum Computation and Quantum Information, Michael A. Nielsen & Isaac L. Chuang

4.1 Quantum algorithm

There are mainly two classes of algorithms:

1. Based on Shor’s quantum Fourier transform, e.g. shor’s algorithm (factoring)
   • exponential speedup
2. Based upon Grover’s algorithm (search algorithm)
   • quadratic speedup

4.2 Single qubit operations

A single qubit: $\vert \psi\rangle=a\vert0\rangle+b\vert1\rangle$, where $a,b \in \mathbb{C}$ and $\vert a\vert^2+\vert b\vert^2=1$.

Quantum gates (operations):

• Pauli matrices: $$X\equiv\left[\begin{matrix} 0 & 1\\ 1 & 0 \end{matrix}\right];\quad Y\equiv\left[\begin{matrix} 0 & -i\\ i & 0 \end{matrix}\right];\quad Z\equiv\left[\begin{matrix} 1 & 0\\ 0 & -1 \end{matrix}\right]$$
• Hadamard gate: $$H\equiv\frac{1}{\sqrt{2}}\left[\begin{matrix} 1 & 1\\ 1 & -1 \end{matrix}\right]=(X+Z)/\sqrt{2}$$
• Phase gate: $$S\equiv\left[\begin{matrix} 1 & 0\\ 0 & i \end{matrix}\right]=T^2$$
• $\pi/8$ gate: $$T\equiv\left[\begin{matrix} 1 & 0\\ 0 & \exp(i\pi/4) \end{matrix}\right]= \exp(i\pi/8)\left[\begin{matrix} \exp(-i\pi/8) & 0\\ 0 & \exp(i\pi/8) \end{matrix}\right]$$

Bloch sphere representation:

• A single qubit can be visualized as a point $(\theta, \varphi)$ on the unit sphere. $$\vert \psi\rangle = \cos(\theta/2)\vert 0\rangle + e^{i\varphi}\sin(\theta/2)\vert 1\rangle\$$
• Bloch vector: $(\cos\varphi\sin\theta, \sin\varphi\sin\theta, \cos\theta)$

Exponentiating Pauli matrices gives rotation operators about the $\hat{x}$, $\hat{y}$ and $\hat{z}$ axes:

$$\begin{align*} R_x(\theta) &\equiv e^{-i\theta X/2}=\cos\frac{\theta}{2}I-i\sin\frac{\theta}{2}X=\left[\begin{matrix} \cos\frac{\theta}{2} & -i\sin\frac{\theta}{2}\\ -i\sin\frac{\theta}{2} & \cos\frac{\theta}{2} \end{matrix}\right]\\ R_y(\theta) &\equiv e^{-i\theta Y/2}=\cos\frac{\theta}{2}I-i\sin\frac{\theta}{2}Y=\left[\begin{matrix} \cos\frac{\theta}{2} & -\sin\frac{\theta}{2}\\ \sin\frac{\theta}{2} & \cos\frac{\theta}{2} \end{matrix}\right]\\ R_z(\theta) &\equiv e^{-i\theta Z/2}=\cos\frac{\theta}{2}I-i\sin\frac{\theta}{2}Z=\left[\begin{matrix} e^{-i\theta/2} & 0\\ 0 & e^{i\theta/2} \end{matrix}\right] \end{align*}$$

Exercise 4.2: Let $x$ be a real number and $A$ a matrix such that $A^2=I$. Show that

$$e^{iAx}=\cos(x)I +i\sin(x)A.$$

Proof: Recall that the taylor series

$$e^x=\sum^\infty_{n=0}\frac{x^n}{n!}, \quad\sin(x)=\sum^\infty_{n=0}\frac{(-1)^n}{(2n+1)!}x^{2n+1}, \quad\cos(x)=\sum^\infty_{n=0}\frac{(-1)^n}{(2n)!}x^{2n}$$

For $A^2=I$,

$$\begin{align*}e^{iAx}&=\sum_n\frac{(iAx)^n}{n!}=\sum_{n\in \text{even}}\frac{(ix)^n}{n!}I+\sum_{n\in\text{odd}}\frac{(ix)^n}{n!}A\\ &= \cos(x)I+i\sin(x)A\end{align*}$$

If $\hat{n}=(n_x,n_y, n_z)$ is a real unit vector in three dimensions then we generalize the previous definitions by defining a rotation by $\theta$ about the $\hat{n}$ axis by the equation

$$R_{\hat{n}}(\theta)\equiv e^{-i\theta\hat{n}\cdot\vec{\sigma}/2}=\cos\left(\frac{\theta}{2}\right)I-i\sin\left(\frac{\theta}{2}\right)(n_xX+n_yY+n_zZ),$$

where $\vec{\sigma}$ denotes the three component vector $(X,Y,Z)$ of Pauli matrices.

Operation function for diagonalizable matrix:
Let $A$ be an diagonalizable matrix $A=\sum_\lambda \lambda\vert \psi_\lambda\rangle\langle\psi_\lambda\vert$, an operation function $f: \mathbb{C}\to\mathbb{C}$. Then

$$f(A)=\sum_\lambda f(\lambda)\vert \psi_\lambda\rangle\langle\psi_\lambda\vert$$

For example, a diagonalizable matrix $Z=\vert 0\rangle\langle 0\vert - \vert 1\rangle\langle 1\vert=\left[\begin{matrix}1&0\\0&-1\end{matrix}\right]$, an operation function $f(x)=e^{\theta x}$. Then

$$f(Z)=e^{\theta Z}= e^\theta\vert 0\rangle\langle 0\vert + e^{-\theta}\vert 1\rangle\langle 1\vert=\left[\begin{matrix}e^\theta&0\\0&e^{-\theta}\end{matrix}\right].$$

For example, $f(x)=\sum_{n\ge0}a_nx^n$ (Taylor expantion).

$$\begin{align*} f(A) &= \sum_\lambda f(\lambda)\vert \psi_\lambda\rangle\langle \psi_\lambda\vert = \sum_\lambda\sum_n a_n\lambda^n\vert \psi_\lambda\rangle\langle\psi_\lambda\vert\\ &= \sum_n a_n\sum_\lambda \lambda^n\vert\psi_\lambda\rangle\langle\psi_\lambda\vert = \sum_n a_n A^n \end{align*}$$

Theorem 4.1: ($Z$-$Y$ decomposition for a single qubit) Suppose $U$ is a unitary operation on a single qubit. Then there exist real numbers $\alpha, \beta, \gamma$ and $\delta$ such that

$$U=e^{i\alpha}R_z(\beta)R_y(\gamma)R_z(\delta)$$

Proof: Let a unitary matrix $U=\left[\begin{matrix}a&c\\b&d\end{matrix}\right]$

$$\begin{align*}\vert a\vert^2+\vert b\vert^2=1 &\Rightarrow a\equiv e^{i\phi_1}\cos\frac{\gamma}{2},\quad b\equiv e^{i\phi_2}\sin\frac{\gamma}{2}\\\vert a\vert^2+\vert c\vert^2=1 &\Rightarrow c\equiv -e^{i\phi_3}\sin\frac{\gamma}{2}\\\vert c\vert^2+\vert d\vert^2=1 &\Rightarrow d\equiv e^{i\phi_4}\cos\frac{\gamma}{2}\\a^*c+b^*d=0 &\Rightarrow -e^{i(\phi_3-\phi_1)}+e^{i(\phi_4-\phi_2)}=0\\&\Rightarrow\phi_3-\phi_1=\phi_4-\phi_2\equiv \beta\end{align*}$$

Another independent variables:

$$\phi_1+\phi_3\equiv2\alpha-\delta,\quad \phi_2+\phi_4\equiv 2\alpha+\delta$$ $$\Rightarrow U=\left[ \begin{matrix}e^{i(\alpha-\beta/2-\delta/2)}\cos\frac{\gamma}{2} & -e^{i(\alpha-\beta/2+\delta/2)}\sin\frac{\gamma}{2}\\e^{i(\alpha+\beta/2-\delta/2)}\sin\frac{\gamma}{2} & e^{i(\alpha+\beta/2+\delta/2)}\cos\frac{\gamma}{2}\end{matrix}\right]$$

Corollery 4.2: Suppose $U$ is a unitary gate on a single qubit. Then there exist unitary operators $A$, $B$, $C$ on a single qubit such that $ABC=I$ and $U=e^{i\alpha}AXBXC$, where $\alpha$ is some overall phase factor.

Proof: For $Z$-$Y$ decomposition of $U$, $U=e^{i\alpha}R_z(\beta)R_y(\gamma)R_z(\delta)$. Let

$$\begin{align*}A &\equiv R_z(\beta)R_y(\frac{\gamma}{2})\\B &\equiv R_y(-\frac{\gamma}{2})R_z(\frac{-(\delta+\beta)}{2})\\C &\equiv R_z(\frac{\delta-\beta}{2})\end{align*}$$

Check that

$$\begin{align*}ABC &= R_z(\beta)R_y(\frac{\gamma}{2})R_y(-\frac{\gamma}{2})R_z(\frac{-(\delta+\beta)}{2})R_z(\frac{\delta-\beta}{2})\\ &= R_z(\beta)R_y(0)R_z(-\beta)\\ &= I\end{align*}$$

Let $f(x)=\sum_na_nx^n$, we show that $Xf(Y)X=f(-Y)$:

1. $XY=-YX~\Rightarrow XYX=-Y$
2. $Xf(Y)X=X\sum_na_nY^nX=\sum_n a_n(XYX)^n=\sum_na_n(-Y)^n=f(-Y)$

Similar for $Xf(Z)X=f(-Z)$. Then we have

$$XBX=XR_y(-\frac{\gamma}{2})XXR_z(-\frac{\delta+\beta}{2})X=R_y(\frac{\gamma}{2})R_z(\frac{\delta+\beta}{2})$$

Hence,

$$\begin{align*}e^{i\alpha} AXBXC &= e^{i\alpha}R_z(\beta)R_y(\frac{\gamma}{2})R_y(\frac{\gamma}{2})R_z(\frac{\delta+\beta}{2})R_z(\frac{\delta-\beta}{2})\\ &= e^{i\alpha}R_z(\beta)R_y(\gamma)R_z(\delta)\\ &= U\end{align*}$$

4.3 Controlled operations

• controlled operation: If $A$ is true, then do $B$.
• controlled-NOT (CNOT): If $c=1$, the target $\vert t\rangle$ flipped, $\vert c\rangle\vert t\rangle\to\vert c\rangle\vert t\oplus c\rangle$ $$\left[\begin{matrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 \end{matrix}\right]= \left[\begin{matrix} I & 0\\ 0 & X \end{matrix}\right]$$

• controlled-$U$: If $c=1$, apply unitary $U$ to the target $\vert t\rangle$. $\vert c\rangle\vert t\rangle\to\vert c\rangle U^c\vert t\rangle$. $$\left[\begin{matrix} I & 0\\ 0 & U \end{matrix}\right]$$

• controlled-$Z$: $$\left[\begin{matrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & -1 \end{matrix}\right]$$

• SWAP gate: $\vert a\rangle\vert b\rangle \to \vert b\rangle\vert a\rangle$ $$\left[\begin{matrix} 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 \end{matrix}\right]$$

• Toffoli gate (CCNOT):
  • Universal for classical circuit (but not for quantum circuit)
  • reversible
    

How to construct controlled-$U$ operation for arbitrary single qubit? By Corollary 4.2, $U=e^{i\alpha}AXBXC$:

1. Apply phase shift $e^{i\alpha}$:

   $$\vert 00\rangle \to \vert 00\rangle, \quad\vert 01\rangle\to\vert 01\rangle, \quad \vert 10\rangle\to e^{i\alpha}\vert 10\rangle, \quad \vert 11\rangle\to e^{i\alpha}\vert 11\rangle$$

   

2. (CNOT$=$controlled-$X$)

   • If $c=0$, $ABC=I$
   • If $c=1$, $e^{i\alpha}AXBXCX=U$
     

Conditioning multiple qubits: Suppose we have $n+k$ qubits, and $U$ is a $k$ qubit unitary operator. Then we define the controlled operation $C^n(U)$ by the eqution

$$C^n(U)\vert x_1x_2\dots x_n\rangle\vert \psi\rangle=\vert x_1x_2\dots x_n\rangle U^{x_1x_2\dots x_n}\vert\psi\rangle$$

4.4 Measurement

• Projective measurement in the computational basis
  • Any measurement can be constructed from adding ancilla qubits, performing a unitary, and followed by computational basis measurement.

Principle 1: Principle of deferred measurement
We can assume all measurements happens at the end of the circuit because you can always move a measurements in the middle of the circuit to the end, and replace classical controls of the measurement outcome with quantum control:

Principle 2: Principle of implicit measurement
We can assume that every quantum wire is measured in the end, because measuring “leftover” wires does not change thet reduced density matrix of the wires that give result.

Exercise 4.33: (Measurement in the Bell basis) Show that

Performs a measurement in the bell basis.

$$\begin{align*}(H\otimes I)CNOT &= (H\otimes I)(\vert 0\rangle\langle 0\vert \otimes I + \vert 1\rangle\langle 1 \vert\otimes X)\\ &= (\vert +\rangle\langle 0\vert \otimes I + \vert -\rangle\langle 1\vert X)\\ &= \frac{1}{\sqrt2}(\vert 0\rangle\langle 0\vert\otimes I + \vert 1\rangle\langle 0\vert\otimes I + \vert 0\rangle\langle 1\vert\otimes X - \vert 1\rangle\langle 1\vert\otimes X)\\ &= \frac{1}{\sqrt2}(\vert00\rangle(\langle00\vert+\langle11\vert)+\vert10\rangle(\langle00\vert-\langle11\vert)\\ & \quad\quad\quad\quad+\vert01\rangle(\langle01\vert+\langle10\vert)+\vert11\rangle(\langle01\vert-\langle10\vert))\end{align*}$$

Projective measurements:

$$\begin{align*}\vert 00\rangle\langle00\vert &\Rightarrow ((H\otimes I)CNOT)^\dagger \vert 00\rangle\langle00\vert (H\otimes I)CNOT \\ &= \frac{1}{2}(\vert00\rangle + \vert11\rangle)(\langle00\vert+\langle11\vert)\\ &= \vert\beta_{00}\rangle\langle\beta_{00}\vert\end{align*}$$ $$\begin{align*}\vert 01\rangle\langle01\vert &\Rightarrow ((H\otimes I)CNOT)^\dagger \vert 01\rangle\langle01\vert (H\otimes I)CNOT \\ &= \frac{1}{2}(\vert01\rangle + \vert10\rangle)(\langle01\vert+\langle10\vert)\\ &= \vert\beta_{10}\rangle\langle\beta_{10}\vert\end{align*}$$ $$\begin{align*}\vert 10\rangle\langle10\vert &\Rightarrow ((H\otimes I)CNOT)^\dagger \vert 10\rangle\langle10\vert (H\otimes I)CNOT \\ &= \frac{1}{2}(\vert00\rangle - \vert11\rangle)(\langle00\vert-\langle11\vert)\\ &= \vert\beta_{01}\rangle\langle\beta_{01}\vert\end{align*}$$ $$\begin{align*}\vert 11\rangle\langle11\vert &\Rightarrow ((H\otimes I)CNOT)^\dagger \vert 11\rangle\langle11\vert (H\otimes I)CNOT \\ &= \frac{1}{2}(\vert01\rangle - \vert10\rangle)(\langle01\vert-\langle10\vert)\\ &= \vert\beta_{11}\rangle\langle\beta_{11}\vert\end{align*}$$

4.5 Universal quantum gates

A set of gates is said to be universal for quantum computation if any unitary operation may be approximated to arbitary accuracy by a quantum circuit involving only those gates.

Three step constructions:

1. (exact) $\{\text{2-level unitaries}\}$ universal: an arbitrary unitary may be expressed as a product of unitary operators that each acts non-trivially only on a subspace spanned by two computational basis states.
2. (exact) $\{\text{all single qubit } U, CNOT\}$ universal: an arbitrary unitary from the first step may be expressed using single qubit and CNOT gates.
3. (approx) $\{H, T, CNOT\}$: single qubit operation from the second step may be approximated to arbitray accuracy using the Hadamard, phase, and $\pi/8$ gates ($T$). This implies that any unitary operation can be approximated to arbitrary accuracy using Hadamard, phase, CNOT, and $\pi/8$ gates.

4.5.1 Two-level unitary gates are universal

• Two-level unitary: unitary that only acts non-trivially on two computational basis. $$\left[\begin{matrix} \begin{matrix} a & c \\ b & d \end{matrix} & 0\\ 0 & I \end{matrix}\right] \quad ~\text{ or}~ \quad \left[\begin{matrix} \ddots&&&&0\\ &a&&c&\\ &&\ddots&&\\ &b&&d&\\ 0&&&&\ddots \end{matrix}\right]$$

Any unitary $U$ can be decomposed into two-level unitaries

Example: $U\in C^{3\times 3}$, $U=\left[\begin{matrix} a & d & g\ b & e & h\ c & f & j\end{matrix}\right]$, find two-level unitaries $U_1, U_2, U_3$ s.t. $U_3U_2U_1U=I\Rightarrow U=U_1^\dagger U_2^\dagger U_3^\dagger$.

Find $U_1$:

• If $b=0$, $U_1=I$,
• If $b\ne0$, $U_1=\left[\begin{matrix}\frac{a^*}{\sqrt{\vert a\vert^2+\vert b\vert^2}} & \frac{b^*}{\sqrt{\vert a\vert^2+\vert b\vert^2}} & 0\\\frac{b}{\sqrt{\vert a\vert^2+\vert b\vert^2}} & \frac{-a}{\sqrt{\vert a\vert^2+\vert b\vert^2}} & 0\\0&0&I\end{matrix}\right]$

$\Rightarrow U_1U=\left[\begin{matrix}a’&d’&g’\\0&e’&h’\\c’&f’&j’\end{matrix}\right]$

Find $U_2$:

• If $c’=0$, $U_2=\left[\begin{matrix}a’^\dagger & 0&0\\0&1&0\\0&0&1\end{matrix}\right]$
• If $c’\ne 0$, $U_2=\left[\begin{matrix} \frac{a’^*}{\sqrt{\vert a’\vert^2+\vert c’\vert^2}}&0&\frac{c’^*}{\sqrt{\vert a’\vert^2+\vert c’\vert^2}} \ 0&1&0\ \frac{c’}{\sqrt{\vert a’\vert^2+\vert c’\vert^2}}&0&\frac{-a’}{\sqrt{\vert a’\vert^2+\vert c’\vert^2}}\end{matrix}\right]$

$\Rightarrow U_2U_1U=\left[\begin{matrix}1&d’’&g’’\\0&e’’&h’’\\0&f’’&j’’\end{matrix}\right]=\left[\begin{matrix}1&0&0\\0&e’’&h’’\\0&f’’&j’’\end{matrix}\right]$, because $U_2U_1U$ is a unitary.

Find $U_3$:
$U_3=\left[\begin{matrix}1&0&0\\0&e’’^\dagger&f’’^\dagger\\0&h’’^\dagger&j’’^\dagger\end{matrix}\right]$

$\Rightarrow U_3U_2U_1U=I$
\
Proof. For general case, prove by induction.

• We can decompose $2\times 2$ U
• If we can decompose $(d-1)\times(d-1)$ unitaries, then given any $U\in C^{d\times d}$, we can find $U_1, \dots, U_{d-1}$ s.t. $U_{d-1}U_{d-2}\dots U_1U=\left[\begin{matrix}1&\begin{matrix}0&0&\cdots&0\end{matrix}\\\begin{matrix}0\\0\\\vdots\\0\end{matrix} & U’\end{matrix}\right]$. By assumption, we can decompose $U’$ because it is a $(d-1)\times(d-1)$ unitary $\Rightarrow$ We can decompose any $U\in C^{d\times d}$ i.e. $U=U_1U_2\cdots U_k$ where $\{U_i\}$ are two level unitaries (and $k\le \frac{d(d-1)}{2}$)

Corollary: Unitaries on $n$-qubit can be decomposed as $2^{n-1}(2^n-1)$ two-level unitaries.

4.5.2 Single qubit and CNOT gates are universal

Recall any unitary $U$ can be decomposed into two-level unitaries. Now we decompose two-level unitaries into multi-controlled unitaries where the target is a single qubit.

1. Suppose unitary $U$ acts non-trivially on the two computational basis $\vert s\rangle=\vert s_1s_2\dots s_n\rangle$ and $\vert t\rangle=\vert t_1t_2\dots t_n\rangle$. Let $\tilde{U}$ be the non-trivial $2\times 2$ unitary submatrix of $U$: $$U= \left[\begin{matrix} \ddots&&&&0\\ &\tilde{U}_{11}&&\tilde{U}_{12}&\\ &&\ddots&&\\ &\tilde{U}_{21}&&\tilde{U}_{22}&\\ 0&&&&\ddots \end{matrix}\right]$$
2. Use Gray code to connect two computational bases $\vert s\rangle$ and $\vert t\rangle$ by flipping one bit at a time. For instance, $s=101001$ and $t=110011$ we have the Gray code: $$\begin{align*} s=g_1&=101001\\ g_2&=101011\\ g_3&=100011\\ t=g_4&=110011 \end{align*}$$
3. Let $g_1$ through $g_m$ be the element of a Gray code connecting $g_1=s$ and $g_m=t$. The goal is to design a circuit $F$ to change the basis from $\vert g_1\rangle \to \vert g_2\rangle \to \cdots \to\vert g_{m-1}\rangle$, then perform controlled unitary $\tilde U$ on $\vert g_{m-1}\rangle$ and $vert g_m\rangle$, with the target qubit located at the single qubit where $\vert g_{m-1}\rangle$ and $\vert g_{m}\rangle$ differ, and then undo the transformation $\vert g_{m-1}\rangle \to \vert g_{m-2}\rangle \to\cdots\to \vert g_1\rangle$ by reversing the circuit $F$, let’s say $\tilde F$.
   • Suppose $\vert g_1 \rangle$ and $\vert g_2\rangle$ differs at $i$-th bit, do a $C^{(n-1)}-X$ on the $i$-th bit, i.e. swap $\vert g_1 \rangle$ and $\vert g_2 \rangle$.
   • Next, swap $\vert g_2 \rangle$ and $\vert g_3 \rangle$ with another Controlled-$X$.
   • Continue this fashion until we swap $\vert g_{m-2} \rangle$ and $\vert g_{m-1} \rangle$.
   • Result in the permutation (Other basis will remain the same after applying $F$): $$\begin{align*} \vert g_1\rangle &\xrightarrow{F} \vert g_{m-1}\rangle\\ \vert g_2\rangle &\xrightarrow{F} \vert g_1\rangle\\ \vert g_3\rangle &\xrightarrow{F} \vert g_2\rangle\\ &\vdots\\ \vert g_{m-1}\rangle &\xrightarrow{F} \vert g_{m-2}\rangle\\ \end{align*}$$

Example: Implement the two-level unitary transformation

$$U=\left[\begin{matrix} a&0&\cdots&0&c \\ 0&1&&0&0 \\ \vdots&&\ddots&&\vdots \\0&0&&1&0\\b&0&\cdots&0&d\end{matrix}\right], \quad \tilde U\equiv\left[\begin{matrix}a&c\\b&d\end{matrix}\right]$$

which acts non-trivially only on the states $\vert 000\rangle$ and $\vert 111\rangle$. Write down the Gray code:

$$\begin{matrix} & A & B & C \\ g_1&0&0&0\\ g_2&0&0&1\\ g_3&0&1&1\\ g_4&1&1&1 \end{matrix}$$

Construct the circuit:

$\Rightarrow$ we can decompose any two-level unitaries into multi-controlled single qubit unitaries.

$\Rightarrow$ $\{\text{single qubit } U, CNOT\}$ universal.

Complexity:

• Each $C^{n-1}-\tilde U$: $O(n)$ gates
• Each two-level $U$: $O(n^2)$ gates
• Each unitary: $O((2^n)^2)=O(2^{2n})$ two-level unitaries $=O(n^22^{2n})$ gates.

4.5.3 A discrete set of universal operations

$\{H, T\}$ approximate single qubit unitaries.

• Solovay-Kitaev theorem
  • $O(m\log^c(m/\varepsilon))$ gates
• $\Omega(1/\varepsilon)$ gates

Error:

• Distance on matrices: $|U-V| = \max_{\vert \psi\rangle,\langle\psi\vert\psi\rangle=1}|(U-V)\vert\psi\rangle|$
• unitary invariant:
  • $|AU|=|A|$, $|UA|=|A|$
• triangle inequality:
  • $|A-C| \le |A-B|+|B-C|$, where $|A|\ge0$, $|A|=0, ~\text{iff}~A=0$ i.e. $|U-V| ~\text{iff}~U=V$

待補

4.6 Summary of the quantum circuit model of computation

待補

4.7 Simulation of quantum systems

待補

Bonus

Quantum oracle

Please refer to Section 6.1.1 The oracle

Oracle: Blackbox for $f(x)$

Classical oracle: used in a classical circuit
Quantum oracle: quantum superposition

• Example: $U_f(\vert x_1\rangle\vert y_1\rangle + \vert x_2\rangle \vert y_2\rangle)=\vert x_1\rangle \vert y_1\oplus f(x_1)\rangle + \vert x_2\rangle\vert y_2\oplus f(x_2)\rangle$

• Classical query complexity is also a big research area
• Gap between quantum query complexity v.s. classical query complexity?

Deutsch’s algorithm

Please refer to Section 1.4.3 Deutsch’s algorithm

Problem: Compute $f(0)+f(1)$ for some $f:\{0, 1\}\to\{0, 1\}$ (with $f$ given as a blackbox)

Classical: need two quries, find $f(0)$ and $f(1)$, then compute $f(0)+f(1)$

Quantum: Only one query:

$$\begin{align*} \vert \psi_1\rangle &= (H\vert 0\rangle) \otimes (HX\vert 0\rangle)\\ &= \vert+\rangle \otimes \vert -\rangle\\ &= \frac{1}{\sqrt 2}\left(\vert 0\rangle \otimes \vert -\rangle + \vert 1\rangle \otimes \vert -\rangle\right)\\ \end{align*}$$

Note that:

$$\begin{align*} U_f \vert x\rangle \otimes \vert -\rangle &= \vert x\rangle\otimes \frac{1}{\sqrt 2}(\vert 0\oplus f(x)\rangle-\vert 1\oplus f(x)\rangle)\\ &= \vert x\rangle \otimes \begin{cases} \vert -\rangle, &f(x)=0\\ -\vert-\rangle, &f(x)=1 \end{cases}\\ &= (-1)^{f(x)}\vert x\rangle \otimes \vert -\rangle\\ \end{align*}$$

Then,

$$\begin{align*} \vert \psi_2\rangle &= U_f\frac{1}{\sqrt 2}(\vert 0\rangle\otimes \vert-\rangle + \vert1\rangle\otimes\vert-\rangle)\\ &= \frac{1}{\sqrt 2}\left( (-1)^{f(0)}\vert 0\rangle\otimes\vert -\rangle + (-1)^{f(1)}\vert 1\rangle\otimes \vert-\rangle\right)\\ &=\frac{1}{\sqrt 2} \underbrace{(-1)^{f(0)}}_{\text{global phase}}\left(\vert 0\rangle\otimes\vert-\rangle+\overbrace{(-1)^{f(1)-f(0)}}^{\text{relative phase}}\vert 1\rangle\otimes\vert-\rangle\right)\\ &= (-1)^{f(0)}\left( \begin{cases} \vert +\rangle, &\text{if }f(0)=f(1)~\\ \vert -\rangle, &\text{if }f(0)\ne f(1)~ \end{cases} \right)\otimes \vert -\rangle\\ ~\\ \vert \psi_3\rangle &= (-1)^{f(0)}\left( \begin{cases} \vert 0\rangle, &\text{if }f(0)=f(1)~\\ \vert 1\rangle, &\text{if }f(0)\ne f(1)~ \end{cases}\right)\otimes \vert -\rangle \end{align*}$$

Measurement:

$$\begin{cases} 0, &\text{if } f(0)=f(1)\\ 1, &\text{if } f(0)\ne f(1) \end{cases}$$

Deutsch－Jozsa algorithm

Please refer to Section 1.4.4 The Deutsch-Jozsa algorithm

Problem: Given an black box quantum computer known as an oracle that implements some function $f:\{0,1\}^n\to\{0,1\}$. We are probmised that the function is either constant (0 on all outputs or 1 on all outputs, $f(x)=0, \forall x$, or $f(x)=1, \forall x$) or balanced (returns 1 for half of the input domain and 0 for the other half). The task then is to determine if $f$ is constant or balanced by using the oracle.

Classical query complexity depends on details:

• If we want to solve with no error, need $2^n/2+1$ queries. Even if $f(x)$ is balanced, the first $2^n/2$ queries might be all zero.
• Using randomized algorithm only want constant (say less than $1/3$) error $\Rightarrow$ only need constant queries. Low probability that random queries or balanced $f$ all match.

Quantum query, perfect with $1$ query:

Note that:

$$\begin{align*} H^{\otimes n} (\vert 0\rangle)^n&=\vert +\rangle^{\otimes n}\\ &= \frac{1}{\sqrt {2^n}}(\vert 0\rangle+\vert 1\rangle)\otimes(\vert 0\rangle+\vert 1\rangle)\otimes\cdots\otimes(\vert 0\rangle+\vert 1\rangle)\\ &= \frac{1}{\sqrt {2^n}}(\vert00\dots0\rangle+\cdots+\vert11\dots1\rangle)\\ &= \frac{1}{\sqrt {2^n}}\sum_{x\in\{0,1\}^n}\vert x\rangle \end{align*}$$

Then,

$$\begin{align*} \vert \psi_1\rangle &= (H^{\otimes n}\otimes HX)\vert 0\rangle^{\otimes n}\otimes \vert 0\rangle\\ &= \sum_{x\in\{0,1\}^n}\frac{1}{\sqrt {2^n}}\vert x\rangle \otimes \vert -\rangle \end{align*}$$

Recall from Deutsch’s algorithm $U_f \vert x\rangle \otimes \vert -\rangle = (-1)^{f(x)}\vert x\rangle \otimes \vert -\rangle$,

$$\begin{align*} \vert \psi_2\rangle &= U_f(\sum_{x\in\{0,1\}^n}\frac{1}{\sqrt {2^n}}\vert x\rangle \otimes \vert -\rangle)\\ &= \sum_{x\in\{0,1\}^n}\frac{(-1)^{f(x)}}{\sqrt {2^n}}\vert x\rangle \otimes \vert -\rangle \end{align*}$$

How about $H^{\otimes n}\vert x\rangle$? On one qubit ($n=1$):

$$\begin{align*} &\begin{cases} H\vert 0 \rangle = \frac{1}{\sqrt 2}(\vert 0\rangle+\vert 1\rangle)\\ H\vert 1 \rangle = \frac{1}{\sqrt 2}(\vert 0\rangle-\vert 1\rangle) \end{cases}\\ \Rightarrow& ~H\vert x \rangle = \frac{1}{\sqrt 2}\sum_{z\in\{0,1\}}(-1)^{xz}\vert z\rangle \end{align*}$$

On multiple qubits:

$$\begin{align*} H^{\otimes n}\vert x_1x_2\dots x_n\rangle &=\sum_{z_1,z_2,\dots,z_n\in\{0,1\}}\frac{(-1)^{x_1z_1+x_2z_2+\dots+x_nz_n}}{\sqrt {2^n}}\vert z_1z_2\dots z_n\rangle\\ &= \sum_{z\in\{0,1\}^n}\frac{(-1)^{x\cdot z}}{\sqrt{2^n}}\vert z\rangle \end{align*}$$

Then,

$$\begin{align*} \vert \psi_3\rangle &= (H^{\otimes n}\otimes I)\vert \psi_2\rangle\\ &=(H^{\otimes n}\otimes I)\sum_{x\in\{0,1\}^n} \frac{(-1)^{f(x)}}{\sqrt{2^n}}\vert x\rangle \otimes \vert -\rangle\\ &= \sum_{z\in\{0,1\}^n}\left( \sum_{x\in\{0,1\}^n} \frac{(-1)^{x\cdot z+f(x)}}{2^n} \right)\vert z\rangle \otimes \vert -\rangle \end{align*}$$

Amplitude for $z=0^n$ on first register $x\cdot z=0 \Rightarrow \text{amp}=\sum_{x\in\{0,1\}^n}\frac{(-1)^{f(x)}}{2^n}$.

$$\begin{cases} \text{amp}=1 & \text{if $f(x)$ is constant, $f(x)=0, \forall x$}\\ \text{amp}=-1 & \text{if $f(x)$ is constant, $f(x)=1, \forall x$}\\ \text{amp}=0 & \text{if $f(x)$ is balanced, $\Big\vert \{x\vert f(x)=0, \forall x\}\Big\vert=\Big\vert \{x\vert f(x)=1, \forall x\}\Big\vert$} \end{cases}$$

$\vert\text{amp}\vert^2=\text{Probability}$

Measurement:

$$\begin{cases} z=0^n, &\text{if $f(x)$ is constant}\\ z\ne0^n, &\text{if $f(x)$ is balanced} \end{cases}$$

Bernstain－Vazirani algorithm

Not on book

Problem: Given an oracle that implements a function $f:\{0,1\}^n\to\{0,1\}$ in which $f(x)$ is promised to be the dot product between $x$ and a secret string $s\in\{0,1\}^n$ module $2$, $f(x)=x\cdot s=x_1\cdot s_1+x_2\cdot s_2+\cdots +x_n\cdot s_n\mod 2$, find $s$.

Classical: need $n$ queries: $s=s_1s_2\dots s_n$

• Get $s_1$ by query $x=100\dots0$
• Get $s_2$ by query $x=010\dots0$
• … learn $s$ in $n$ queries
• Claim: Can’t do better even with random algorithm because each query only gives one bit of information on $s$.

Quantum: $1$ query. The algorithm is almost the same as Deutsch－Jozsn algorithm.

$$\begin{align*} \vert \psi_3\rangle &= \sum_{z\in\{0,1\}^n}\sum_{x\in\{0,1\}^n} \frac{(-1)^{z\cdot x + f(x)}}{2^n} \vert z\rangle\\ &= \sum_{z\in\{0,1\}^n}\sum_{x\in\{0,1\}^n} \frac{(-1)^{z\cdot x + s\cdot x}}{2^n} \vert z\rangle\\ &= \sum_{z\in\{0,1\}^n}\sum_{x\in\{0,1\}^n} \frac{(-1)^{(z\oplus s)\cdot x}}{2^n} \vert z\rangle\\ \end{align*}$$

Claim that $\sum_{x\in\{0,1\}^n} \frac{1}{2^n}(-1)^{(z\oplus s)\cdot x} \vert z\rangle=\delta_{z\cdot s}$.

Proof:

• When $z=s$, $z\oplus s=0\Rightarrow\sum_{x\in\{0,1\}^n} \frac{1}{2^n}(-1)^{(z\oplus s)\cdot x}=\sum_{x\in\{0,1\}^n}\frac{1}{2^n}=1$.
• When $z\ne s$, $\vert \psi_3\rangle$ normalized $\Rightarrow$ all $z\ne s$ terms $=0$ (can also check cancellation)

$$\Rightarrow \vert\psi_3\rangle=\sum_{z\in\{0,1\}^n}\delta_{z\cdot s}\vert z\rangle=\vert s\rangle$$

Measurement result is $s$.

Let $a=z\oplus s$, prove that if $a\ne 0^n$ (i.e. $z\ne s$),

$$\sum_{x\in\{0,1\}^n} (-1)^{a\cdot x} = 0.$$

Proof: Let $a_i$ and $x_i$ denote the $i^\text{th}$ element of $a$ and $x$, respectively. Suppose there are $k>0$ bits in $a$ are $1$, then we can separate $a$ and $x$ into $\bar{a}=(a_i|a_i=0,\forall i)$, $\hat{a}=(a_i|a_i=1,\forall i)$, $\bar{x}=(x_i|a_i=0,\forall i)$ and $\hat{x}=(x_i|a_i=1,\forall i)$. Since $\bar{a}=0^{n-k}$ and $\hat{a}=1^k$,

$$\sum_{x\in\{0,1\}^n}(-1)^{a\cdot x}=\sum_{\bar{x}\in\{0, 1\}^{n-k}}\sum_{\hat{x}\in\{0,1\}^k}(-1)^{\bar{a}\cdot\bar{x}+\hat{a}\cdot\hat{x}}=2^{n-k}\sum_{\hat{x}\in\{0,1\}^k}(-1)^{\hat{a}\cdot\hat{x}}$$

If the number of $1$-bits in $\hat{x}$ is odd, $(-1)^{\hat{a}\cdot\hat{x}}=-1$. Otherwise, $(-1)^{\hat{a}\cdot\hat{x}}=1$ if it is even. Thus, we can prove $\sum_{\hat{x}\in\{0,1\}^k}(-1)^{\hat{a}\cdot\hat{x}}=0$ if we show the number of $\hat{x}$ in which the number of $1$-bits is odd equals to that of the number of $1$-bits is even. We prove by induction:

1. Hypothesis: for $k>0$, $\text{Odd}(k)=\text{Even}(k)$, where $\text{Odd}(k)$ denotes the number of $\hat{x}\in\{0,1\}^k$ in which the number of $1$ is odd, $\text{Even}(k)$ denotes the number of $\hat{x}\in\{0,1\}^k$ in which the number of $1$ is even.

2. Base case: for $k=1$, the outcomes of $\hat{x}$ are $\{0, 1\}$ $\Rightarrow \text{Odd}(1)=\text{Even}(1)=1$.

3. Induction step: suppose for $k>1$, $\text{Odd}(k)=\text{Even}(k)$ is true. Then for $k+1$, $\text{Odd}(k+1)=\text{Odd}(k)+\text{Even}(k)$ as we add a $0$ for odd numbers they still remain odd, and add a $1$ for even numbers they become odd. Similar for $\text{Even}(k+1)=\text{Even}(k)+\text{Odd}(k)$. Thus, $\text{Odd}(k+1)=\text{Even}(k+1)$, the statement holds.

Hence, $\sum_{\hat{x}\in\{0,1\}^k}(-1)^{\hat{a}\cdot\hat{x}}=0, \forall k>0 \Longrightarrow \sum_{x\in\{0,1\}^n}(-1)^{a\cdot x}=0$, if $a\ne 0^n$.

Simon’s problem

Please refer to Section 5.4.3 The hidden subgroup problem

Problem: Given an oracle $f:\{0,1\}^n\to\{0,1\}^n$, promised to satisfy the property that, for some $s\in\{0,1\}^n, s\ne 0^n$ and all $x,y\in\{0, 1\}^n$, $f(x)=f(x\oplus s)$. Find $s$.

Example: if $n=3$, the following is the function $f(x)$:

$x$	000	001	010	011	100	101	110	111
$f(x)$	101	010	000	110	000	110	101	010

The answer is $s=110$.

Classical: How many random classical queries needed to find a “collision”? $2^{n-1}$ possible outputs. $\sim\frac{1}{2^{n-1}}$ probability a pair is a collision.

• $O(2^n)$ probabilities $\Rightarrow$ $O(\sqrt{2^n})=O(2^{\frac{n}{2}})$ queries to find a collision with constant probability.
• Lowerbound also $\Omega(2^\frac{n}{2})$
• $\Rightarrow$ classical complexity $\Theta(2^\frac{n}{2})$

Quantum complexity: $O(n)$ queries

$$\begin{align*} \vert \psi_1\rangle &= \frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}\vert x\rangle \otimes \vert 0\rangle^{\otimes n}\\ \vert \psi_2\rangle &= \frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}\vert x\rangle \otimes \vert f(x)\rangle \end{align*}$$

On measuring second register: uniformly random $f(x)$ collapse the first register into corresponding preimages:

$$\vert \psi_3\rangle = \frac{1}{\sqrt 2}(\vert x\rangle + \vert x\oplus s\rangle)$$ $$\vert \psi_4\rangle = \frac{1}{\sqrt 2}\frac{1}{\sqrt{2^n}}\sum_{z\in\{0,1\}^n}\left( (-1)^{x\cdot z}+(-1)^{(x\oplus s)\cdot z} \right)\vert z\rangle$$

Measurement:

1. non-zero amplitude $\Rightarrow$ $x\cdot z=(x\oplus s)\cdot z \Rightarrow s\cdot z=0$
2. Will get a “uniformly” random $z$ such that $s\cdot z=0$ (there are $2^{n-1}$ such z)
3. Do this $k$ times, get $z_1, z_2, \dots, z_k$.
   (informal) each $z_i$ gives one bit of information on $s$, need $O(n)$ $z_i$ to solve: $$\begin{eqnarray*} s\cdot &z_1=0 &~~\Rightarrow~ &s_1z_{11}+s_2z_{12}+\cdots+s_nz_{1n}&=0\\ s\cdot &z_2=0 &~~\Rightarrow~ &s_1z_{21}+s_2z_{22}+\cdots+s_nz_{2n}&=0\\ &\vdots\\ s\cdot &z_k=0 &~~\Rightarrow~ &s_1z_{n1}+s_2z_{n2}+\cdots+s_nz_{kn}&=0 \end{eqnarray*}$$
4. $k$ linear equations on $(s_1,s_2,\dots,s_n)$. $n$ Linearly independent equations $\Rightarrow$ solve $s$
5. Good probability to determine $s$ with $k=O(n)$ random equations.

Birthday paradox: How many people in a room such that the probability of “a pair of people has same birthday” $\sim 50\%$ ?

• $365$ possible birthday $\Rightarrow$ $23$ people suffice.
• Number of pairs $\sim N^2$ $\Rightarrow$ $\sqrt{365}$ to find collision