Quantum Computing

---

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

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

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 lends itself to 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:

Just like with regular vectors, adding complex vectors is the same.

And so is scalar multiplication.

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

Matrix addition, scalar multiplication, and the transpose is the same as regular matrices.

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

Dimension

The dimension of a complex vector space is the number of elements in a basis of the space.

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 two matrices `A,B in RR^(nxxn)`, the inner product is defined as

where the trace of a matrix is the sum of the diagonal elements of the matrix.

For complex vectors, the inner product is defined as

For two matrices `A,B in CC^(nxxn)`, 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`.

Trig

In `RR^3`, the inner product `(:V,V':)` is the same as

where `theta` is the angle between `V` and `V'`.

Eigenvalues and Eigenvectors

For a matrix `A in CC^(nxxn)`, if there is a number `c in CC` and a vector `V ne 0` such that

then `c` is an eigenvalue of `A` and `V` is an eigenvector of `A` associated with `c`.

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

`I` is the identity matrix, which means only `1`s along the diagonal and `0`s everywhere else.

Unitary matrices preserve inner products: `(:UV,UV':)=(:V,V':)`.

Unitary matrices also preserve norms: `abs(UV)=abs(V)`

Tensor Product

For vectors,

For matrices,

Quantum Architecture

Moving away from linear algebra for a bit (heh), 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. (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.)

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]]` where `abs(c_0)^2+abs(c_1)^2=1` represents a qubit.

`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:)`.

Let's consider the complex vector `V=[[5+3i],[6i]]`. We can turn this complex vector into a qubit by normalizing it, that is, dividing each entry by the length of the vector (recall that the sum of the square of the entries has to equal `1` for it to be a qubit).

The length of the vector is

So the qubit is

After measuring the qubit, the probability that it is found in state `|0:)` is `34/70` (`abs(c_0)^2`) and the probability that it is found in state `|1:)` is `36/70` (`abs(c_1)^2`).

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:

Toffoli Gate

The Toffoli gate is another reversible gate. It has three inputs and three outputs.

The Toffoli gate is universal, which means that all the other logical gates can be built using copies of the Toffoli gate. The AND gate is obtained with `|z:)=``|0:)`; the output then becomes `|x ^^ y:)`. The NOT gate is obtained with `|x:)=``|1:)`, `|y:)=``|1:)`; the output then becomes `|1 oplus z:)=``|not z:)`.

The matrix representation of the Toffoli gate is

Fredkin Gate

The Fredkin gate is another reversible gate. It has three inputs and three outputs. For this gate, if `|x:)=``|0:)`, then all the outputs are the same as the input, i.e., `|y':)=``|y:)` and `|z':)=``|z:)`. If `|x:)=``|1:)`, then the outputs are reversed, i.e., `|y':)=``|z:)` and `|z':)=``|y:)`.

The `xx` represents a swap gate.

The matrix representation of the Fredkin gate is

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

Pauli Matrices

The matrices

are called the Pauli matrices. Apparently, they're used everywhere in quantum computing.

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.

Quantum Theory

Now we can really get into the quantum stuff. You know, the stuff like Schrödinger's cat and Heisenberg's uncertainty principle. Well, not these two concepts specifically, but the general ideas behind these concepts, like things not being predictable; things being in two states at the same time; and all that.

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!

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

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.