Quantum Computing: Introduction

Qubits 

A qubit is a well-defined quantum two-level system with states $|0\rangle$ and $|1\rangle$. Unlike a classical bit that is either 0 or 1, a qubit can be in a superposition of both $|0\rangle$ and $|1\rangle$ as $$\begin{equation}|\text{qubit}\rangle\equiv\cos\frac{\theta}{2} |0\rangle +\sin\frac{\theta}{2} e^{i\phi}|1\rangle\,.\end{equation}$$ Notes:

• Quantum states are the same up to an overall phase factor. To remove the ambiguity of the overall phase factor, we use the conversion that the coefficient in front of $|0\rangle$ is always a real positive number. $\phi$  is the relative phase difference between $|0\rangle$ and $|1\rangle$.
• Each qubit state can be one-to-one mapped to a point on the Bloch sphere. Note that the polar angle $\theta$ in the spherical coordinate system takes the value in $[0, \pi]$. To ensure the coefficient in front of $|0\rangle$ is always a real positive number, we parameterize the qubit state as $\frac{\theta}{2}$ rather than $\theta$. As a result, $|0\rangle$ and $|1\rangle$ are the north and south pole on the Bloch sphere, respectively. 

Quantum gates

A quantum gate performs reversible operation on qubits via unitary transformations:

• 1-qubit gate: to create superpositions. A prevalent example is the Hadamard gate: $$\begin{equation} H\,|0\rangle\equiv\frac{|0\rangle + |1\rangle}{\sqrt{2}}\,,\quad H\,|1\rangle\equiv\frac{|0\rangle - |1\rangle}{\sqrt{2}}\,.\tag{1}\end{equation}$$
• 2-qubit gate: to generate entanglements. The most important one is the controlled-NOT gate or CNOT gate: $|0\rangle|0\rangle|\rightarrow|0\rangle|0\rangle,\,|0\rangle|1\rangle\rightarrow |0\rangle|1\rangle,\,|1\rangle|0\rangle\rightarrow|1\rangle|1\rangle,\,|1\rangle|1\rangle\rightarrow|1\rangle|0\rangle$, or $|x\rangle|y\rangle\rightarrow |x\rangle|x\oplus y\rangle$ in short.

Any multiple-qubit gate can be built from a sequence of 1-qubit gates and the CNOT gate (universality).

Consider a bit string $x\in\{0, 1\}^n$: $x\equiv x_1x_2\cdots x_n$ with $x_i\in \{0, 1\}$ from $i$ from 1 to n, we denote the n-qubit state $|x_1\rangle|x_2\rangle\cdots|x_n\rangle$ by $|x\rangle_n$ for illustration. If performing Hadamard gate on each qubit in such state, we have $$\begin{equation} H^{\otimes n} |x\rangle_n \equiv\prod_{i=1}^n H\,|x_i\rangle =\prod_{i=1}^n \frac{|0\rangle + (-1)^{x_i} |1\rangle}{\sqrt{2}} = \sum_{y\in \{0,1\}^n}\frac{(-1)^{x\cdot y}}{2^{n/2}}|y\rangle_n\,.\tag{2}\end{equation}$$ , where $x\cdot y\equiv x_1y_1\oplus x_2y_2\oplus\cdots\oplus x_ny_n$. Especially, $$\begin{equation} H^{\otimes n} |0\rangle_n = \frac{1}{2^{n/2}} \sum_{x\in\{0,1\}^n}|x\rangle_n\,,\tag{3}\end{equation}$$ which is the equally weighted sum over all computational basis elements.

Quantum Parallelism

Suppose $f:\{0,1\}^n\rightarrow\{0,1\}^m$ is a classical function that acts on a bit string of n bits and outputs a bit string of m bits. In quantum world, we can linearly extend the classical function $f$ to a unitary transformation defined by $$\begin{equation} U_f\left(|x\rangle_n |y\rangle_m\right)=|x\rangle_n | y \oplus f(x)\rangle_m\,,\tag{4}\end{equation}$$ Especially, $$\begin{equation}  U_f\left(|x\rangle_n |0\rangle_m\right)=|x\rangle_n | f(x)\rangle_m\,.\end{equation}$$

Now $U_f$ is reversible because $U_f^2=1$: $$\begin{equation}U_fU_f\left(|x\rangle_n |y\rangle_m\right)=U_f\left(|x\rangle_n | y \oplus f(x)\rangle_m\right)=|x\rangle_n | y \oplus f(x)\oplus f(x)\rangle_m=|x\rangle_n |y\rangle_m\,.\end{equation}$$

Quantum parallelism is to use the size of the Hilbert space to evaluate a classical function $f$ for many values simultaneously: $$\begin{equation} U_f \left(H^{\otimes n} \otimes I_m\right) \left(|0\rangle_n |0\rangle_m\right) = U_f \left(\frac{1}{2^{n/2}}\sum_{x\in \{0,1\}^n}|x\rangle_n|0\rangle_m\right) = \frac{1}{2^{n/2}}\sum_{x\in \{0,1\}^n}|x\rangle_n|f(x)\rangle_m\,.\tag{5}\end{equation}$$

That is, a single action of $U_f$ prepare a state that has the information of $f(x)$ for all $x$.

No-cloning theorem

There is no unitary transformation $U$, such that for arbitrary state $|\psi\rangle$ such that $U|\psi\rangle |0\rangle = |\psi\rangle |\psi\rangle$. That is, we cannot copy a quantum state without changing it.

The proof is simple. Suppose there exists such operation, then $U|\psi\rangle |0\rangle = |\psi\rangle |\psi\rangle$ and $U|\phi\rangle |0\rangle = |\phi\rangle |\phi\rangle$. By the linearity, we have $U\,\left(a|\psi\rangle + b|\phi\rangle\right)|0\rangle=a U |\psi\rangle|0\rangle + b U |\phi\rangle|0\rangle=a|\psi\rangle |\psi\rangle+b|\phi\rangle |\phi\rangle$. But on the other hand, by the definition, we have $U\,\left(a|\psi\rangle + b|\phi\rangle\right)|0\rangle= \left(a|\psi\rangle + b|\phi\rangle\right)\left(a|\psi\rangle + b|\phi\rangle\right)$. The two results are clearly not equal for general $a, b, \psi, \phi$.

Quantum algorithms in early ages

Deutsch Algorithm

Deutsch algorithm is the first quantum computing algorithm that is faster than the best classical algorithm, although not exponentially faster. It is proposed to solve a toy problem: Given a function $f:\{0,1\}\rightarrow\{0,1\}$ that maps a bit to a bit, whether $f(0)=f(1)$ or not? A classical algorithm has to evaluate the function $f$ twice. But the quantum algorithm call the function $f$ only once: $$\begin{eqnarray}|0\rangle|1\rangle&\xrightarrow{H\otimes H}& \frac{1}{2}\left(\sum_{x\in \{0,1\}}|x\rangle\right)\left(|0\rangle-|1\rangle\right) \\ &\xrightarrow{U_f} & \frac{1}{2} \sum_{x\in \{0,1\}}|x\rangle \left(|0\oplus f(x)\rangle-|1\oplus f(x)\rangle\right) = \frac{1}{2}\left(\sum_{x\in \{0,1\}}(-1)^{f(x)}|x\rangle\right)\left(|0\rangle-|1\rangle\right)\\ &\xrightarrow{H\otimes I}&\frac{1}{2\sqrt{2}} \left(\sum_{x,y\in \{0,1\}}(-1)^{f(x)+x\cdot y}|y\rangle\right)\left(|0\rangle-|1\rangle\right)\end{eqnarray}$$ The first qubit is finally in the state $\left((-1)^{f(0)}+(-1)^{f(1)}\right)|0\rangle+\left((-1)^{f(0)}-(-1)^{f(1)}\right)|1\rangle$. The measurement of the first qubit is $|0\rangle$ if $f(0)=f(1)$ and $|1\rangle$ otherwise. 

Bernstein-Vazirani Algorithm

As an extension to the Deutsch algorithm, Bernstein-Vazirani algorithm is to find out the secrete bit string $s\in \{0, 1\}^n$ in the boolean function $f_s(x)\equiv s\cdot x$. The classical solution is to call the function $f_s$ n times. For each $i$ from 1 to n, one feed in a bit string $x$ with only $x_i=1$ and others zero, and the output of $f_s$ is then $s_i$. The quantum solution only requires ONE call to the function $f_s$: $$\begin{eqnarray}|0\rangle_n |1\rangle&\xrightarrow{H^{\otimes (n+1)}}&\frac{1}{2^{(n+1)/2}} \left(\sum_{x\in\{0,1\}^n}|x\rangle_n\right)\left(|0\rangle-|1\rangle\right) \\ &\xrightarrow{U_{f_s}}& \frac{1}{2^{(n+1)/2}} \sum_{x\in\{0,1\}^n}|x\rangle_n\left(|f_s(x)\rangle-|1\oplus f_s(x)\rangle\right) = \frac{1}{2^{(n+1)/2}} \left(\sum_{x\in\{0,1\}^n}(-1)^{s\cdot x}|x\rangle_n\right)\left(|0\rangle-|1\rangle\right) \\ &\xrightarrow{H^{\otimes n}\,\otimes I}&|s\rangle_n\frac{|0\rangle-|1\rangle}{\sqrt{2}}\,.\end{eqnarray}$$

Simon's Algorithm

Simon's algorithm is the first quantum computing algorithm that is exponentially faster than the best classical algorithm. It is proposed to solve another toy problem: Given a two-to-one function $f_s:\{0, 1\}^n\rightarrow \{0, 1\}^n$, find out the secrete bit string $s\in \{0, 1\}^n$ such that $f_s(x)=f_s(x\oplus s)$. A special case is that $s=0$, in which $f_s$ becomes a one-to-one map. 

Classically, we have to check up to $2^{n-1}+1$ inputs. If we are lucky, we can find out $s$ by the first two tries. But if $s=0$ or we are really unlucky, we have to check all the $2^{n/2}+1$ inputs. So a classical algorithm takes time $\Omega(2^n)$. A quantum solution solves this problem in $O(n)$ times: $$\begin{eqnarray}|0\rangle_n|0\rangle_n&\xrightarrow{H^{\otimes n} \,\otimes I^{\otimes n}}&\frac{1}{2^{n/2}} \left(\sum_{x\in\{0,1\}^n}|x\rangle_n\right)|0\rangle_n \\&\xrightarrow{U_{f_s}}& \frac{1}{2^{n/2}} \sum_{x\in\{0,1\}^n}|x\rangle_n |f_s(x)\rangle_n \\ &\xrightarrow{\text{Measure to } |f_s(x)\rangle_n}&\frac{1}{\sqrt{2}}\left(|x\rangle_n+|x\oplus s\rangle_n\right)\\ &\xrightarrow{H^{\otimes n}} &\frac{1}{2^{(n+1)/2}}\sum_{y\in \{0,1\}^n} \left((-1)^{x\cdot y} +(-1)^{(x\oplus s)\cdot y}\right)|y\rangle_n\,.\end{eqnarray}$$ Finally, measuring the first register to the state $|y\rangle_n$ only if $y\cdot s=0$. Repeating $n$ times gives $n$ such linear equations, from which we can solve $s$.