Introduction to Quantum

In physics

How particles behave.
Scientists noticed that real experiments showed some weird results.
Results could be explained only by assumption that the universe is quantum.
Study of quantum.

In mathematics

What if the probability can be negative? The only meaningful answer is quantum.

Classical and Quantum Probability

Event $v:(p_1,\cdots,p_n)$ with $n$ possible outcomes, where $$ \sum_{i=1}^np_i=1. $$ Equivalently, $$ \vert\vert v\vert\vert_1=1. $$ What if we require $\vert\vert v\vert\vert_2=1$? We get quantum.

Example

A biased coin, $v=(p,1-p)$. $\vert\vert v\vert\vert_1=1$.

A quantum biased coin, $v=(\alpha,\beta)$. In the vector there's amplitude instead of probability.

$\vert\vert v\vert\vert_2=\sqrt{\alpha^2+\beta^2}=1$, where $\alpha,\beta\in\mathbb C$.
The probability is $\vert\alpha\vert^2,\vert\beta\vert^2$.

In this setting, same probability but different amplitude means different things: $v_1:(1/\sqrt2,1/\sqrt2),v_2:(1/\sqrt2,-1/\sqrt2)$ are different.

Operations

Operations on classical probabilities $v$. We describe an operation on $v$ by stochastic matrix. The matrix must preserves $1$-norm.

Operations on amplitude. We describe an operation by a unitary matrix, which preserves $2$-norm.

Recap of unitary matrix $M$:

$M^{-1}=M^*$, the reverse of $M$ is the conjugate transpose matrix.

$M\times M^*=M^*\times M=I$.

酋矩阵：逆矩阵等于其共轭转置矩阵

Why do we introduce complex number? Because we want to see how universe $v$ evolves in $1/2$ time steps.

Qubits

Examples:

$v^\top=(\alpha,\beta)^\top=\alpha\vert0\rangle+\beta\vert1\rangle$.
$v^\top=(0,0,0,1/\sqrt2,0,0,1/\sqrt2,0)^\top=1/\sqrt{2}(\vert3\rangle+\vert6\rangle)$

Let $v=\vert0\rangle=(1,0)^\top$, a qubit that is deterministically $0$.

Let an unitary matrix $$ M=\frac{1}{\sqrt2} \begin{pmatrix} 1&-1\ 1&1 \end{pmatrix}. $$ We apply $M$ on $v$ multiple times:

$v_1^\top=M\times v^\top=\frac{1}{\sqrt2}(1,1)^\top=\frac{1}{\sqrt2}(\vert0\rangle+\vert1\rangle)$

$v_2^\top=M^2\times v^\top=M\times v_1^\top=(0,1)^\top=\vert1\rangle$

$v_3^\top=M^3\times v^\top=M\times v_2^\top=\frac{1}{\sqrt2}(-1,1)^\top=\frac{1}{\sqrt2}(-\vert0\rangle+\vert1\rangle)$

$v_4^\top=M^4\times v^\top=M\times v_3^\top=(-1,0)^\top=-\vert0\rangle$

We can see that $v_1,v_3$ have the same probability distributions, but different amplitudes.

Arithmetic on Qubits

$1$ qubit: $\alpha\vert0\rangle+\beta\vert1\rangle$

$2$ qubits: $\alpha_1\vert00\rangle+\alpha_2\vert01\rangle+\alpha_3\vert10\rangle+\alpha_4\vert11\rangle$

A famous $2$ qubits state: Bell state $$ \vert\Phi^{+\rangle=\frac{1}{\sqrt2}(\vert00\rangle+\vert11\rangle)=(1/\sqrt2,0,0,1/\sqrt2)}\top. $$

It guarantees that both bits observe the same $1$ or $0$ with equal probability (amplitude).

$n$ qubits can be described by a vector of amplitudes with length $2^n$: $$ \vert\psi\rangle=\sum_{z\in{0,1}^n}\alpha_z\vert z\rangle $$ Unitary matrix: transform a quantum state into another one.

Quantum computing is to constructing (or find) the unitary matrix for solving problems.

In practice, it is not feasible to compute $2^n\times2^n$ matrix multiplications. We aim to define matrices that can be obtained (approximated) by composing "small" unitary matrices.

Those "small" unitary matrices is called quantum gates (aka quantum circuits).

Uniform quantum algorithm: $\forall n$, output in $\mathsf{poly}(n)$ time a quantum circuit of $\mathsf{poly}(n)$ size that solves a given problem on all instances of size $n$.