Alex Balgavy

Qubits “computational basis states” are $\ket{0}$ and $\ket{1}$.

You can have a superposition: $\ket{\psi} = \alpha\ket{0} + \beta\ket{1}$

Qubits can be implemented as photon polarization, electron states, etc.

When you measure, you get 0 with probability $|\alpha|^2$ and 1 with probability $|\beta|^2$

Normalization constraint: $|\alpha|^2 + |\beta|^2 = 1$. Required because $\alpha$ and $\beta$ are probabilities.

If both probabilities occur with 50%:

$\begin{aligned} |\alpha|^2 + |\beta|^2 = 1 \\ \alpha = \beta &= \frac{1}{\sqrt{2}} \end{aligned}$

This superposition is $\ket{+} = \frac{\ket{0} + \ket{1}}{\sqrt{2}}$

Measurement collapses the qubit.

With multiple qubits, write it like $\ket{01}$. Each basis state has its own probability (amplitude).

EPR pair (Bell state): $\frac{\ket{00} + \ket{01}}{\sqrt{2}}$

For a system of n qubits, we need $2^n$ amplitudes.

You can write $\alpha \ket{0} + \beta \ket{1}$ as $\alpha \begin{bmatrix} 1 \\ 0 \end{bmatrix} + \beta \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}$

Quantum gates are matrices.

NOT (“X”) is $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$.

Applying is multiplication:

$\begin{aligned} X \begin{bmatrix}\alpha \\ \beta\end{bmatrix} &= \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix}\alpha \\ \beta\end{bmatrix} \\ &= \begin{bmatrix} 0\alpha + 1\beta \\ 1\beta + 0\alpha \end{bmatrix} \\ &= \begin{bmatrix} \beta \\ \alpha \end{bmatrix} \end{aligned}$

Because of normalization, single-qubit gate must be unitary: $U^\dag U = I$ where $U^\dag$ is the transpose and complex conjugate of U.

Z gate: $\begin{bmatrix} 1 & 0 \\ 0 & -1\end{bmatrix}$ flips sign of $\ket{1}$

H gate: $\frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1\end{bmatrix}$

CNOT gate: if control 0, nothing, else target bit flipped. Two-bit input gate.

$U_{CN} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix}$

As a matrix, the coefficients of the base states $\ket{00}$, $\ket{01}$, $\ket{10}$, $\ket{11}$, in order.

For example, $\ket{10}$ is $0\ket{00} + 0\ket{01} + 1\ket{10} + 0\ket{11}$.

$\begin{aligned} \ket{10} &= \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix} \\ &= \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} \\ &= \ket{11} \end{aligned}$

In quantum circuits, convention is for input $\ket{0}$.

Cannot copy qubits! Try: start in state

$\begin{aligned} \ket{\psi}\ket{0} &= (a\ket{0} + b\ket{1})\ket{0} \\ &= a\ket{00} + b\ket{10} \end{aligned}$

Target:

$\begin{aligned} \ket{\psi}\ket{\psi} &= (a\ket{0} + b\ket{1})(a\ket{0} + b\ket{1}) \\ &= a^2 \ket{00} + ab\ket{01} + ab\ket{10} + b^2 \ket{11} \end{aligned}$

Only if $ab = 0$…which is impossible because of the normalization condition.

Toffoli gate: flip target bit if both control are 1, else nothing.

Normally quantum can’t simulate classical, because quantum gates are reversible and classical can be irreversible. Toffoli can simulate irreversible gates like NAND and FANOUT.

Quantum parallelism

To compute function f(x): input state $\ket{x, y}$ where x data and y target. $\ket{x,y} \mapsto \ket{x, y \oplus f(x)}$ is called “$U_f$”

To evaluate f(x) for both x = 0 and x = 1 simultaneously, use Hadamard on data x.

$x = H0 = \frac{\ket{0} + \ket{1}}{\sqrt{2}}$

To get the full input state, tensor product $x \otimes y$:

$\begin{aligned} \frac{\ket{0} + \ket{1}}{\sqrt{2}} \otimes \ket{0} &= \frac{\ket{0}\ket{0} + \ket{1}\ket{0}}{\sqrt{2}} \\ &= \frac{1}{\sqrt{2}} (\ket{00} + \ket{10}) \end{aligned}$

Applying f(x) for both parts of the superposition, we get

$\frac{1}{\sqrt{2}} (\ket{0, f(0)} + \ket{1, f(1)})$

So in one circuit we get info about both values of x.

Hadamard transform is $n$ H gates in parallel on n qubits.

$H\otimes^2$ is

$\begin{aligned} (\frac{\ket{0} + \ket{1}}{\sqrt{2}})(\frac{\ket{0} + \ket{1}}{\sqrt{2}}) &= \frac{\ket{00} + \ket{01} + \ket{10} + \ket{11}}{2} \\ &= \frac{1}{\sqrt{2^2}} \sum_{x} \ket{x} \end{aligned}$

But when we measure, we get only one state. Have to extract info somehow.