Quantum Computing

---

Shortcut to this page: ntrllog.netlify.app/quantum

Notes provided by Professor Negin Forouzesh (CSULA), Quantum Computing for Computer Scientists, Quantum Soar, and minutephysics

Apparently complex numbers are used a lot in quantum mechanics. So this will start off with some light review of complex numbers and linear algebra.

Complex Numbers (Algebraically)

A complex number `c` is an expression `c=a+bi` where `a,b in RR`. `a` is referred to as the real part of `c` and `b` is the imaginary part of `c`.

With this in mind, we can also define a complex number as an ordered pair of real numbers: `c=(a,b)`.

Addition and Subtraction

Let `c_1=(a_1,b_1)` and `c_2=(a_2,b_2)` be two complex numbers.

Multiplication

Division

Conjugation

Changing the sign of only the imaginary part of a complex number is called conjugation. Formally, if `c=a+bi`, then the conjugate of `c` is

Modulus

The modulus of a complex number `c=a+bi` is

and is denoted as `abs(c)`. It's the "length" of a complex number when thinking about it geometrically.

Complex Numbers (Geometrically)

As we've seen, we can represent complex numbers as ordered pairs. This naturally leads to the idea of them being graphable on a plane.

Cartesian Representation

For example, the complex number `2+3i` would look like

So we can think of complex numbers as vectors on the complex plane.

Notice that if we calculate the length of the vector, we get the modulus. So the "length" of a complex number `c=a+bi` is `|c|=+sqrt(a^2+b^2)`.

Polar Representation

To convert a complex number from Cartesian coordinates to polar coordinates, we need `rho` and `theta`:

To go back from polar to Cartesian:

Multiplication

Let `c_1=(rho_1,theta_1)` and `c_2=(rho_2,theta_2)`.

Complex Vector Spaces

A complex vector space is a set of vectors where each element of a vector is a complex number.

For example, `CC^4` is the set of `4`-element vectors and an element of `CC^4` would look like this:

`CC^(mxxn)` is the set of `mxxn` matrices, and it is also a complex vector space.

For a complex matrix `A`,

• the conjugate of `A`, denoted `bar A`, is obtained by conjugating each element of `A`
• the adjoint of `A`, denoted `A^†`, is obtained by transposing and conjugating `A`

Basis

A set of complex vectors `B` is a basis of a complex vector space if

• every vector can be written as a linear combination of vectors from `B`
• `B` is linearly independent

Inner Products

For two vectors `V_1=[[r_0],[r_1],[vdots],[r_n]]` and `V_2=[[r_0'],[r_1'],[vdots],[r_n']]`, the inner product is defined as

For complex vectors, the inner product is defined as

Norm

The norm (length) of a vector `V` is defined as

Orthogonal/Orthonormal

Two vectors are orthogonal if their inner product is equal to `0`.

A basis is orthogonal if all the vectors in the basis are pairwise orthogonal to each other.

An orthogonal basis is orthonormal if all the vectors in the basis is of norm `1`.

Hermitian Matrices

A complex matrix `A` is hermitian if `A^†=A`.

Unitary Matrices

A matrix is unitary if the matrix is invertible, and its inverse is its adjoint.

A matrix `A` is invertible if there exists `A^(-1)` such that

Tensor Product

For vectors,

For matrices,

Quantum Architecture

Now that the linear algebra is over, we'll look at the components of quantum computers.

Bits and Qubits

A bit is a unit of information describing a classical system that has only two states (a two-dimensional classical system). Typically these states can be thought of as "on" and "off" or "true" and "false" and are represented by `0` and `1`.

We denote the states as `|0:)` and `|1:)`, which can be represented as matrices `[[1],[0]]` and `[[0],[1]]` respectively. We can think of it as having a `1` in the `0^text(th)` index, so that represents the `|0:)` state and having a `1` in the `1^text(st)` index, so that represents the `|1:)` state. This is reflected with the notation

A qubit is a quantum bit. So it is a unit of information describing a two-dimensional quantum system. We can also represent a qubit using a matrix, but instead of just `0`s and `1`s, the entries are complex numbers. So `[[c_0],[c_1]]` represents a qubit.

A qubit also has the requirement that `abs(c_0)^2+abs(c_1)^2=1`. This is because `abs(c_0)^2` is the probability that the qubit is in state `|0:)` and `abs(c_1)^2` is the probability that the qubit is in state `|1:)`. In a sense, a qubit is in both states at the same time until it is measured. Once a qubit is measured, it collapses to become a bit, which at that point, means it is definitively either in state `|0:)` or `|1:)`.

Suppose we have two qubits `|0:)` and `|1:)`. They can be written as a pair of qubits as `|0:) otimes ``|1:)` or `|0 otimes 1:)`. If we calculate the tensor product, we end up with

The tensor product is implicitly understood, so it can also be denoted as `|01:)`.

Classical Gates

Gates are operators that manipulate bits. They take in bits as input and outputs one bit. The classical gates are pretty much just the boolean operators. We can represent gates with matrices.

NOT Gate

NOT of `|0:)` equals `|1:)` and NOT of `|1:)` equals `|0:)`. The matrix representation is

AND Gate

The matrix representation of the AND gate is

OR Gate

The matrix representation of the OR gate is

NAND Gate

NAND is "not and". The matrix representation of the NAND gate is (unsurprisingly)

Sequential Operations

There's another way to derive the matrix for the NAND gate. NAND is the result of performing the AND operation followed by the NOT operation. We can sequentially apply the operations one by one, but we can also multiply their matrices to get the matrix that produces the same result.

If the input of one operation depends on the output of another operation, then those are sequential operations.

Parallel Operations

If two operations are working with different bits and their inputs and outputs don't depend on each other, then those operations are parallel. With parallel operations, we perform tensor multiplication between them.

For example, consider one of DeMorgan's laws:

The matrix representation of this is

The two NOT operators in `not P ^^ not Q` are acting on different bits, so they are parallel.

The outermost NOT operator can only be performed after the AND operator, so they are sequential.

Reversible Gates

In the quantum world, only reversible operations are allowed. Reversible means that you can look at the output and know what the original input was.

For example, the NOT operation is reversible because if the output is `|0:)`, we know the input was `|1:)` (and vice versa). The AND operation is not reversible because if the output is `|0:)`, we don't know if the input was `|00:)`, `|01:)`, or `|10:)`.

Controlled-NOT (CNOT) Gate

Another reversible gate is the controlled-NOT gate. It has two inputs and two outputs.

The top input is called the control bit because it controls what the output will be. The black filled circle indicates that the input to the left of it is the control bit. If the control bit is `|0:)`, then the bottom output stays the same.

If the control bit is `|1:)`, then the bottom output is calculated depending on what type of operation the gate is. In the CNOT gate, the bottom output is the exclusive or of `|x:)` and `|y:)`.

The matrix representation of the CNOT gate is

The CNOT gate is reversible because it can be reversed by itself (meaning that we apply the CNOT operation twice). Here's what that looks like:

Quantum Gates

(The reversible gates are also quantum gates, but idk, we'll have a separate quantum gates section.)

Hadamard Gate

The Hadamard gate is a gate that puts a qubit into a superposition where both states `|0:)` and `|1:)` are equally likely. The matrix representation is

Bloch Sphere

Similar to how a complex number can be visualized as an arrow on a 2D plane, a qubit can be visualized as an arrow in a sphere.

The north pole of the Bloch sphere corresponds to `|0:)` and the south pole corresponds to `|1:)`. If the qubit is pointing more north, then it is more likely to collapse to `|0:)` when it is measured.

If we rotate the qubit around the `z` axis, we are performing a phase change.

Classical to Quantum

Here, we'll look at how to represent a real-world situation with a model and how to do the same in the quantum world.

Classical Deterministic Systems

(The book uses marbles and vertices, but it's Halloween season as I'm writing this, so mazes and people instead!) Imagine we had a maze with `6` rooms.

There are currently `6` people in room `0`, `2` people in room `1`, and so on. The arrows point to the next room that everyone will be moving to. So after following the arrows once (which we'll refer to as a "time click"), all `6` people in room `0` will be moving to room `5`, and all `10` people in room `5` will be moving to room `2`, and so on.

We can represent this transition as a matrix:

(This matrix can be interpreted as: the room indicated by the row index is receiving from the room indicated by the column index. So room `4` (row index `4`) is receiving from room `2` (column index `2`)).

If we represent the current state of the maze with the vector `[[6],[2],[1],[5],[3],[10]]`, we can multiply it by the matrix to find out what the next state of the maze will be:

For example, this means that there will be `12` people in room `2`, which we can manually confirm is true.

If we want to get the state of the maze after two time clicks, we repeat the process but with the new current state.

Probabilistic Systems

Let's consider a different type of maze with `3` rooms and only `1` person.

For example, if the person is in room `0`, they have a `1/3` chance of choosing to go to room `1` and a `2/3` chance of choosing to go to room `2`.

Suppose we came late and we don't know where the person started. Let's say there's a `1/6` chance they're in room `0`, a `1/6` chance they're in room `1`, and a `2/3` chance they're in room `2`, i.e., the current state of the maze can be represented as `[[1/6],[1/6],[2/3]]`.

We can find out the probabilities for which room they might be in after one time click by multiplying the transition matrix by the current state:

So after following the arrows once, there's a `21/36` chance the person is in room `0`, a `9/36` chance the person is in room `1`, and a `6/36` chance the person is in room `2`.

Probabilistic Double-Slit Experiment

(The book uses bullets and targets, but bullets kinda seem like they don't really make sense in this example.) Suppose we're playing a carnival game where we're throwing baseballs through one of two holes. Behind the holes is a mechanism that will then shoot the baseballs at one of three targets. (Assume we're good enough that we always successfully throw the baseballs into a hole, and that the mechanism always hits a target.)

Let's say it takes one time click for a baseball to reach the hole and another time click for the baseball to hit a target. The transition matrix is

As we saw earlier in the deterministic maze, we can get the state of the system after two time clicks by calculating the next state twice. Another way to get the state of the system after two time clicks is to instead multiply the transition matrix by itself twice:

If the baseball starts at position `0`, then the state of the baseball is `[[1],[0],[0],[0],[0],[0],[0],[0]]`. After two time clicks, the state of the baseball is

Notice that the probability of the baseball hitting target `5` is `1/3` because there is a `1/6+1/6=1/3` chance of hitting target `5`.

Quantum Systems

The difference between quantum systems and classical probabilistic systems is that quantum systems deal with complex numbers as probabilities while classical probabilistic systems use real numbers as probabilities.

The fact that complex numbers are used as probabilities is significant because complex probabilities can decrease when added together. Real-numbered probabilities can only increase when added together.

For example, if `c_1=5+3i` and `c_2=-3-2i`, then

but

which is less than both `34` and `13`.

The fact that complex numbers can cancel each other out when added is referred to as interference.

An example of a quantum system could look like this:

for which the corresponding transition matrix is

Quantum Double-Slit Experiment

Instead of baseballs and targets, we will now look at photons and measuring devices. We will also deal with complex probabilities, but the setup is still the same as the classical one.

The adjacency matrix is

The modulus squared of the matrix is

This is actually the exact same transition matrix as the transition matrix for the baseball game after one time click. (Which, if we think about it, shouldn't be too surprising since the probabilities in both systems are the same.)

But let's see what the transition matrix is after two time clicks.

In terms of the modulus squared:

This is actually almost the exact same transition matrix as the transition matrix for the baseball game after two time clicks. The only difference is row index `5`, column index `0`.

So what happened here?

There's a `1/sqrt(2)((1-i)/sqrt(6))+1/sqrt(2)((-1+i)/sqrt(6))=(1-i)/sqrt(12)+(-1+i)/sqrt(12)=0/sqrt(12)=0` chance of hitting measurement device `5`.

This is a seemingly strange phenomenon: even though there are two ways for a photon to reach measurement device `5`, there will be no photons measured by device `5`. Interference at its finest!

Quantum Theory

This will be a formalized review of all the theory we saw so far, along with some new quantum mechanics stuff.

Quantum States

An arbitrary state `|psi:)` is a linear combination of all the possible basic states with complex weights. I.e.,

These weights are called complex amplitudes.

There is a natural mapping:

The state `|psi:)` is called a superposition of all the basic states. This means that an object in state `|psi:)` is simultaneously in all `{x_0,x_1,...,x_(n-1)}` locations.

But when we measure an object (e.g., observe a particle), it collapses to a specific location. The complex amplitudes give us the probability of the object being in each location. Specifically,

Spin

Electrons "spin". I think there are infinitely many "directions" it could be spinning, but when we measure an electron, it can only be found spinning "up" or "down".

The generic state for the spin is

State Transitions

Suppose we have a start state `|psi:)``=[[c_0],[c_1],[vdots],[c_(n-1)]]` and an end state `|psi':)``=[[c'_0],[c'_1],[vdots],[c'_(n-1)]]`. How likely is it that the start state will end up in the end state? We can measure this by looking at the transition amplitude. To calculate the transition amplitude, we calculate the inner product.

We start by getting the adjoint of the end state. This state is called a bra, and it is denoted as `(:psi'|`.

The transition amplitude is then calculated as

Oh, one thing I forgot to mention is that the states should be normalized first before computing the inner product.

Quantum Entanglement

Consider a two-particle system where the first particle can only be either `x_0` or `x_1` and the second particle can only be either `y_0` or `y_1`.

Suppose we have a state

Let's see if we can write `|psi:)` as the tensor product of two states coming from the two subsystems. In other words, let's see if we can rewrite this state as the tensor product of the first particle with the second particle. In math, let's see if we can find `c_0,c_1,c'_0,c'_1` such that `|psi:)=(c_0``|x_0:)+c_1``|x_1:))otimes(c'_0``|y_0:)+c'_1``|y_1:))`.

Well, we can rewrite it as

This means that the state `|psi:)=``|x_0:)otimes``|y_1:)+``|x_1:)otimes``|y_1:)` is separable.

Let's now consider the state

We can see that it's not possible to rewrite this as a tensor product of `x`s and `y`s. So this state is entangled.

Quantum Algorithms

For this section, I'll be using a boxed `M` in the diagrams to represent the measurement operator.

Deutsch's Algorithm

Consider a function `f:{0,1}mapsto{0,1}`. We say that the function is balanced if `f(0)nef(1)` and constant if `f(0)=f(1)`. Suppose that we wanted to know for any given `f`, if it is balanced or constant.

Of course, with classical computers, we can easily see if any function is balanced or constant. We simply evaluate `f(0)` and then `f(1)`. But this requires `f` to be evaluated twice. With quantum computers, we can do better.

Suppose we have a function `f` that takes `0` to `1` and `1` to `0`, i.e., `f(0)=1` and `f(1)=0`. We can represent this function as a matrix:

However, if we want to work in the quantum world, we need to work with unitary matrices. So we need to define a new function `U_f` that encodes `f` as a unitary matrix.

One way to do this is with the following quantum gate `U_f`:

`U_f` is also sometimes referred to as the "oracle".

The corresponding unitary matrix for `U_f` is

Deriving Deutsch's Algorithm: Attempt 1

So we have this new function `U_f` and we want to use it to determine if `f` is balanced or constant (without having to evaluate `f(x)`).

Let's, arbitrarily, start both inputs at `|0:)` and try applying the Hadamard gate on the top input:

In terms of matrices, this circuit is

Applying the Hadamard gate to the top input, we get

Multiplying with `U_f`, we get

If we measure the bottom qubit, there is a `50%` chance that it will be in state `|f(0):)` and a `50%` chance that it will be in state `|f(1):)`. This doesn't really help us determine if `f` is balanced or constant, so on to attempt 2!

Deriving Deutsch's Algorithm: Attempt 2

This time, let's start the bottom qubit at `|1:)` and put it in superposition:

If we measure the bottom qubit, it will be either in state `|0:)` or `|1:)`. Again, this doesn't really help us determine if `f` is balanced or constant, so on to attempt 3!

Deriving Deutsch's Algorithm: Attempt 3

(Spoiler alert: this will be the actual correct algorithm.)

Let's put both inputs into a superposition. And add another Hadamard to the top input for good measure (pun not intended).

Factoring out `|0:)` and `|1:)`,

Applying `U_f`,

"Distributing" the `oplusf(0)` and `oplusf(1)`,

Factoring out `1/sqrt(2)``(``|0:)-``|1:))`,

Let's take a closer look at `|0:)``(-1)^(f(0))+``|1:)``(-1)^(f(1))`. Note that if `f(0)=f(1)`, then we get

which we can simplify to

Note that if `f(0)!=f(1)`, then we get

which we can simplify to

So we have

and

If we measure the top qubit and it's `|0:)`, then `f` is a constant function. If we measure the top qubit and it's `|1:)`, then `f` is a balanced function.

We Saved One Computation. So What?

As mentioned earlier, to determine if a function is balanced or constant using classical computers, we need to evaluate `f` twice. But with this quantum algorithm, we only need to perform one measurement. Going from two evaluations to one may not seem like a big deal*, but it gets pretty significant when the problem is scaled, which is what we'll look at next.

*To be fair, this problem is very contrived, so one could argue that it's not a big deal to begin with.

Deutsch-Josza Algorithm

Let's now consider functions from `{0,1}^n` to `{0,1}`. A function `f:{0,1}^n mapsto {0,1}` is constant if all the inputs go to `0` (or all the inputs go to `1`), and balanced if exactly half of the inputs maps to `0` (and the other half maps to `1`).

Here's an example of a constant function for `n=3`:

`x`	`f(x)`
`000`	`0`
`001`	`0`
`010`	`0`
`011`	`0`
`100`	`0`
`101`	`0`
`110`	`0`
`111`	`0`

Here's an example of a balanced function for `n=3`:

`x`	`f(x)`
`000`	`0`
`001`	`0`
`010`	`0`
`011`	`0`
`100`	`1`
`101`	`1`
`110`	`1`
`111`	`1`

If we want to find out whether a function is constant or balanced using classical computers, we have to evaluate `f` at most `2^(n-1)+1` times. With quantum computers, we only need to perform one measurement.

We'll use the same oracle as before, but with a slight modification.

The `/n` means that there are `n` qubits (it's kinda like saying there are `n` of these lines). The bolded `bb x` is a binary string, so `|bbx:)=``|x_0x_1...x_(n-1):)`. For example,

With this oracle, let's jump straight into the circuit for the Deutsch-Josza algorithm:

`H^(otimesn)` is the tensor product of `n` Hadamard matrices. For example, `H^(otimes3)=HotimesHotimesH`.

It turns out that `H^(otimesn)``|bb0:)` simplifies to a nice expression. We can derive it by looking at the pattern for different values of `n`, starting with `n=2`:

Now for `n=3`:

So the general pattern is

Going back to our analysis,

Using the identity we derived previously for `U_f``|x:)H``|1:)`, we get

For simplifying `H^(otimesn)``|bbx:)`, we can't use `H^(otimesn)``|bb0:)=``1/sqrt(2^n)sum_(bbx in{0,1}^2)``|bbx:)` since this is only for the state with all `0`s.

It turns out that for any `x_i`,

Let's see if there's some sort of pattern we can derive. We'll look at `n=3`.

Taking the tensor product, we get

Simplifying the exponents,

There's actually an interesting pattern here. Notice that for each term with a `(-1)^(x_i)`, there's a `1` in the `i^(th)` spot. Using this, we can rewrite the exponents as inner products:

Which we can then rewrite compactly as

For general `n` then, we have

Now that we have a simplified expression for `H^(otimesn)``|bbx:)`, we can continue our analysis of the algorithm.

It would be helpful to isolate the `f(bbx)`, and we can do this by setting `bbz=bb0`.

This is the probability that the top `n` qubits collapse to state `|bb0:)`. And the probability is dependent on `f(bbx)`. If `f(bbx)` is constant at `0`, we have

Since there are `2^n` strings in `{0,1}^n`, the summation results in

If `f` is constant at `1`, we have

So if `f` is constant, the probability that the top `n` qubits collapse to state `|bb0:)` is `1`.

If `f` is balanced, then half of the inputs will result in `f(bbx)=0` and the other half will result in `f(bbx)=1`.

Everything will cancel out with each other and we'll end up with

So if `f` is balanced, the probability that the top `n` qubits collapse to state `|bb0:)` is `0`.

How do we apply these results for the algorithm? If we measure the top `n` qubits and they're in the state `|bb0:)`, then `f` is constant. If they're in any state other than `|bb0:)`, then the function is balanced.

Simon's Algorithm

Moving away from constant and balanced functions, we'll now look at something different.

Let's consider a function `f:{0,1}^n mapsto {0,1}^n`. Suppose there exists a secret binary string `bbc=c_0c_1...c_(n-1)` such that for all strings `bbx,bby in {0,1}^n`, we have `f(bbx)=f(bby)` if and only if `bby=bbxoplusbbc`. The goal of Simon's algorithm is to find out what `bbc` is.

Well, okay, what does this problem even mean in the first place? Let's look at an example with `n=2`.

Suppose we're given these values in the table below. The rule is that all `bbx` entries that have the same `f(bbx)` values are related to each other.

`bbx`	`f(bbx)`
`00`	`00`
`01`	`11`
`10`	`00`
`11`	`11`

So `00` and `10` are related to each other, and `01` and `11` are related to each other. The way they're related is that `00oplusbbc=10` and `01oplusbbc=11`. The goal is to find out what `bbc` is.

The oracle we'll be using for Simon's algorithm is

And the circuit for Simon's algorithm is

Using the last two updated identities really makes things a lot easier here.

We're given that `f(bbx)=f(bbxoplusbbc)`. This means that the coefficient for `|bbz:)``|f(bbx):)` and the coefficient for `|bbz:)``|f(bbxoplusbbc):)` should be the same.

From this, we can see that the only way that the coefficients will be the same is if `(:bbc,bbz:)=0`. This means that when we measure the top qubits, the only results that are possible are the binary strings such that the inner product of that string with `bbc` is `0`.

Let's see Simon's algorithm in action with our `n=2` example.

`bbx`	`f(bbx)`
`00`	`00`
`01`	`11`
`10`	`00`
`11`	`11`

At this point, if we were to measure the top 2 qubits, there is a `50%` chance that they'll collapse to `|00:)` or `|01:)`. (There's a `2/4` chance that the whole system collapses to `|00:)otimes``|00:)` or `|00:)otimes``|11:)`, and a `2/4` chance that the whole system collapses to `|01:)otimes``|00:)` or `|01:)otimes``|11:))`.)

Let's arbitrarily say that this time it collapses to `|00:)`. From analyzing the algorithm, we know that `(:00,bbc:)=0`. If we let `bbc=c_1c_2`, then we have

There isn't enough information to determine what the values of `c_1,c_2` are (since they could both be `0` or `1`). So we need to run the algorithm again to (hopefully) get a different equation after measurement.

Let's say that on the second run of the algorithm, the top 2 qubits collapse to `|01:)`. Then we have

Now we know for sure that `c_2=0`. It's not obvious from looking at these two equations alone, but we do, in fact, also know that `c_1!=0`. This comes from the note earlier in this section about one-to-one and two-to-one functions. This example is dealing with a two-to-one function, so `bbc!=00 implies c_1=1`.

So we have figured out that the secret binary string `bbc` is `10`. And we can confirm this.

Recall that `00` and `10` were related to each other by `00oplusbbc=10` since `f(00)=f(10)=00`.

Recall that `01` and `11` were related to each other by `01oplusbbc=11` since `f(01)=f(11)=11`.

Grover's Algorithm

Grover's algorithm solves the problem of finding one particular element out of a bunch of elements. Suppose we have a function `f:{0,1}^n mapsto {0,1}`. For exactly one of the inputs `bbx_0`, `f(bbx_0)` will return `1`. For all the other inputs, `f` will return `0`. The goal is to find out what that `bbx_0` is.

We'll use the same oracle as the one for Deutsch-Josza.

For this section, we'll use `bbx_0=01`.

The main idea behind Grover's algorithm is that it progressively increases the chances of the qubits measuring to the correct binary string.

It does this by using two tricks: phase inversion and inversion about the mean.

Phase Inversion

In order to boost the probability of the correct binary string `bbx_0`, we need to distinguish it from the others. We'll use this circuit to do so:

This is similar to the circuit in attempt 2 for Deutsch's algorithm, just with `n` qubits and the measurement operator on the top qubits. The result of the circuit is still the same though:

This essentially just changes the sign of the `|bbx_0:)` state. For example, if `|bbx:)` starts in an equal superposition of all states

then phase inversion will transform `|bbx:)` into

While changing the sign does distinguish the `|bbx_0:)` state from the other states, the probability of the `|bbx_0:)` state is still the same as the others (recall that the probability is calculated using the norm squared). We need a way to change the probabilities.

Inversion About the Mean/Average

This technique is a not a quantum-specific operation, so we'll first see how it works with just regular numbers.

Suppose we have the numbers `53`, `38`, `17`, `23`, and `79`. Their average is `a=42`. We can plot the numbers and their distance away from their average like this

To invert these numbers around the average is to move each number in the opposite direction from the average. For example, `53` is `11` units up from the average, so `53` inverted about the mean would be `11` units down from the mean, which is `31`.

This effectively "rotates" the numbers about the mean.

The general equation for inversion about the mean is

where `v` is each element and `a` is the average of all `v` elements.

If we want to apply this technique to our quantum states, we turn everything into matrices. The matrix that computes the average of `5` numbers is

We can confirm this with our sequence of numbers:

With the average represented as `AV`, the general equation for inversion about the mean in matrix form is

For our example,

And we can confirm that this matrix inverts the numbers about the mean:

Back to Grover's Algorithm

Combining phase inversion and inversion about the mean, we can create the circuit for Grover's algorithm:

Let's see how this works with our `bbx_0=01` example. We start with

After applying the Hadamard gates, we get

After applying phase inversion, we get

To prepare for inversion about the mean, we calculate the average, which is

and the inversion about the mean, which is

After applying inversion about the mean, we get

Shor's Algorithm

Shor's algorithm is used to find the factors of a number `N`. The algorithm starts by picking a random number, let's call it `a`. If we're lucky, `a` divides `N`, in which case the algorithm is done. If it doesn't divide `N`, but it shares a common factor with `N`, then the algorithm is also done.

So if `a` doesn't divide `N` and it also doesn't share any factors with `N` (i.e., `a` is co-prime to `N`), then we can start using some number theory magic to transform `a` into a better guess. It turns out that

meaning that if we multiply `a` by itself enough times, we'll end up with a number that can be divided by `N+1`.

With some rearranging, we get

What this is saying is that we can multiply two numbers `(a^(p/2)+1)` and `(a^(p/2)-1)` to get a multiple of `N`. Because of number theory, these two numbers should share a common factor with `N`. So the factors of `N` are

But how do we find `p`? Unfortunately, there aren't any tricks for this; we just have to keep trying different values of `p`. We can, however, speed things up by trying a superposition of values for `p`.

First, we can reframe our situation as

where the problem we're trying to solve is finding the smallest non-zero value of `p` such that

The quantum circuit that implements `f_(a,N)` (a.k.a. the oracle) is

where `n=log_2N` and `m=2n`.

And the whole circuit for Shor's algorithm is

We start with `|bb0_m,bb0_n:)` and apply the Hadamards to get

Then the output of `U_(f_a,N)` is

Now, if we measure the bottom qubits, we'll get a random value of

for some `z`. This means after measuring the bottom qubits, we will have a superposition of states where the bottom qubits are in the state `|a^ztext( Mod )N:)`. In fact, there are `floor(2^m/p)` of these states.

Continuing with the circuit tracing, we feed this into the `QFT` operation. The details of how the `QFT` works is beyond the scope of the class (and the scope of my knowledge since I never learned about Fourier transforms), but basically, it is able to take in a superposition of numbers separated by `p` and output the state `|1/p:)`, which we can easily invert to get `p`.

Recall that once we find `p`, we can find the factors of `N` using

The steps of Shor's algorithm are:

1. Choose a random `a` such that `1 lt a lt N` and calculate `GCD(a,N)`
   • if `GCD(a,N)ne1` then the GCD is a factor of `N`
2. Use the quantum circuit to find the period `p`
   • if `p` is odd or if `a^p=-1text( Mod )N`, then choose another `a`
3. Calculate `GCD(a^(p/2)+1,N)` and `GCD(a^(p/2)-1,N)`