1 Introduction and overview¶

Each remaining section in the chapter gives a brief introduction to one or more fundamental concepts from the field: quantum bits, quantum computers, quantum gates and quantum circuits, quantum algorithms, experimental quantum information processing, quantum information and quantum communication.

1.1 Global perspectives¶

Whether it is possible to signal faster than light $\leftrightarrow$ whether it is possible to clone an unknown quantum state: no-cloning theorem (early 1980s), is one of the earliest results of quantum computation and quantum information.
Church–Turing thesis: if an algorithm can be performed on any piece of hardware (say, a modern personal computer), then there is an equivalent algorithm for a Universal Turing Machine which performs exactly the same task as the algorithm running on the personal computer.
Strong Church–Turing thesis: Any algorithmic process can be simulated efficiently using a Turing machine.
The first major challenge to the strong Church–Turing thesis arose in the mid 1970s, which is that it's possible to test whether an integer is prime or composite using a randomized algorithm. That is, the Solovay–Strassen test for primality used randomness as an essential part of the algorithm.
Untill today there is no known deterministic test for primality $\rightarrow$ computers with access to a random number generator would be able to efficiently perform computational tasks with no efficient solution on a conventional deterministic Turing machine.
Hence we have a modified version of Church-Turing Thesis: Any algorithmic process can be simulated efficiently using a probabilistic Turing machine.
It is comparatively difficult to come up with quantum algorithm, since ^①要先抑制自己已經根深蒂固的古典思維, ^②發明出新的演算法必須比當前已知所有解同樣問題的古典演算法還要快.
At the same time computer science was exploding in the 1940s, another revolution was taking place in our understanding of communication. The key step taken by Shannon was to mathematically define the concept of information.
Shannon’s noiseless channel coding theorem, quantifies the physical resources required to store the output from an information source. Shannon’s second fundamental theorem, the noisy channel coding theorem, quantifies how much information it is possible to reliably transmit through a noisy communications channel.
Shannon 的 noisy channel coding theorem 只給出在噪音通道下, 有效資訊傳輸量的上界, 但沒明確給出有哪個 error correcting code 可以達到這個上界.
In 1996 two groups (= CSS codes) $\xrightarrow{\text{subsumed by}}$ the stabilizer codes. The theory of quantum error-correcting codes was developed to protect quantum states against noise.
As for transmitting ordinary classical information using a quantum channel, we have superdense coding (transmit two classical bits of information, while only transmitting one quantum bit from sender to receiver).
No unifying theory of networked information theory exists for quantum channels. But it is of much consequence! One example may suffice its value: 兩個 zero-capacity 的古典通道併聯, 還是 zero-capacity; 但如果是兩個反向的量子通道併聯, 就竟然可以通訊!
Another field is quantum cryptography: for private key cryptosystem, there is QKD (quantum key distribution), which makes use of the property that eavesdropping changes the quantum state of the qubit; for public key cryptosystem, Shor's algorithm can break RSA, and Shor's quantum algorithm for solving the discrete logarithm problem can break other public key systems.

1.2 Quantum bits¶

In this section we introduce the properties of single and multiple qubits, comparing and contrasting their properties to those of classical bits.

How a qubit can be realized: as the two different polarizations of a photon, as the alignment of a nuclear spin in a uniform magnetic field, as two states of an electron (ground state $\ket0$ & excited state $\ket1$) orbiting a single atom.
Interestingly, by giving not enough light for an electron to perform $\ket0\rightarrow\ket1$, it will be moved "halfway" into $\ket+$ state.
Geometric representation of a qubit: a qubit in superposition can be written as

\[ \ket{\psi} = \alpha\ket{0} + \beta\ket{1} \;\;,\;\;\text{whereas}\;\abs{\alpha}^2 + \abs{\beta}^2 = 1 \]

but since $\abs{\alpha}^2 + \abs{\beta}^2 = 1$, we can rewrite the equation as

\[ \ket\psi = e^{i\gamma}\bigg( \cos\frac{\theta}{2}\ket0 + e^{i\varphi}\sin\frac{\theta}{2}\ket1\bigg) \]

where $\theta$, $\varphi$, and $\gamma$ are real numbers. Since the factor $e^{i\gamma}$ have no observable effects, we can essentially write the equation

\[ \ket\psi = \cos\frac{\theta}{2}\ket0 + e^{i\varphi}\sin\frac{\theta}{2}\ket1 \]

The numbers $\theta$ and $\varphi$ define a point on the unit three-dimensional sphere, which is called Bloch-sphere:

![](./QCQInote/part1/02.png){width=50%}

However, it must be kept in mind that this intuition is limited because there is no simple generalization of the Bloch sphere known for multiple qubits.

Multiple qubits: say, if we express a pair of qubits in their computational basis state, we get

\[ \ket\psi = \alpha_{00}\ket{00} + \alpha_{01}\ket{01} + \alpha_{10}\ket{10} + \alpha_{11}\ket{11} \]

, with the normalization condition $\Sigma_{x\in\{0,1\}^2} \abs{\alpha_x}^2 = 1$. Now if we only take measurement on the first qubit:

\[ \begin{cases} \text{will measure 0 with probability}\; \abs{\alpha_{00}}^2+\abs{\alpha_{01}}^2, \text{ leaving the post-measurement state}\; \ket{\psi'} = \frac{\alpha_{00}\ket{00} + \alpha_{01}\ket{01}}{\sqrt{\abs{\alpha_{00}}^2+\abs{\alpha_{01}}^2}} \\ \text{will measure 1 with probability}\; \abs{\alpha_{10}}^2+\abs{\alpha_{11}}^2, \text{ leaving the post-measurement state}\; \ket{\psi'} = \frac{\alpha_{10}\ket{10} + \alpha_{11}\ket{11}}{\sqrt{\abs{\alpha_{10}}^2+\abs{\alpha_{11}}^2}} \end{cases} \]

A particularly important two qubit state is the Bell state or EPR pair,

\[ \frac{\ket{00} + \ket{11}}{\sqrt2} \]

is the key ingredient in quantum teleportation and superdense coding. We can know from the measurement on the first qubit which state the second qubit would have if we then measures it. The two qubits are strongly correlated.

1.3 Quantum computation¶

Changes occurring to a quantum state can be described using the language of quantum computation. Analogous to the way a classical computer is built from an electrical circuit containing wires and logic gates, a quantum computer is built from a quantum circuit containing wires and elementary quantum gates to carry around and manipulate the quantum information.

1.3.1 Single qubit gates¶

Quantum state written in vector notation: $\alpha\ket0 + \beta\ket1 \longrightarrow\begin{bmatrix}\alpha \\ \beta\end{bmatrix}$.
Quantum NOT gate $X = \begin{bmatrix} 0 & 1\\ 1 & 0\end{bmatrix}$, hence ${X}\begin{bmatrix}\alpha \\ \beta\end{bmatrix} = \begin{bmatrix}\beta \\ \alpha\end{bmatrix}$.
So quantum gates on a single qubit can be described by two by two matrices $U$. Are there any constraints on what matrices may be used as quantum gates? It turns out that the normalization condition $\abs{\alpha}^2 + \abs{\beta}^2 = 1$ yields

\[ U^\dagger U = I \]

Amazingly, this unitarity constraint is the only constraint on quantum gates!

Another two important gates:

\[ Z\equiv\begin{bmatrix} 1 & \;\;0\\ 0 & -1\end{bmatrix}\;\;\;\text{and}\;\;\;H\equiv\frac{1}{\sqrt2}\begin{bmatrix} 1 &\;\; 1\\ 1 & -1\end{bmatrix} \]

To get the visualization of the Hadamard gate on the Bloch sphere, the operation is just a rotation of the sphere about the $\hat y$ axis by 90°, followed by a rotation about the $\hat x$ axis by 180° (below is the illustration of an $H$ gate acting on $\ket +$ state).

![](./QCQInote/part1/03.png)

Decomposing single qubit operations¶

Later in the content we can prove that an arbitrary $2 \times 2$ unnitary matrix may be decomposed as

\[ U = e^{i\alpha} \begin{bmatrix} e^{-i\beta/2} & 0 \\ 0 & e^{i\beta/2}\end{bmatrix} \begin{bmatrix} \cos{\frac{\gamma}{2}} & -\sin{\frac{\gamma}{2}} \\ \sin{\frac{\gamma}{2}} & \;\;\;\cos{\frac{\gamma}{2}}\end{bmatrix} \begin{bmatrix} e^{-i\delta/2} & 0 \\ 0 & e^{i\delta/2}\end{bmatrix} \]

where $\alpha, \;\beta, \;\gamma$, and $\delta$ are real-valued. Notice that the second matrix is just an ordinary rotation. It turns out that the first and last matrices can also be understood as rotations in a different plane. This decomposition can be used to give an exact prescription for performing an arbitrary single qubit quantum logic gate.

1.3.2 Multiple qubit gates¶

常見的 classical multiple gates 有 AND, OR, XOR, NAND, 和NOR. An important theoretical result is that any function on bits can be computed from the composition of NAND gates alone, which is thus known as a universal gate.
CNOT can be realized as the control qubit and the target qubit are XORed and stored in the target qubit:

![](./QCQInote/part1/04.svg)

, where $\oplus$ is addition modulo two. Yet another way of describing the action of the CNOT is through its matrix representation:

\[ U_{\text{CNOT}} = \begin{bmatrix} 1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{bmatrix} \]

, as for the single qubit case, the requirement that probability be conserved is expressed in the fact that $U_{\text{CNOT}}$ is a unitary matrix, that is, $U_{\text{CNOT}}^\dagger U_{\text{CNOT}} = I$.

Any multiple qubit logic gate may be composed from CNOT and single qubit gates. (proof in later content)

1.3.3 Measurements & Quantum circiuts¶

It is possible to treat the $\ket{+}$ and $\ket -$ states as though they were the computaitonal basis states, for instance,

\[ \ket\psi = \alpha\ket0 + \beta\ket1 = \frac{\alpha + \beta}{\sqrt2}\ket+ \;+\; \frac{\alpha - \beta}{\sqrt2}\ket- \]

Generally, given ay basis states $\ket a$ and $\ket b$ for a qubit, it is possible to express an arbitrary state as a linear combination $\alpha\ket a + \beta\ket b$ of these states. Furthermore, provided the states are orthonormal, it is possible to perform a measurement with respect to the basis.
Swap gate: Below circuit accomplishes the swap operation.

![](./QCQInote/part1/05.svg)

\[ \begin{align} \ket{a, b} &\longrightarrow \ket{a, a\oplus b}\nonumber \\ &\longrightarrow \ket{a\oplus{(a\oplus b)}, a\oplus b} = \ket{b, a\oplus b}\nonumber \\ &\longrightarrow \ket{b, (a\oplus b)\oplus b} = \ket{b, a} \end{align} \]

There are a few features allowed in classical circuits that are not usually present in quantum circuits:
- Acyclic: there are no loops in quantum circuits (feedback from one part of the quantum circuit to another).
- No FANIN: wires can't be joined together, since this is a bitwise-OR operation and irreversible, xhence not unitary.
- No FANOUT: quantum mechanics forbids the copying of a qubit, which is the no-cloning theorem.

The no-cloning theorem¶

Suppose we are copying the pure quantum state $\ket\psi$ from slot $A$ to slot $B$ (which starts in also a pure state $\ket s$) in a quantum machine. Thus the initial state of the copying machine is:

\[ \ket\psi\otimes\ket s \]

Some unitary evolution $U$ now effects the copying procedure, ideally,

\[ \ket\psi\otimes\ket s \nonumber \xrightarrow{U} U (\ket\psi\otimes\ket s) = \ket\psi\otimes\ket\psi \]

This works for another state, $\ket\varphi$, also:

\[ \begin{align} U (\ket\psi\otimes\ket s) = \ket\psi\otimes\ket\psi \\ U (\ket\varphi\otimes\ket s) = \ket\varphi\otimes\ket\varphi \end{align} \]

Taking the inner product of these two equations gives:

\[ \bra{\psi}\ket{\varphi} = (\bra{\psi}\ket{\varphi})^2 \]

From the above equation there are oly two possibilities: either $\ket\psi = \ket\varphi$, or $\ket\psi$ are orthogonal to $\ket\varphi$. Thus a cloning device can only clone states which are orthogonal to one another, and therefore a general quantum cloning device is impossible.

Even if one allows non-unitary cloning devices, the cloning of non-orthogonal pure states remains impossible unless one is willing to tolerate a finite loss of fidelity in the copied states.

1.3.4 Bell states & Quantum teleportation¶

![](./QCQInote/part1/06.svg)

Above is a demonstration of quantum teleportation:

First generate an EPR pair (or Bell state): the part before the dashed line. Assume $\ket\psi = \alpha\ket0 + \beta\ket1$, then the state of the three qubits are:

\[ \begin{align*} \text{original state :} \;&\Big(\alpha\ket0 + \beta\ket1\Big) \ket{00} \\ &\xrightarrow{\text{after Hadamard gate}} \frac{1}{\sqrt2}\Big(\alpha\ket0 + \beta\ket1\Big) \Big(\ket{00} + \ket{10}\Big) \\ &\xrightarrow{\text{after CNOT}} \frac{1}{\sqrt2}\Big(\alpha\ket0 + \beta\ket1\Big) \Big(\ket{00} + \ket{11}\Big) \end{align*} \]
We then entangle the state which we want to teleport with qubit #2:

\[ \begin{align*} \text{from previous section :}\;&\frac{1}{\sqrt2}\Big(\alpha\ket{000} + \alpha\ket{011} + \beta\ket{100} + \beta\ket{111}\Big) \\ & \xrightarrow{\text{after CNOT}} \frac{1}{\sqrt2}\Big(\alpha\ket{000} + \alpha\ket{011} + \beta\ket{110} + \beta\ket{101}\Big) \\ & \xrightarrow{\text{after Hadamard}} \frac{1}{\sqrt2}\Bigg( \alpha\Big( \frac{\ket0 + \ket1}{\sqrt2} \Big)\Big(\ket{00}+\ket{11}\Big)\;+\; \beta\Big( \frac{\ket0 - \ket1}{\sqrt2} \Big)\Big(\ket{10}+\ket{01}\Big) \Bigg) \end{align*} \]

which equals to:

\[ \frac{1}{2} \Bigg( \ket{00}\Big(\alpha\ket0 + \beta\ket1\Big) \;+\; \ket{01}\Big(\alpha\ket1 + \beta\ket0\Big) \;+\; \ket{10}\Big(\alpha\ket0 - \beta\ket1\Big) \;+\; \ket{11}\Big(\alpha\ket1 - \beta\ket0\Big) \Bigg) \]
We can then apply $X$ and $Z$ gate to the third qubit (depend on the measurement outcome of qubit #1 and #2) to restore $\ket\psi$ on qubit #3.

Quantum teleportation emphasizes the interchangeability of different resources in quantum mechanics, showing that one shared EPR pair together with two classical bits of communication is a resource at least the equal of one qubit of communication. In particular, in Chapter 10 待補 we explain how teleportation can be used to build quantum gates which are resistant to the effects of noise, and in Chapter 12 待補 we show that teleportation is intimately connected with the properties of quantum error-correcting codes.

1.4 Quantum algorithms¶

1.4.1 Simulating Classical Computer¶

Though quantum circuits can't be used to directly simulate classical circuits (because unitary quantum logic gates are inherently reversible, whereas many classical logic gates such as the NAND gate are inherently irreversible), but we can make use of the Toffoli gate:
Now if a quanutm computer wants to simulate a classical computer which is non-deterministic (e.g. generate random number), one can achieve that by apply $H$ gate to a $\ket0$ state, then measure it and results in a 50/50 chance of 0 or 1.

1.4.2 Quantum parallelism¶

quantum parallelism allows quantum computers to evaluate a function $f(x)$ for many different values of $x$ simultaneously. Suppose $f(x):{0,1} \rightarrow{0,1} $ is a function with a one-bit domain and range. The below circuit implemented a transformation $U_f: \ket{x,y} \rightarrow \ket{x, y\oplus f(x)}$ (引進$\oplus$是為了要讓這個transformation是unitary的, 只要apply兩次就回到原來的state).

Now if $\ket y = 0$ we will result $f(x)$ in the second register. But if we first Hadamard transform the first qubit (or Walsh– Hadamard transform), we'll result in the state: ${\ket{0, f(0)} + \ket{1, f(1)}}/\sqrt2$. 1. Generally, the result of performing the Hadamard transform on $n$ qubits initially in the all $\ket0$ state is

\[ \frac{1}{\sqrt{2^n}}\sum_x\ket x \]

, where the sum is over all possible values of $x$, and we write $H^{\otimes n}$ to denote this action (read "$\otimes$" as "tensor"). Note that the Hadamard transform is super efficient since it can produce a superposition of $2^n$ states using only $n$ qubits.
Only quantum parallelism is not enough, we also require the ability to extract information about more than merely one value of $f(x)$ from superposition states like

\[ \frac{1}{\sqrt{2^n}}\sum_x\ket x \ket{f(x)} \]

, which is obtained from applying Hadamard transform and then $U_f$ to the $n+1$ qubit state $\ket{0}^{\otimes n}\ket{0}$.

1.4.3 Deutsch's Algorithm¶

Deutsch’s algorithm combines quantum parallelism with a property of quantum mechanics known as interference, as illustrated below. We set the input state $\ket{\psi_0} = \ket{01}$ and use the same transform $U_f$ above:

![](./QCQInote/part1/11.svg)

after two $H$ gate, we have $\ket{\psi_1} = \Big[\frac{\ket0 + \ket1}{\sqrt2}\Big]\Big[\frac{\ket0 - \ket1}{\sqrt2}\Big]$, due to the unitarity of $U_f$, we expect the state $\ket{\psi_2} = (-1)^{f(x)}\ket{x}\frac{\ket0-\ket1}{\sqrt2}$. (因為如果$f(x) = 0$的話那$U_f$就等於沒做任何事, 那如果$f(x) = 1$的話那第二個qubit出來的$y\oplus f(x)$就相當於反相$y$) So there are two possible groups of outcome $\ket{\psi_2}$:

\[ \ket{\psi_2} = \begin{cases} \pm \Big[\frac{\ket0 + \ket1}{\sqrt2}\Big]\Big[\frac{\ket0 - \ket1}{\sqrt2}\Big] \;\;\;\text{, if } f(0) = f(1) \\ \\ \pm \Big[\frac{\ket0 - \ket1}{\sqrt2}\Big]\Big[\frac{\ket0 - \ket1}{\sqrt2}\Big] \;\;\;\text{, if } f(0) \neq f(1) \end{cases} \]

, therefore we have:

\[ \ket{\psi_3} = \begin{cases} \pm \ket0\Big[\dfrac{\ket0 - \ket1}{\sqrt2}\Big] \;\;\;\text{, if } f(0) = f(1) \\ \\ \pm \ket1\Big[\dfrac{\ket0 - \ket1}{\sqrt2}\Big] \;\;\;\text{, if } f(0) \neq f(1) \end{cases} \]

, notice that if

\[ \begin{cases*} \;f(0) = f(1)\Rightarrow f(0) \oplus f(1) = 0 \\ \\ \;f(0) \neq f(1)\Rightarrow f(0) \oplus f(1) = 1 \end{cases*} \]

, hence we can technically write $\ket{\psi_3}$ as:

\[ \ket{\psi_3} = \pm \ket{f(0) \oplus f(1)}\bigg[\dfrac{\ket0 - \ket1}{\sqrt2}\bigg] \]

, which is very interesting indeed! (compare to the classical scheme) Because the quantum circuit has given us the ability to determine a global property of $f(x)$ (在此題即$f(0) \oplus f(1)$), using only one evaluation of $f(x)$.

The essence of the design of many quantum algorithms is that a clever choice of function and final transformation allows efficient determination of useful global information about the function (information which cannot be attained quickly on a classical computer).

1.4.4 The Deutsch–Jozsa algorithm¶

First we need to deal with the Deutsch’s problem:

How many times do we need to repeat the following procedure to decide whether the function $f(x)$ is balanced or constant?

select a number $x$ from $0$ to $2^n-1$.
feed $x$ into $f$, note that $f(x)$ only outputs $0$ or $1$.

balanced: equal amount of $0$ and $1$ as outcome for all possivle value of $x$, constant: constant output disregarding different values of $x$.

Classical case: The best deterministic classical algorithm require $2^{n-1}+1$ queries (for the worst case)
Quantum case: Analogous to the Duetsch's algorithm scheme, but now prepare $n$ query-qubits instead of $1$, we result in

\[ \ket{\psi_0} = \ket{0}^{\otimes n}\ket{1} \]

, after the Hadamard transform on the query registers and applying $H$ gate on the answer register we get

\[ \ket{\psi_1} = \sum_{x\in \{0,1\}^n} \dfrac{\ket x}{\sqrt{2^n}} \bigg[ \dfrac{\ket0-\ket1}{\sqrt2}\bigg] \]

. Next, the classical function $f$ is evaluated using $U_f: \ket{x, y} \rightarrow\ket{x, y\oplus f(x)}$, giving

\[ \ket{\psi_2} = \sum_{x\in \{0,1\}^n} \dfrac{(-1)^{f(x)}\ket x}{\sqrt{2^n}} \bigg[ \dfrac{\ket0-\ket1}{\sqrt2}\bigg] \]

we now has a set of qubits in which the result of function evaluation is stored in the amplitude of the qubit superposition state.

Now we want to derive the expression for the Hadamard transform on $n$ superpositioned qubits, we start from $n=1$ case:

\[ H\ket{x} = \sum_{z}\frac{(-1)^{xz}\ket z}{\sqrt2} \]

thus,

\[ H^{\otimes n}\ket{x_1,\cdots,x_n} = \frac{1}{\sqrt{2^n}}\sum_{z_1,\cdots,z_n} (-1)^{x_1z_1 + \cdots x_nz_n} \ket{z_1,\cdots,z_n} \]

, and this can be summarized in a more terse term:

\[ H^{\otimes n}\ket{x} = \frac{1}{\sqrt{2^n}}\sum_{z} (-1)^{x\cdot z} \ket{z} \]

where $x\cdot z$ is the bitwise inner product of $x$ and $z$, modulo $2$.

We can then evaluate $\ket{\psi_3}$:

\[ \ket{\psi_3} = \sum_z\sum_x \dfrac{(-1)^{x \cdot z + f(x)}\ket{z}}{2^n} \bigg[\dfrac{\ket0-\ket1}{\sqrt2}\bigg] \]

consider the amplitude of $\ket z = \ket{0\cdots 0}$, we found it solely depends on the function type of $f(x)$.

\[ \begin{cases} \;f\text{ is constant}\longrightarrow \ket{0\cdots0}\text{'s amplitude is }\pm 1\longrightarrow\text{we will definitely measure all 0 for n qubits.} \\ \\ \;f\text{ is balanced}\longrightarrow \ket{0\cdots0}\text{'s amplitude is }\;\;0\longrightarrow\text{we will definitely not measure all 0 for n qubits.} \end{cases} \]

Caveats:

Deutsch’s problem is not an especially important problem; it has no known applications.
The method for evaluating the function is quite different in the two cases, render it uncomparable between classical and quantum scenario.
If one adopts a probabilistic instead of deterministic classical computer, one can quickly decide the function type with high confidence.

Exercise 1.1

(Probabilistic classical algorithm) Suppose that the problem is not to distinguish between the constant and balanced functions with certainty, but rather, with some probability of error $\epsilon<1/2$. What is the performance of the best classical algorithm for this problem?

solution

\[ \binom{2^n/2}{2} / \binom{2^n}{2} \times 2 = \frac{(2^{n-1})(2^{n-1}-1)/2}{(2^{n})(2^{n}-1)/2}\times2 = \frac{2^{n-1}-1}{2^n-1} < \frac{1}{2} \]

A probabilistic classical computer can solve Deutsch’s problem with two evaluations with some probability of error $\epsilon<1/2$.

1.4.5 Summarization¶

Generally there are 3 classes of quantum algorithms which provide an advantage over known classical algorithms:

algorithms based upon quantum versions of the Fourier transform (e.g. Deutsch–Jozsa algorithm, Shor's algorithm for factoring and discrete algorithm)
quantum search algorithms
quantum simulation

We will now breifly describe each of these three classes of algorithms.

Quantum algorithms based upon the Fourier transform The discrete Fourier transform is usually described as transforming a set $x_0, \cdots, x_{N-1}$ of $N$ complex numbers into a set of complex numbers $y_0, \cdots, y_{N-1}$ defined by

\[ y_k \equiv \frac{1}{\sqrt N} \sum^{N-1}_{j=0}e^{i\frac{2\pi jk}{N}}x_j \]

, the Fourier transformed version of a problem is often easier than the original problem, enabling a solution.

The Fourier transform has proved so useful that a beautiful generalized theory of Fourier transforms has been developed which goes beyond the definition of equation (33). What is important is that the Hadamard transform used in the Deutsch–Jozsa algorithm is an example of this generalized class of Fourier transforms. Moreover, many of the other important quantum algorithms also involve some type of Fourier transform.

Shor’s fast algorithms for factoring and discrete logarithm, are two examples of algorithms based upon the Fourier transform. We start by imagining that we define a linear transformation $U$ on $n$ qubits with the action it performs on computational basis $\ket j$:

\[ \ket j \longrightarrow \frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1}e^{i\frac{2\pi jk}{2^n}}\ket k\;\;\;\;\;,\text{where}\; 0\leq j \leq (2^n-1). \]

, you can check the unitarity of this transformation, which makes it a valid quantum circuit; moreover if we perform same transformation on superposition states:

\[ \sum_{j=0}^{2^n-1} x_j\ket{j} \longrightarrow \sum_{j=0}^{2^n-1} x_j \bigg(\frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1}e^{i\frac{2\pi jk}{2^n}}\ket k\bigg) = \sum_{k=0}^{2^n-1} y_k\ket{k} \]

, which is the vector version for the Fourier transform in equation (33) where $N = 2^n$.

Time complexity:

Classically, the fast Fourier transform takes roughly $N\log(N) \approx n2^n$ steps.
On a quantum computer, it takes only $\Big(\log(N)\Big)^2 \approx n^2$ steps. (The quantum circuit to do this is explained in [Chapter 5][#5] 待補)

Though we can compute QFT faster on quantum computer, Fourier transform is being performed on the information hidden in the amplitudes of the quantum state. This information is not directly accessible to measurement. (if the output state is measured, it will collapse each qubit into the state $\ket0$ or $\ket1$, preventing us from learning the transform result $y_k$ directly.

Problems like Deutsch’s problem, and Shor’s algorithms for discrete logarithm and factoring, are all cases for Kitaev's discovery of a method to solve the Abelian stabilizer problem, and the generalization to the hidden subgroup problem:

Let $f$ be a function from a finitely generated group $G$ to a finite set $X$ such that $f$ is constant on the cosets of a subgroup $K$, and distinct on each coset. Given a quantum black box for performing the unitary transform $U\ket{g}\ket{h} = \ket{g} \ket{h\oplus f(g)}$, for $g\in G,\; h\in X$, and $\oplus$ an appropriately chosen binary operation on $X$, find a generating set for $K$.

Quantum search algorithms With its basic principles were discovered by Grover, quantum search algorithm solves the following problem:

Given a search space of size $N$, and no prior knowledge about the structure of the information in it, we want to find an element of that search space satisfying a known property. How long does it take to find an element satisfying that property?

Time complexity:

Classically, this problem requires approximately $N$ operations.
But the quantum search algorithm allows it to be solved using approximately $\sqrt N$ operations.

Though it offers only a quadratic speedup (whereas QFT offers an exponential speedup), it has richer application and can adapt to a wide range of problems, in [Chapter 6][#6] 待補 which will it be explained in detail.

Quantum simulation
In general, storing the quantum state of a system with $n$ distinct components takes something like $c^n$ bits of memory on a classical computer, where $c$ is a constant which depends upon details of the system being simulated, and the desired accuracy of the simulation.
Whereas on a quantum computer, it only needs $cn$ qubits to perform simulation, but this does not mean that the fast simulation will allow the desired information about the quantum system to be obtained. (e.g. when we take measurement on the quantum circuit, the $cn$ qubit simulation will collapse into a definite state, giving only $cn$ bits of information; in other words, the total amount of $c^n$ bits information is not entirely accessible)

Thus, a crucial step in making quantum simulations useful is development of systematic means by which desired answers can be efficiently extracted.

The power of quantum computation

First we need to understand some of Computational complexity theory:
Two of the most important complexity classes are $\textbf{P}$ and $\textbf{NP}$. Roughly speaking, $\textbf{P}$ is the class of computational problems that can be solved quickly on a classical computer. $\textbf{NP}$ is the class of problems which have solutions which can be quickly checked on a classical computer.
For instance, factoring (finding the prime factors of a given number) is a problem not in $\textbf{P}$, but a problem in $\textbf{NP}$.
It is clear that $\textbf{P}$ is a subset of $\textbf{NP}$, since the ability to solve a problem implies the ability to check potential solutions.
But it's not so clear is whether or not there are problems in $\textbf{NP}$ that are not in $\textbf{P}$, which is:

\[ \textbf{P} = \textbf{NP} \;\;\;\;\text{or}\;\;\;\;\ \textbf{P} \neq \textbf{NP} \]

if $\textbf{P} \neq \textbf{NP}$, then there are no $\textbf{NP-complete}$ problem which can be efficiently solved on a classical computer. (可以把NP-complete問題想成是NP問題裡面比較具代表性的問題)
Besides $\textbf{P}$ and $\textbf{NP}$, there're also other complexity classes:
$\textbf{PSPACE}$: consists of those problems which can be solved using resources which are few in spatial size (that is, the computer is small), but not necessarily in time (long computations are fine). (有點無腦暴力法的感覺), is believed to be strictly larger than both $\textbf{P}$ and $\textbf{NP}$ although, again, this has never been proved.
$\textbf{BPP}$: problems that can be solved using randomized algorithms in polynomial time, if a bounded probability of error (say $\frac{1}{4}$) is allowed in the solution to the problem. (他被認為甚至比$\textbf{P}$更能在classical computer上是efficiently solvable的)

No matter what do we not know, what is already clear is that the theory of quantum computation poses interesting and significant challenges to the traditional notions of computation. What makes this an important challenge is that the theoretical model of quantum computation is believed to be experimentally realizable, because – to the best of our knowledge – this theory is consistent with the way Nature works. If this were not so then quantum computation would be just another mathematical curiosity.

1.5 Experimental quantum information processing¶

In the next two sections , we begin with a review of the famous Stern–Gerlach experiment, which provides evidence for the existence of qubits in Nature. We then widen our scope, addressing the broader problem of how to build practical quantum information processing systems.

1.5.1 The Stern–Gerlach experiment¶

Qubit is the term we used to describe the fundamental element of QCQI, but is there any quantum system that behaves like a qubit in real world? It turns out that we may now understand qubits in terms of two level quantum systems.
1927 Stern–Gerlach experiment: 用烤箱加熱氫原子(本來在1922時是用銀原子), then form a beam of atoms, which subsequently fly through a magnetic field (會偏折原子束的方向), and finally project on to a screen. Theoretically, there would only be one peak since the magnetic dipole moment is 0 for hydrogen atom, but surprisingly there appears two peaks, which then suggests there may be some hidden variables (即後來提出的電子自旋 electron spin).
What is more peculiar is that for the $\text{beam}\rightarrow Z\rightarrow X$ scheme (everytime progressing to the next arrow we only take the positive-half part of splitted beams), there are also two peaks at $\pm X$; and for $\text{beam}\rightarrow Z\rightarrow X\rightarrow Z$ scheme, there are again two peaks at $\pm Z$. (古典的想法是$Z$方向的磁矩已經在第一次$Z$磁場的時候被過濾掉了)
The qubit model provides a simple explanation of this experimentally observed behavior:

\[ \begin{align*} \ket{+Z} &\leftarrow \ket 0 \\ \ket{-Z} &\leftarrow \ket 1 \\ \ket{+X} &\leftarrow (\ket 0 + \ket 1)/\sqrt2 \\ \ket{-X} &\leftarrow (\ket 0 - \ket 1)/\sqrt2 \end{align*} \]

, therefore we have $\ket{+Z} = \frac{\ket{+X}+\ket{-X}}{\sqrt2}$ and $\ket{+X} = \frac{\ket{+Z}+\ket{-Z}}{\sqrt2}$, and this explains why everytime there will be two beams split upon meeting new magnetic fields. This example demonstrates how qubits could be a believable way of modeling systems in Nature.

1.5.2 Prospects for practical quantum information processing¶

There are 2 possible points which will prohibit us from doing one or more forms of quantum information processing:
Noise: there is a threshold theorem for quantum computation, which states that if the level of noise in a quantum computer can be reduced below a certain constant threshold value, quantum error-correcting codes can be used to push it down even further, essentially ad-infinitum! The theorem indicates that the effects of noise can be made essentially negligible for quantum information processing. In Chapters 8, 10 and 12 待補 we will discuss quantum noise, quantum error-correction and the threshold theorem in detail.
QM is incorrect: If this occurs, it will be a momentous discovery in the history of science, and can be expected to have considerable consequences in other areas of science and technology, as did the discovery of quantum mechanics.
Quantum state tomography and quantum process tomography are two elementary processes whose perfection is of great importance to quantum computation and quantum information, as well as being of independent interest in their own right.
Quantum state tomography is a method for determining the quantum state of a system: by performing repeated preparations of the same quantum state, which is then measured in different ways in order to build up a complete description of the quantum state.
Quantum process tomography is a more ambitious (but closely related) procedure to completely characterize the dynamics of a quantum system. (e.g. can be used to characterize the performance of an alleged quantum gate or quantum communications channel, or to determine the types and magnitudes of different noise processes in a system.)

Quantum state tomography and quantum process tomography are described in more detail in Chapter 8 待補.

Various small-scale communications primitives like quantum cryptography and quantum teleportation are also of great interest. Chapter 12 待補 will show that teleportation may be an extremely useful primitive for transmitting quantum states between distant nodes in a network, in the presence of noise. 量子瞬移(~~我真會翻譯~~)其實更注重EPR pair的純度, since the EPR pairs may be corrupted during communication, but special entanglement distillation protocols can then be used to clean up the EPR pairs, enabling them to be used to teleport quantum states from one location to another.
For the medium-scale, a promising of quantum information processing is to the simulation of quantum systems. 因為60個qubit的系統就不足以讓超級電腦負荷過來了, 更不用說要跑模擬.
For large-scale applications, there are the factoring of large numbers, taking discrete logarithms, and quantum searching. 前兩者在長遠方向上不重要, 因為他們只威脅到現今我們所使用的加密技術的可靠度; 但quantum searching就應用範圍很廣了, we will discuss some possible applications in Chapter 6 待補.
Physical realization of QC:
Optical system turns out to be suitable for small-scale quantum computer, since photons are highly stable carriers for quantum information, which in other words, hard to directly interact with another, so the quantum gates (a form of interaction) must be mediated by something else, like an atom (光子一號先跟一顆原子作用, 該原子再跟光子二號作用, 來達成兩顆光子的間接作用)
Ion traps and neutral atom traps are alternative schemes for storing qubits. Photons are also used in this scheme, but instead of carring quantum information itself, they manipulate the quantum information stored inside the atom in trap. (e.g. Single qubit quantum gates can be performed by applying appropriate pulses of electromagnetic radiation to individual atoms; quantum measurement can be accomplished in these systems using the long established quantum jumps technique, which implements with superb accuracy the measurements in the computational basis used for quantum computation.)
Nuclear Magnetic Resonance, or NMR schemes, store quantum information in the nuclear spin of atoms in a molecule, and manipulate that information using electromagnetic radiation. (但他不太能操控單一顆原子, 通常是一次操控$10^{15}$個溶液中的粒子, 可以看成是$10^{15}$台電腦平行運算).

To conclude, note that it is important not to assess quantum information processing as though it were just another technology for information processing.

1.6 Quantum Information¶

We can identify a few fundamental goals uniting work on quantum information theory:

Identify elementary classes of static resources in quantum mechanics. (e.g. qubit, classical bit, or a Bell state shared between two distant parties 都可以作為存儲/傳遞訊息的單位)
Identify elementary classes of dynamical processes in quantum mechanics. (e.g. memory⇒the ability to store a quantum state over some period af time; quantum information transmission; or the process of protecting quantum information processing against the effects of noise)
Quantify resource tradeoffs incurred performing elementary dynamical processes. (e.g. what are the minimal resources required to reliably transfer quantum information between two parties using a noisy communications channel?)

The remainder of this section describes some examples of questions studied by quantum information theory, in each case emphasizing the fundamental static and dynamic elements under consideration, and the resource tradeoffs being considered.

Classical information through quantum channels
The fundamental results of classical information theory are Shannon’s noiseless channel coding theorem (quantifies how many bits are required to store information being emitted by a source of information), and Shannon’s noisy channel coding theorem (quantifies how much information can be reliably transmitted through a noisy communications channel)
Definition of an information source (這邊先暫時定義): a classical information source is described by a set of probabilities $p_j, \;j = 1,2,\cdots,d$. Each use of the source results in the "letter" $j$ being emitted, chosen at random with probability $p_j$, independently for each use of the source. (比如說如果information source是English的話, 因為一個段落中字母"e"出現的機率比"z"還高, 故 $p_\text e > p_\text z$, 那我們就可以改用比較少bit的資訊量來表示字母"e", 使整體文章的bit使用量減少, 而Shannon's noiseless channel coding theorem可以告訴我們how well we can compress such a source)
The noiseless channel coding theorem tells us that a classical source described by probabilities $p_j$ can be compressed so that on average each use of the source can be represented using $H(p_j)$ bits of information, where $$ H(p_j) \equiv -\sum_jp_j\log{p_j} $$ is a function of the source probability distribution known as the Shannon entropy. Moreover, the noiseless channel coding theorem tells us that to attempt to represent the source using fewer bits than this will result in a high probability of error when the information is decompressed. (See chapter 12 待補 for more detail)
Verify that Shannon’s noiseless coding theorem satisfies the previous three goals:
1. Static resources X2: the bit and the information source
2. Two-stage dynamic process X1: compress the information source and then decompress it after transmission
3. Finally a quantitative criterion for determining the resources consumed (goal 3) by an optimal data compression scheme is found.
Shannon’s second major result, the noisy channel coding theorem, quantifies the amount of information that can be reliably transmitted through a noisy channel. 訊息傳輸可能是兩個空間點之間的傳輸, 或是兩個時間點之間的傳輸(即儲存資訊, 且是在有噪音的情況下). Both ways to overcome noises is to introduce error-correcting codes, the idea is to add an amount of redundancy into the information so that even some bits corrupt after the channel, one is still possible to recover the original message. (比如說一個channel的錯誤率是50%, 那它的 capacity 就是 half a bit) Shannon’s noisy channel coding theorem provides a general procedure for calculating the capacity of an arbitrary noisy channel.
Verify that Shannon’s noisy channel coding theorem satisfies the previous three goals:
1. Static resources X2: the information source, and the bits being sent through the channel.
2. Dynamic process X3: noise process + encoding process + decoding process.
3. For a fixed noise model, Shannon’s theorem tells us how much redundancy must be introduced by an optimal error-correction scheme if reliable information transmission is to be achieved (goal 3).
One might wonder if the medium used to carry information changed from a bit to a qubit, are the Shannon's two theorems still valid? (e.g. if using qubits allows a better compression rate than is possible classically?) Unfortunately, we will eventually prove that qubits do not allow any significant saving in the amount of communication required to transmit information over a noiseless channel.
For the problem of transmitting classical information through a noisy quantum channel, in Chapter 12 待補 we’ll prove the HSW (Holevo–Schumacher–Westmoreland) theorem, which provides a lower bound on the capacity of such a channel. Will the encoding scheme using entangled states raise the capacity beyond the lower bound provided by the HSW theorem? All evidence to date suggests that this doesn’t help raise the capacity, but it is still a fascinating open problem of quantum information theory.
Quantum information through quantum channels
For quantum information, we can again compress them in another way before sending them into channels, but since in general we cannot distinguish between $\ket0$ and $(\ket0+\ket1)/\sqrt2$, we aren't able to apply Shannon entropy to quantum informations. The way we use to compress the quantum information is not error-free, instead we use a measure: fidelity, to quantify the correctness of the information after decompressing from the compressed form, in the limit of large block lengths, it should tend towards the no error limit of 1.
Schumacher’s noiseless channel coding theorem quantifies the resources required to do quantum data compression, with the restriction that it be possible to recover the source with fidelity close to 1:
- source only produces orthogonal quantum states ($\ket{\psi_j}$ with probability $p_j$): the theorem reduces to classical case saying that the source may be compressed down to but not beyond the classical limit $H(p_j)$.
- for a more general case (source that produces non-orthogonal states): how much a quantum source may be compressed is not Shannon entropy ever, but von Neumann entropy (他在正交態的時候會化簡成Shannon entropy, 其餘比較廣義的情況會 strictly smaller than Shannon entropy). (e.g. a source producing the state $\ket0$ with probability $p$ and $(\ket0+\ket1)/\sqrt2$ with probablilty $1-p$ can be reliably compressed using fewer than $H(p, 1-p)$ qubits per use of the source!)
- compressing procedure for a certain scheme:
- Suppose the source emit state $\ket0$ with probability $p$ and $(\ket0+\ket1)/\sqrt2$ with probablilty $1-p$ and is repeated $n$ times, creating a total of $n$ qubits of information.
- With $\lim_{n\to\infty}$ we will have in average $np + \frac{n(1-p)}{2}$ of $\ket0$ and $\frac{n(1-p)}{2}$ of $\ket1$ in the above $n$ qubits, for such configuration there are $\binom{n}{n(1-p)/2} \xrightarrow{\text{Stirling’s approximation}} 2^{nH(\frac{1+p}{2}, \frac{1-p}{2})} \equiv N$ combinations in total.
- We can then label these combinations from $\ket{0\cdots00},\;\ket{0\cdots01}, \cdots, \;\ket{1\cdots10},\;\ket{1\cdots11}$, equivalent to performing a unitary transformation:

\[ \ket0^{\otimes\frac{n(1+p)}{2}} \ket1^{\otimes\frac{n(1-p)}{2}} \xrightarrow{\text{unitary transform}} \ket{j}\ket{0}^{\otimes\big( n-nH(\frac{1+p}{2}, \frac{1-p}{2}) \big)} \]

, and discard the tailing $\ket0$s, leaving a compressed state of $nH(\frac{1+p}{2}, \frac{1-p}{2})$ qubits.

To decomopress, we just append the previously discarded $\ket0$s and do the inverse unitary transform.

This procedure for quantum data compression and decompression results in a storage requirement of $H(\frac{1+p}{2}, \frac{1-p}{2})$ qubits per use of the source, and we can deduce whenever $p\geq 1/3$, it will be an improvement over Shannon’s noiseless channel coding theorem scheme $H(p,\;1-p)$. (這種壓縮方法的核心概念是利用$\ket0$和$(\ket0+\ket1)/\sqrt2$都在$\ket0$方向上有分量的這個redundancy, 來進行壓縮的)

Can we find an analogue of Shannon’s noisy channel coding theorem? Considerable progress on this important question has been made, using the theory of quantum error-correcting codes; however, a fully satisfactory analogue has not yet been found.
Quantum distinguishability
- As the above scheme mentioned, in general we cannot distinguish $\ket0$ from $(\ket0+\ket1)/2$. If we are able to distinguish $\{\ket0, \ket1, \ket+, \ket-\}$, we can develop a way of communication which is faster than light! (e.g. suppose Alice and Bob share a Bell's pair $\frac{\ket{00}+\ket{11}}{2}$, which is also $\frac{\ket{++}+\ket{--}}{2}$ if you do some math, then Alice can convey messages via measuring her qubit with intended basis (she can deliberately choose $Z$-measurement or $X$-measurement), and Bob's qubit will collapse into corresponding state as soon as Alice made her measurement, now Bob then use his device which is capable of distinguishing $\{\ket0, \ket1, \ket+, \ket-\}$ and he can instantaneously know what measurement does Alice perform).
- 但有時候這種quantum indistinguishability反而是一種advantage. (e.g. it can be used to built quantum-money: only the bank knows the exact sequence of $\{\ket0, \ket1, \ket+, \ket-\}$ on the note it publishes, it can attribute a unique classical serial number to each note, and then verify it by telling the merchant what will the result be after measuring with a sequence of basis the bank provides, after the merchants provide them the serial number on individual note. The counterfeiter cannot duplicate same note due to the quantum indistinguishability.)

Exercise 1.2

Explain how a device which, upon input of one of two non-orthogonal quantum states $\ket\psi$ or $\ket\varphi$ correctly identified the state, could be used to build a device which cloned the states $\ket\psi$ and $\ket\varphi$, in violation of the no-cloning theorem. Conversely, explain how a device for cloning could be used to distinguish non-orthogonal quantum states.

solution

If states are distinguishable, you can determine which state you send and then, employing an appropreate designer of Hamiltonian, build a second system in the same state.

Conversely, if you can prepare many identical copies of a qubit, then it is possible to measure the mean value of noncommuting observables.

Creation and transformation of entanglement
Creating entanglement is a simple dynamical process of interest in quantum information theory. How many qubits must two parties exchange if they are to create a particular entangled state shared between them, given that they share no prior entanglement?
Transforming entanglement from one form into another. (e.g. Alice and Bob share between them a Bell state, and wish to transform it into some other type of entangled state. What resources do they need to accomplish this task?)

Answering these and more complex questions about the creation and transformation of entanglement forms a fascinating area of study in its own right, and also promises to give insight into tasks such as quantum computation. (e.g. a distributed quantum computation may be viewed as simply a method for generating entanglement between two or more parties.)

Problem 1.1

(Feynman-Gates conversation) Construct a friendly imaginary discussion of about 2000 words between Bill Gates and Richard Feynman, set in the present, on the future of computation. (Comment: You might like to try waiting until you’ve read the rest of the book before attempting this question. See the 'History and further reading' below for pointers to one possible answer for this question.)

solution

From Bill Gates:

Thirty years ago I went on vacation and fell for Richard Feynman.

A friend and I were planning a trip together and wanted to mix a little learning in with our relaxation. We looked at a local university’s film collection, saw that they had one of his lectures on physics, and checked it out. We loved it so much that we ended up watching it twice. Feynman had this amazing knack for making physics clear and fun at the same time. I immediately went looking for more of his talks, and I’ve been a big fan ever since. Years later I bought the rights to those lectures and worked with Microsoft to get them posted online for free.

Problem 1.2

What is the most significant discovery yet made in quantum computation and quantum information? Write an essay of about 2000 words for an educated lay audience about the discovery. (Comment: As for the previous problem, you might like to try waiting until you’ve read the rest of the book before attempting this question.)

solution

Maybe try waiting until I've read the rest of the book before attempting this question.