The Power of Quantum Computing and Quantum Operations

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

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.

Quantum Operations: Part 2

The H Gate

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

The Z gate inverts the phase of |1> to -|1>, but does nothing to |0>.

Probability, Measurement, and Superposition

Quantum Notation

Bra-ket notation

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} $.

Vector notation

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

Working with Single Qubits

The NOT gate as a matrix

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:

The H gate as a matrix

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}$:

And if applied to $\ket{0}$:

Working with Multiple Qubits

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:

The C-NOT gate in matrix form is:

SAME ENTANGLE circuit

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.

Algorithms

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.

Bernstein-Vazirani Oracle Algorithm

Exam