Back to notes

# Quantum Computation

## My notes on Quantum Computation

Topics Progress HTML PDF
Quantum Minimum Circuit Size Problems
100%

### Qubits and quantum states

Instead of classical bits, i.e., ${0,1}$, the most elementary element in quantum computation is a qubit. Mathematically, a qubit is a unit complex vector in $\C^2$ and in practice people use the orthonormal basis ${\ket{0},\ket{1}}$ as a quantum analog of the classical bits ${0,1}$. Concretely, one can think of $\ket{0}=[1\ 0]^\top$ and $\ket{1}=[0\ 1]^\top$. Intuitively, one can view $\ket{0}$ and $\ket{1}$ as the two possible outcomes of a qubit.

In quantum theory, we allow superposition, which mathematically refers to a linear combination of the vectors in the orthonormal basis. For example, \begin{equation*} \ket{+} = \frac{\ket{0}+\ket{1}}{\sqrt{2}} \end{equation*} and \begin{equation*} \ket{-} = \frac{\ket{0}-\ket{1}}{\sqrt{2}} \end{equation*} are both superposition states. In general, a single qubit quantum state can be described as \begin{equation*} \ket{\psi} = c_0\ket{0} + c_1\ket{1} \end{equation*} where $c_0,c_1\in\C$ and $|c_0|^2+|c_1|^2=1$. In other words, as hinted earlier, a unit vector in $\C^2$ corresponds to a single qubit state.

It seems that a single qubit state $\ket{\psi} = c_0\ket{0} + c_1\ket{1}$ has 4-real degree of freedom since one can write $c_0=a+ib$ and $c_1=c+id$ for some real numbers $a,b,c,d\in\R$. However, it turns out that there's only 2-real degree of freedom that is relevant to physics since physically only the ratio between $c_0$ and $c_1$ matters. Thus, it is convenient to express $\ket{\psi}=\cos(\theta/2)\ket{0}+e^{i\phi}\ket{1}$ for some $\theta,\phi\in[0,2\pi]$. Note that, a single qubit state can thus be visualized in a 3-dimensional sphere. This is also known as the Block sphere.

#### Different choices of basis

We started with the $\{\ket{0},\ket{1}\}$ basis and in general one can consider a different basis. For example, one can verify that $\{\ket{+},\ket{-}\}$ also forms an orthonormal basis for $\C^2$. This is also known as the Pauli X basis (and $\{\ket{0},\ket{1}\}$ is sometimes called the computational basis).

How to think about different choices of basis? Physically, this corresponds to different measurements or different properties of the quantum system you are studying. The most basic example would be the position basis and the momentum basis. More intuitions will be provided in later section when we talk about operators and measurements.

#### Multi-qubit states

To study a larger system, we can compose several qubits together. Mathematically, this can be done by taking tensor product of multiple copies of $\C^2$. Concretely, an $n$-qubit state is a unit vector in space $(\C^2)^{\otimes n}\cong\C^{2^n}$.

For example, $\ket{x}:=\otimes_{i=1}^n\ket{x_i}$ is an $n$-qubit state for every $x\in{0,1}^n$. In fact, $\{ \ket{x} \}_{x\in\{0,1\}^n}$ forms an orthonormal basis for $\C^{2^n}$ and is known as the computational basis. Another common example is $\ket{+}^{\otimes n}=\frac{1}{\sqrt{2^n}}\sum_{x\in{0,1}^n}\ket{x}$.

As a quantum state is modeled as a vector, it’s natural to discuss the inner product between two quantum states. As $\ket{\psi}$ describes a column vector, its conjugate transpose is denoted by $\bra{\psi}$ which is a row vector. Finally, the inner product between two quantum states $\ket{\psi}=\sum_{x\in\{0,1\}^n}\alpha_x\ket{x}$ and $\ket{\phi}=\sum_{x\in\{0,1\}^n}\beta_x\ket{x}$ is \begin{equation*} \braket{\psi}{\phi} := \sum_{x\in\{0,1\}^n}\alpha_x\beta_x \, . \end{equation*}

### Operators

Now that we know that quantum states are the basic information carriers in quantum computation, we would like to study what kind of operations we can do on top of them. In general, we should obey the physical laws in quantum theory and fortunately these laws are all mathematically well-defined (even though there might be different interpretations for them!). There are two types of operations to perform: (i) changing the state and (ii) measure a property of the state.

An evolution operator describes how quantum states change. Mathematically, an operator is a unitary matrix.

A matrix $U\in\C^N$ is unitary if $UU^\dagger=U^\dagger U=I$ where $U^\dagger=(\bar{U})^\top$ is the conjugate transpose of $U$.

There are two facts/intuitions good to know about unitary matrices in this context: a unitary matrix is invertible (moreover $U^{-1}=U^\dagger$) and all the eigenvalues of a unitary matrix has absolute value $1$.

A measurement operator is a procedure for us to obtain information about a quantum state. Unlike classical mechanics, in quantum mechanics and beyond, we in general cannot hope to obtain full information about a quantum state through physically-plausible measurements. Furthermore, a measurement could even alter a quantum state! To illustrate these unintuitive concepts, let’s first introduce the mathematical object that models measurements.

A matrix $H\in\C^N$ is Hermitian if $H^\dagger=H$.

You might wonder why physicists model a measurement as a Hermitian matrix? Mathematically, the eigenvalues of a Hermitian matrix are always real number. Physically, this turns out to make a lot of sense because we expect the outcome of a measurement to a real number.

To be more precise on modeling a measurement process, a Hermitian matrix $H$ can be spectrally decomposed as \begin{equation*} H=UDU^\dagger \end{equation*} by some unitary matrix $U$ and a real-valued diagonal matrix $D$. We will talk about the physical intuition of eigenvectors and eigenvalues of $H$ in a moment but let’s first see how a measurement works.

Let $\ket{\psi}$ be a $n$-qubit quantum state and $H=UDU^\dagger$ be a Hermitian matrix (i.e., a measurement). Denote $\ket{e_i}$ as the $i$-th eigenvector and $\lambda_i$ as the $i$-th eigenvalue of $H$. The Born’s rule says that the measurement outcome is $\lambda_i$ and the quantum state becomes $\ket{e_i}$ with probability $|\braket{e_i}{\psi}|^2$.

So far this might be a bit abstract, so let’s consider a very intuitive example: position operator. Here I’ll sacrifice some mathematical rigor to exchange for simplicity.

In quantum mechanics, the position of a particle is no longer a definite value, but is encoded inside its quantum state/wave function $\ket{\psi}$. The position operator applies to an infinite-dimensional Hilbert space and its eigenvalue-eigenvector pairs are of the form $(x,\ket{x})$ for all $x\in\R$. When the position operator measures $\ket{\psi}$, the particle will collapse into an eigenstate $\ket{x}$ and we as an observer will get an outcome value $x$ (i.e., the position of the particle) with probability $|\braket{x}{\psi}|^2$.
Unitary matrices and Hermitian matrices in general are incomparable to each other. For example a rotation matrix is unitary but not always Hermitian and $\textsf{diag}(2, 1)$ is clearly Hermitian but not unitary. Nevertheless, there's a convenient way to transform a Hermitian matrix $H$ into a unitary matrix through $H\mapsto e^{iH}$.