% vim: ft=tex
\section{Introduction to Binary Quantum Computing}

\subsection{Single Qbits}
\label{ref:singleqbitsystems}

A qbit is a two-level quantum mechanical system $ \{\ket{\uparrow} \equiv \ket{1}, \ket{\downarrow} \equiv \ket{0}\} $
with $\braket{\uparrow}{\downarrow} = 0$. One can associate 
$\ket{\uparrow} \equiv \left(\begin{array}{c} 0 \\ 1\end{array} \right)$ and 
$\ket{\downarrow} \equiv \left(\begin{array}{c} 1 \\ 0 \end{array} \right)$ which
is helpful in the following discussion.

A gate operating on a qbit is a unitary operator $G \in U(2)$. One can show that
$\forall G \in U(2)$ $G$ can be arbitrarily good as a product of unitary generator matrices\cite[Chapter 4.3]{kaye_ea2007},
common choices for the generators are $ X, H, R_{\phi}$ and $Z, H, R_{\phi}$ with 
\label{ref:singleqbitgates}

\begin{equation}
    X := \left(\begin{array}{cc} 0 & 1 \\ 1 & 0\end{array}\right) 
\end{equation}
\begin{equation}
    Z := \left(\begin{array}{cc} 1 & 0 \\ 0 & -1\end{array}\right) 
\end{equation}
\begin{equation}
    H := \frac{1}{\sqrt{2}}\left(\begin{array}{cc} 1 & 1 \\ 1 & -1\end{array}\right) 
\end{equation}
\begin{equation}
    R_{\phi} := \left(\begin{array}{cc} 1 & 0 \\ 0 & \exp(i\phi)\end{array}\right)
\end{equation}

\subsection{$N$ Qbit Systems}
\label{ref:nqbitsystems}

\begin{postulate}
    A $N$ qbit quantum mechanical state is the tensor product\cite[Definition 14.3]{wuest1995} of the $N$ single qbit 
states. The $N$ qbit operators are the tensor product of the $N$ single qbit operators.
\end{postulate}

Let $\ket{0}_s := \left(\begin{array}{c} 1 \\ 0 \end{array} \right)$ and $\ket{1}_s := \left(\begin{array}{c} 0 \\ 1 \end{array} \right)$
be the basis of the one-qbit systems. Then two-qbit basis states are

\begin{equation}
    \ket{0} := \ket{0b00} := \ket{0}_s \otimes \ket{0}_s :=  \left(\begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \end{array} \right)
\end{equation}
\begin{equation}
    \ket{1} := \ket{0b01} := \ket{0}_s \otimes \ket{1}_s :=  \left(\begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \end{array} \right)
\end{equation}
\begin{equation}
    \ket{2} := \ket{0b10} := \ket{1}_s \otimes \ket{0}_s :=  \left(\begin{array}{c} 0 \\ 0 \\ 1 \\ 0 \end{array} \right)
\end{equation}
\begin{equation}
    \ket{3} := \ket{0b11} := \ket{1}_s \otimes \ket{1}_s :=  \left(\begin{array}{c} 0 \\ 0 \\ 0 \\ 1 \end{array} \right)
\end{equation}

The $N$ qbit basis states can then be constructed in a similar manner. 
A general $N$ qbit state can then be written as a superposition of the 
basis states:

\begin{equation}
    \ket{\psi} = \sum\limits_{i = 0}^{2^N - 1} c_i \ket{i} 
\end{equation}
\begin{equation}
    \sum\limits_{i = 0}^{2^N - 1} |c_i|^2 = 1
\end{equation}


FIXME: rewrite this.

One can show that the gates in \ref{ref:singleqbitgates} together with an entanglement gate, such as $CX$ or $CZ$ are enough
to generate an arbitrary $N$ qbit gate\cite[Chapter 4.3]{kaye_ea2007}.
The matrix representation of $CX$ and $CZ$ for two qbits is given by

\begin{equation}
    CX(1, 0) = \left(\begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 \end{array}\right)
\end{equation}
\begin{equation}
    CZ(1, 0) = \left(\begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & -1 \end{array}\right)
\end{equation}

Where $1$ is the act-qbit and $0$ the control-qbit. In words $CX$ ($CZ$) apply an $X$ ($Z$) gate on the act-qbit,
if the control-qbit is set.
The following notation\cite{dahlberg_ea2019} can be more handy when discussing more qbits:

\begin{equation}\label{eq:CX_pr}
    CX(i, j) = \ket{0}\bra{0}_j\otimes I_i + \ket{1}\bra{1}_j \otimes X_i 
\end{equation}
\begin{equation}\label{eq:CZ_pr}
    CZ(i, j) = \ket{0}\bra{0}_j\otimes I_i + \ket{1}\bra{1}_j \otimes Z_i 
\end{equation}

Where $i$ is the act-qbit, $j$ the control-qbit and $I_i$, $Z_i$ are the identity and Pauli $Z$ gate
operating on qbit i. Note that $CX(i, j) = H(i) CZ(i, j) H(i)$ which will be important later.

\subsection{Measurement}

\begin{postulate}

    Let $\ket{\psi} = \alpha\ket{\phi_1} \otimes \ket{1}_n + \beta\ket{\phi_0} \otimes \ket{0}_n$ be a state
    where $\ket{1}_n, \ket{0}_n$ denote the $n$-th qbit state and $|\alpha|^2 + |\beta|^2 = 1$. 
    Then the measurement of the $n$-th qbit will yield $\ket{\phi_1} \otimes \ket{1}_n$ with probability
    $|\alpha|^2$ and $\ket{\phi_0} \otimes \ket{0}_n$ with probability $|\beta|^2$.

    This is called collapse of the wave function.
\end{postulate}

Measuring a qbit will also yield a classical result $0$ or $1$ with the respective probabilities.

\begin{corrolary}
    In general the measurement of a qbit is not invertible, in particular it cannot be represented as a
    unitary operator.
\end{corrolary}

\begin{proof}
    The measuerment in not injective: Measuring both
    $\ket{0}$ and $\frac{1}{\sqrt{2}}(\ket{0} + \ket{1}$ (can) map to $\ket{0}$.

    Any unitary matrix $U$ has the inverse $U^\dagger \equiv U^{-1}$.
\end{proof}
