Type | Class |
---|---|

Tags | Project: Online Classes, mooc, quantum computing |

- UChicagoX QUAN11000

Table of Contents

Quantum computing may be good for:

- Simulations of natural processes, e.g. chemical simulation, which have a large solution space
- Optimization problems, e.g. the travelling salesman problem
- Encryption
- Machine learning, image/audio generation

It's hard to scale quantum computers.

Encryption techniques that depend on the difficulty of factoring large numbers will be broken if a method is discovered of factoring such numbers quickly. **Shor's algorithm** is a quantum algorithm to factor numbers. We do not presently have quantum computers powerful enough to run Shor's algorithm on large keys such as are used today, but as quantum computers grow more powerful, messages encrypted with weaker keys will become vulnerable.

The H gate has a 50% chance of giving either result upon measurement. However, it's not simply a purely random 50% chance of applying a NOT. If you apply the H gate twice in a row, you will recover the input. There is additional state (called **phase**) stored on the qubit that is lost in measurement.

The Z gate inverts the phase of `|1>`

to `-|1>`

, but does nothing to `|0>`

.

Represent quantum states with **bra-ket** notation: $ a\ket{0} + b\ket{1} $ means that $ |a|^2 $ is the probability of measuring 0 and $ |b|^2 $ is the probability of measuring 1. So we know $ |a|^2 + |b|^2 = 1 $.

If we have an equal chance of measuring 0 or 1, then the state would be $ \frac{1}{\sqrt{2}}\ket{0} + \frac{1}{\sqrt{2}}\ket{1} $.

In vector notation, write $ a\ket{0} + b\ket{1} $ as $ \begin{bmatrix} a \ b \end{bmatrix} $.

A `NOT`

gate is the matrix \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}. We apply a gate to a qubit by multiplying them, with the gate on the left and the qubit on the right. So to apply the `NOT`

gate to \ket{1}, we write:

\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 0 \\ 1 \end{bmatrix} =
\begin{bmatrix} 0*0 + 1* 1 \\ 1*0 + 0*1 \end{bmatrix} =
\begin{bmatrix} 1 \\ 0 \end{bmatrix}

The H gate is the matrix \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}. If we apply it to \ket{1}:

\begin{equation}
\frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \\
\frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ -1 \end{bmatrix}
\end{equation}

And if applied to \ket{0}:

\begin{equation}
\frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \\
\frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix}
\end{equation}

If we have two independent (not entangled) qubits, we can write them in a combined way. If qubit 1 is a\ket{0} + b\ket{1} and qubit 2 is c\ket{0} + d\ket{1}, then to express them jointly, we can write ac\ket{00} + ad\ket{01}+ bc\ket{10} + bd\ket{11}. This is called a **tensor product**.

For a concrete example, if Q1 is \frac{1}{2}\ket{0} + \frac{\sqrt{3}}{2}\ket{1} and Q2 is 0\ket{0} + 1\ket{1}, then the combined representation is 0\ket{00} + \frac{1}{2}\ket{01} + 0\ket{10} + \frac{\sqrt{3}}{2}\ket{11}. In vector notation, that would be \begin{bmatrix}0 \\ \frac{1}{2} \\ 0 \\ \frac{\sqrt{3}}{2} \end{bmatrix}.

The SWAP gate in matrix form is:

\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}

The C-NOT gate in matrix form is:

\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0
\end{bmatrix}

Given input WW, this circuit gives a 50% probability of each qubit being measured W or B, but both members of the pair will be the same, so there is overall a 50% probability each of WW or BB, and WB or BW are impossible.

When doing multi-qubit operations, phase is associated with a *pair* of qubits. The example is given of a **controlled Z** gate, **C-Z**. This is a gate that inverts the phase of its target only when the control is \ket{1} (and, as we know, the Z gate does nothing to \ket{0}). Given input \ket{11}, the output of that gate is -\ket{11}–notice that it is not specified that one or the other of the qubits in the pair has received the negative phase.

This first course in quantum computing is for novices and requires learners to have only basic algebra. It covers the future impacts of quantum computing, provides intuitive introductions of quantum physics phenomenon, and progresses from single operations to a complete algorithm.

Name | Role |
---|---|

Diana Franklin | Instructor |

Kate Smith | Instructor |