## Quantum Searching

Imagine a shuffled deck of 52 cards, and you are asked to find the ace of spades. The most natural thing to do is to take the top most card, see if it’s the ace of spades. If not, put it aside, take the top most and repeat the process until you find the ace of spades. If you are lucky, the ace of spades is the top most then we’re done. If you’re not so lucky, the ace of spades is at the bottom and it will take you 52 peeks before you find the card.

If we scatter the cards face down on the floor and randomly pick a card, then on the average, we will need $52/2$ peeks before we can find the ace of spades.

With quantum computing we can do even better!

For the sake of demonstration, let’s say we have 8 cards as shown in the figure below. We want to find the ace of spades.

Here are the steps:

1. Label each card from 0 to 7 in random order. The positions of the cards will represent the states of cards. The state $\left|6\right\rangle$ will therefore represent the ace of spades.

2. Let $\left|\phi\right\rangle$ be the superposition of states:

$\displaystyle \left|\phi\right\rangle = \frac{1}{2^{n/2}} \sum_{k=0}^{2^n-1} \left|x\right\rangle = \frac{1}{2^{n/2}} \Big( \left|0\right\rangle + \ldots + \left|7\right\rangle \Big) = \frac{1}{\sqrt{8}} \left[ \begin{array}{c} 1\\ 1\\ 1\\ 1\\ 1\\ 1\\ 1\\ 1 \end{array} \right]$

3. Let $f$ be a function such that

$f(x) = \begin{cases} 1 & x \text{ corresponds to ace of spades}\\ 0 & \text{ otherwise} \end{cases}$

Define the operator $\mathbf{V}$

$\mathbf{V} = \mathbf{I} - 2\left|a\right\rangle \left\langle a\right|$

where a is the unique value where

$f(a) = 1$

In our example, the value of a is 6. Therefore,

$\mathbf{V} = \begin{bmatrix} 1.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 \\ 0.00 & 1.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 \\ 0.00 & 0.00 & 1.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 \\ 0.00 & 0.00 & 0.00 & 1.00 & 0.00 & 0.00 & 0.00 & 0.00 \\ 0.00 & 0.00 & 0.00 & 0.00 & 1.00 & 0.00 & 0.00 & 0.00 \\ 0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 1.00 & 0.00 & 0.00 \\ 0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 & -1.00 & 0.00 \\ 0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 1.00 \\ \end{bmatrix}$

Observe that the matrix element $\mathbf{V}_{6,6} = -1$

4. Define the operator W:

$\mathbf{W} = 2\left|\phi\right\rangle \left\langle\phi\right| - \mathbf{I} = \begin{bmatrix} -0.75 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 \\ 0.25 & -0.75 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 \\ 0.25 & 0.25 & -0.75 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 \\ 0.25 & 0.25 & 0.25 & -0.75 & 0.25 & 0.25 & 0.25 & 0.25 \\ 0.25 & 0.25 & 0.25 & 0.25 & -0.75 & 0.25 & 0.25 & 0.25 \\ 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & -0.75 & 0.25 & 0.25 \\ 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & -0.75 & 0.25 \\ 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & -0.75 \\ \end{bmatrix}$

5. Compute the operator $\mathbf{WV}$:

$\mathbf{WV} = \begin{bmatrix} -0.75 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & -0.25 & 0.25 \\ 0.25 & -0.75 & 0.25 & 0.25 & 0.25 & 0.25 & -0.25 & 0.25 \\ 0.25 & 0.25 & -0.75 & 0.25 & 0.25 & 0.25 & -0.25 & 0.25 \\ 0.25 & 0.25 & 0.25 & -0.75 & 0.25 & 0.25 & -0.25 & 0.25 \\ 0.25 & 0.25 & 0.25 & 0.25 & -0.75 & 0.25 & -0.25 & 0.25 \\ 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & -0.75 & -0.25 & 0.25 \\ 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & 0.75 & 0.25 \\ 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & -0.25 & -0.75 \\ \end{bmatrix}$

6. Multiply $\mathbf{WV}$ to $\left|\phi\right\rangle$ a number of times, about $\pi/4 \cdot 2^{n/2} = \pi/4 \cdot \sqrt{8} = 2.2 \approx 2$:

$\mathbf{WV}\left|\phi\right\rangle = \begin{bmatrix} 0.18 \\ 0.18 \\ 0.18 \\ 0.18 \\ 0.18 \\ 0.18 \\ 0.88 \\ 0.18 \\ \end{bmatrix}, \mathbf{(WV)^2}\left|\phi\right\rangle = \begin{bmatrix} -0.09 \\ -0.09 \\ -0.09 \\ -0.09 \\ -0.09 \\ -0.09 \\ 0.97 \\ -0.09 \\ \end{bmatrix}$

As you can see, the probability of getting the state $\left|6\right\rangle$ becomes very close to 1.

Making a measurement of the input register at this point will give us the state $\left|6\right\rangle$ with a probability very close to 1.

We have just demonstrated the quantum search algorithm!

## Why it works

Let $f$ be a function such that

$f(x) = \begin{cases} 1 & x \text{ the item we are looking for}\\ 0 & \text{ otherwise} \end{cases}$

Define the operator $\mathbf{U}_f$ whose action on an n qubit register and 1 qubit output register is

$\mathbf{U}_f(\left|x\right\rangle \otimes \left|y\right\rangle) = \left|x\right\rangle\otimes\left|y\oplus f(x)\right\rangle$

Prepare the n qubit input register and 1 qubit output register in the following state:

$\underbrace{\left|0\right\rangle\ldots \left|0\right\rangle}_{\text{n times}} \otimes \left|1\right\rangle$

Applying the Hadamard operator on the input and output qubits gives us a superposition of $N=2^n$ states:

$\begin{array}{rl} \displaystyle \mathbf{H}^{\otimes n}\otimes\mathbf{H}(\left|0\ldots 0\right\rangle\otimes \left|1\right\rangle )&= \mathbf{H}^{\otimes n}\left|0\ldots 0\right\rangle\otimes \mathbf{H}\left|1\right\rangle\\ &= \displaystyle \frac{1}{2^{n/2}}\sum_{x=0}^{2^n-1} \left|x\right\rangle \otimes \frac{1}{\sqrt{2}} \left(\left|0\right\rangle - \left|1\right\rangle\right) \end{array}$

Next apply the operator $\mathbf{U}_f$ to get

$\begin{array}{rl} \displaystyle \mathbf{U}_f \left[\frac{1}{2^{n/2}}\sum_{x=0}^{2^n-1} \left|x\right\rangle \otimes \frac{1}{\sqrt{2}} \left(\left|0\right\rangle - \left|1\right\rangle\right)\right] &= \displaystyle \frac{1}{\sqrt{2}} \frac{1}{2^{n/2}}\left[\sum_{x=0}^{2^n-1} \mathbf{U}_f \left|x\right\rangle \otimes \left|0\right\rangle - \sum_{x=0}^{2^n-1} \mathbf{U}_f \left|x\right\rangle \otimes \left|1\right\rangle\right] \\ &= \displaystyle \frac{1}{\sqrt{2}} \frac{1}{2^{n/2}}\left[\underbrace{\sum_{x=0}^{2^n-1} \left|x\right\rangle \otimes \left|0\oplus f(x) \right\rangle }_{\text{first underbrace}} - \underbrace{\sum_{x=0}^{2^n-1} \left|x\right\rangle \otimes \left|1\oplus f(x) \right\rangle}_{\text{second underbrace}}\right] \end{array}$

When $f(x) = 1$ for x=a, the first underbrace will expand to

$\displaystyle \sum_{x=0}^{2^n-1} \left|x\right\rangle \otimes \left|0\oplus f(x) \right\rangle = \left|0\right\rangle\otimes\left|0\right\rangle + \ldots + \underbrace{\left|a\right\rangle\otimes\left|1\right\rangle} + \ldots + \left|2^n-1\right\rangle \otimes \left|0\right\rangle$

The second underbrace will expand to

$\displaystyle \sum_{x=0}^{2^n-1} \left|x\right\rangle \otimes \left|1\oplus f(x) \right\rangle = \left|0\right\rangle\otimes\left|1\right\rangle + \ldots + \underbrace{\left|a\right\rangle\otimes\left|0\right\rangle} + \ldots + \left|2^n-1\right\rangle \otimes \left|1\right\rangle\\$

The underbraces in the above summations can be swapped so that we get

$\displaystyle \frac{1}{\sqrt{2}} \frac{1}{2^{n/2}} \left[ \sum_{x=0}^{2^n-1} (-1)^{f(x)} \left|x\right\rangle \otimes \left|0\right\rangle - \sum_{x=0}^{2^n-1} (-1)^{f(x)} \left|x\right\rangle \otimes \left|1\right\rangle\right]$

$\begin{array}{rl} &= \displaystyle \frac{1}{2^{n/2}} \sum_{x=0}^{2^n-1} (-1)^{f(x)} \left|x\right\rangle \otimes \frac{1}{\sqrt{2}} \left( \left|0\right\rangle - \left|1\right\rangle\right)\\ &= \displaystyle \frac{1}{2^{n/2}} \sum_{x=0}^{2^n-1} (-1)^{f(x)} \left|x\right\rangle \otimes \mathbf{H}\left|1\right\rangle \end{array}$

This means that the action of $\mathbf{U}_f$ leaves the output qubit unentangled with the input qubit. We can just ignore this moving forward and focus our attention to the input qubits.

We view the current state of the input qubit as the result of some operator $\mathbf{V}$ defined by

$\mathbf{V} \left|\phi\right\rangle = \displaystyle \frac{1}{2^{n/2}} \sum_{x=0}^{2^n-1} (-1)^{f(x)} \left|x\right\rangle$

where

$\left|\phi\right\rangle = \displaystyle \frac{1}{2^{n/2}} \sum_{x=0}^{2^n-1} \left|x\right\rangle$

We can derive the expression of $\mathbf{V}$ by expanding $\mathbf{V} \left|\phi\right\rangle$, noting that at x=a, $f(x) = 1$:

$\begin{array}{rl} \mathbf{V} \left|\phi\right\rangle &= \displaystyle \frac{1}{2^{n/2}} \sum_{x=0}^{2^n-1} (-1)^{f(x)} \left|x\right\rangle\\ &= \displaystyle \frac{1}{2^{n/2}} \left[\left|0\right\rangle + \ldots - \left|a\right\rangle +\ldots + \left|2^n-1\right\rangle\right]\\ &= \displaystyle \frac{1}{2^{n/2}} \left[\left|0\right\rangle + \ldots + \left|a\right\rangle +\ldots + \left|2^n-1\right\rangle - 2\left|a\right\rangle\right]\\ &= \displaystyle \frac{1}{2^{n/2}} \sum_{x=0}^{2^n-1} \left|x\right\rangle - \frac{2}{2^{n/2}} \left|a\right\rangle\\ &= \left|\phi\right\rangle - 2\left\langle a|\phi\right\rangle \left|a\right\rangle\\ &= \Big[\mathbf{I} - 2\left|a\right\rangle \left\langle a\right|\Big] \left|\phi\right\rangle\\ \end{array}$

which means

$\mathbf{V} = \mathbf{I} - 2\left|a\right\rangle \left\langle a\right|$

The two vectors $\left|\phi\right\rangle$ and $\left|a\right\rangle$ determine a plane P. Let $\left|a_{\perp}\right\rangle$ be the vector in the plane perpendicular to $\left|a\right\rangle$. We can write $\left|\phi\right\rangle$ as

$\left|\phi\right\rangle = \phi_1 \left|a_\perp\right\rangle + \phi_2\left|a\right\rangle$

Applying $\mathbf{V}$ to $\left|\phi\right\rangle$ gives us:

$\begin{array}{rl} \mathbf{V}\left|\phi\right\rangle &= \left(\mathbf{I} - 2\left|a\right\rangle \left\langle a\right| \right) \left( \phi_1 \left|a_\perp\right\rangle + \phi_2\left|a\right\rangle \right)\\ &= \phi_1 \left|a_\perp\right\rangle + \phi_2\left|a\right\rangle - 2\phi_2\left|a\right\rangle\\ &= \phi_1 \left|a_\perp\right\rangle - \phi_2\left|a\right\rangle \end{array}$

The effect of the operator $\mathbf{V}$ is therefore to reflect the vector $\left|\phi\right\rangle$ with respect to the vector $\left|a_\perp\right\rangle$.

Now, we want to reflect this vector $\mathbf{V}\left|\phi\right\rangle$ with respect to $\left|\phi\right\rangle$. To accomplish this, we define the operator $\mathbf{W}$ by

$\mathbf{W} = 2\left|\phi\right\rangle \left\langle\phi\right| - \mathbf{I}$

Apply this operator to $\mathbf{V}\left|\phi\right\rangle$:

$\begin{array}{rl} \mathbf{WV}\left|\phi\right\rangle &= \Big[ 2\left|\phi\right\rangle \left\langle\phi\right| - \mathbf{I} \Big]\mathbf{V}\left|\phi\right\rangle\\ &= 2\left|\phi\right\rangle \left\langle\phi\right|\mathbf{V}\left|\phi\right\rangle -\mathbf{V}\left|\phi\right\rangle \end{array}$

If we express $\mathbf{V}\left|\phi\right\rangle$ as a linear combination of $\left|\phi\right\rangle$ and a vector $\left|\phi_\perp\right\rangle$ in the plane P,

$\mathbf{V}\left|\phi\right\rangle = \alpha \left|\phi\right\rangle + \beta \left|\phi_\perp\right\rangle$

We have,

$\begin{array}{rl} \mathbf{WV}\left|\phi\right\rangle &= \Big[ 2\left|\phi\right\rangle \left\langle\phi\right| - \mathbf{I} \Big]\mathbf{V}\left|\phi\right\rangle\\ &= 2\left|\phi\right\rangle \left\langle\phi\right|\mathbf{V}\left|\phi\right\rangle -\mathbf{V}\left|\phi\right\rangle\\ &= 2\alpha\left|\phi\right\rangle - \alpha \left|\phi\right\rangle - \beta \left|\phi_\perp\right\rangle\\ &= \alpha\left|\phi\right\rangle - \beta \left|\phi_\perp\right\rangle \end{array}$

which demonstrates that $\mathbf{W}$ reflects $\mathbf{V}\left|\phi\right\rangle$ with respect to $\left|\phi\right\rangle$.

Therefore, the effect of $\mathbf{WV}$ on $\left|\phi\right\rangle$ is to rotate it by an angle $\gamma$ counter-clockwise.

We can compute this $\gamma$ by getting the inner product of $\mathbf{WV}\left|\phi\right\rangle$ and $\left|\phi\right\rangle$. First, let’s find the expression of $\mathbf{WV}\left|\phi\right\rangle$:

$\begin{array}{rl} \mathbf{WV}\left|\phi\right\rangle &= \mathbf{W} \left( \mathbf{I} - 2\left|a\right\rangle \langle a |\right) \left|\phi\right\rangle\\ &= \mathbf{W} \left(\left|\phi\right\rangle - 2 \underbrace{\langle a| \phi \rangle} \left|a\right\rangle \right) \end{array}$

The quantity $\langle a| \phi \rangle$ is

$\langle a| \phi \rangle = \displaystyle \langle a| \left( \frac{1}{2^{n/2}} \sum_{k=0}^{2^n-1} \left|x\right\rangle \right) = \frac{1}{2^{n/2}} = \cos \theta$

where $\theta$ is the angle between $\left|a\right\rangle$ and $\left|\phi\right\rangle$.

The complementary angle, $\rho = 90-\theta$ is the angle between $\left|\phi\right\rangle$ and $\left|a_\perp\right\rangle$. Using a well-known trigonometric identity, we can compute for the angle of $\rho$:

$\cos \theta = \sin \rho = \displaystyle \frac{1}{2^{n/2}}$

Since $\displaystyle \frac{1}{2^{n/2}}$ is very small if n is large,

$\sin \rho = \displaystyle \frac{1}{2^{n/2}} \approx \rho$

Continuing,

$\begin{array}{rl} \mathbf{WV}\left|\phi\right\rangle &= \mathbf{W} \left( \mathbf{I} - 2\left|a\right\rangle \langle a |\right) \left|\phi\right\rangle\\ &= \mathbf{W} \left(\left|\phi\right\rangle - 2 \cos\rho \left|a\right\rangle \right)\\ &= (2\left|\phi\right\rangle \langle \phi| - \mathbf{I}) \left(\left|\phi\right\rangle - 2 \cos\rho \left|a\right\rangle \right)\\ &= 2\left|\phi\right\rangle - \left|\phi\right\rangle - 2\cos\rho \left|\phi\right\rangle \langle \phi |a\rangle + 2 \cos\rho \left|a\right\rangle\\ &= \left|\phi\right\rangle - 4\cos^2\rho \left|\phi\right\rangle + 2 \cos\rho \left|a\right\rangle\\ &= (1- 4\cos^2\rho) \left|\phi\right\rangle + 2 \cos\rho \left|a\right\rangle \end{array}$

The inner product of $\mathbf{WV}\left|\phi\right\rangle$ and $\left|\phi\right\rangle$ is given by

$\begin{array}{rl} \langle\phi|\mathbf{WV}\left|\phi\right\rangle &= \langle\phi|\left[ (1- 4\cos^2\rho) \left|\phi\right\rangle + 2 \cos\rho \left|a\right\rangle\right]\\ &= (1- 4\cos^2\rho) + 2\cos^2\rho\\ &= 1- 2\cos^2\rho\\ &= \cos 2\rho \end{array}$

Therefore, the angle between these two vectors is $2\rho = \displaystyle \frac{1}{2^{n/2}}$. How many times do we have to apply the operator $\mathbf{WV}$ to get to $\pi/2$?

$\begin{array}{rl} m\cdot 2\rho &= \displaystyle \frac{\pi}{2}\\ \displaystyle m \frac{2}{2^{n/2}}&= \displaystyle \frac{\pi}{2}\\ m &=\displaystyle \frac{\pi\cdot 2^{n/2}}{4} \end{array}$

Therefore, we need to apply the operator $\mathbf{WV}$ $O(\sqrt{N})$ times to find our value (where $N=2^n$).

## Parallel Computing in the Small: An Introduction to Quantum Computing

As I watched my one-month old baby sleeping, a thought ran through my mind. I wonder what technology would look like when she’s my age. There’s a lot of things going on simultaneously in technology today. I remember doing Artificial Intelligence/Machine Learning about 15 years ago. They used to be done in a university setting. They are now the new normal. Some technologies are quite recent like Big Data and Blockchain but they have become mainstream very quickly. I wonder what it will look like when my daughter grows up.

There is a technology I’m currently watching. It’s still in it’s infancy but this technology is really fascinating. It is a technology based on a remarkably counter-intuitive theory of the universe that governs the atoms and sub-atomic particles. It is called Quantum Computing. Given the high speed at which science fiction become realities, it’s possible that my baby girl will someday be programming on a quantum computer. But for now, we can only hope.

I have not seen a Quantum Computer and based on what I read so far, it’s still an engineering challenge. It might probably be a few more years before they are mass-produced but it is something to look forward to. But the good thing is, we can already talk about quantum algorithms! So let’s sharpen our pencils and get a few sheets of paper for we are going to talk about this new way of computing.

In classical computing, a bit has a value that is either one or zero. In quantum computing, a bit can now have a value that is a superposition of 1 and 0. We call this a QBit. The values 1 and 0 are now symbolized as $\left| 1\right\rangle$ and $\left| 0\right\rangle$ respectively. These are unit vectors in what is known as a Hilbert space. They are also known as kets, derived from the word bracket which we’ll talk more of later. An example of a vector space that you are familiar with is the color wheel. Each color is actually a combination of red, blue and green. For example, the color yellow is a combination of red and green. It’s also the same as with the qubit. A general QBit vector is of the form

$\displaystyle \left| \Psi \right\rangle = a\left| 0\right\rangle + b\left| 1\right\rangle$

such that $\mid a\mid^2 + \mid b\mid^2 = 1$. The numbers a and b are complex numbers and the symbol $\mid a\mid^2$ is defined as

$\displaystyle \mid a\mid^2 = a^*a$

where $a^*$ is the complex conjugate of a. A QBit vector represents the state of the QBit. We shall use the term vector and state interchangeably moving forward.

However, you won’t be able to see them in superposition state. If you want to know the state of a qubit, you will have to measure it. But when you measure it, it will collapse to one of either $\left| 0\right\rangle$ or $\left| 1\right\rangle$ but you will have a clue as to what that state will be. The coefficients a and b will give you the probability of the result of the measurement: it will be $\mid a\mid^2$ in state $\left| a\right\rangle$ and $\mid b\mid^2$ in state $\left| b\right\rangle$.

If the state of a QBit is a superposition of basis states $\left| 0\right\rangle$ and $\left| 1\right\rangle$, does this mean our computation is also random? Does it mean we get different answers every time ?

It turns out that we can get a definite answer! Let’s illustrate this by a simple quantum computation.

Suppose a I have a number between 0 and 1 million. What is my number? You can guess my number and I will only tell you if you got it correctly or not. I won’t tell you if my number is higher or lower than your guess. How many tries do you think you need in order to guess my number? I’m sure our tries will be many. In the worst case, you’ll need about 1 million tries.

For a quantum computer, you only need one try to guess it and that’s what we’re going to see. However, bear with me since we have to build up our arsenal of tools first before we can even talk about it. Let’s start with how a QBit looks like as a matrix.

The basis QBits $\left| 0\right\rangle$ and $\left| 1\right\rangle$ can be written as 1×2 matrices:

$\displaystyle \left| 0 \right\rangle = \begin{bmatrix} 1\\ 0 \end{bmatrix}$

$\displaystyle \left| 1 \right\rangle = \begin{bmatrix} 0\\ 1 \end{bmatrix}$

Using this representation, we can write a general QBit as:

$\displaystyle \mid\Psi\rangle = a\mid 0\rangle + b\mid 1\rangle = a \begin{bmatrix} 1\\ 0 \end{bmatrix} + b \begin{bmatrix} 0\\ 1 \end{bmatrix} = \begin{bmatrix} a\\ b \end{bmatrix}$

So now we know that every QBit is a linear combination of ket vectors $\left| 0\right\rangle$ and $\left| 1\right\rangle$. These ket vectors have a corresponding “bra” vectors $\langle 0 \mid$ and $\langle 1\mid$. In matrix representation, the bra basis vectors are defined as:

$\displaystyle \langle 0\mid = \begin{bmatrix} 1 & 0 \end{bmatrix}$

and

$\displaystyle \langle 1\mid = \begin{bmatrix} 0 & 1 \end{bmatrix}$

For a general QBit $\mid\Psi\rangle = a\mid 0\rangle + b\mid 1\rangle$, the corresponding bra vector is

$\displaystyle \langle \Psi \mid = a^*\langle 0\mid + b^*\langle 1\mid = \begin{bmatrix} a^* & b^* \end{bmatrix}$

There is an operation between bra and ket vectors of the basis states called inner product which is defined as:

$\begin{array}{rl} \displaystyle \langle 0\mid 0 \rangle &= 1\\ \displaystyle \langle 1\mid 1 \rangle &= 1\\ \displaystyle \langle 0\mid 1 \rangle &= \langle 1\mid 0\rangle = 0 \end{array}$

Using the above rules, we can define the inner product of any two QBits $\mid \Psi\rangle = a\mid 0\rangle + b\mid 1\rangle$ and $\mid\Phi\rangle = c\mid 0\rangle + d\mid 1\rangle$ as

$\begin{array}{rl} \displaystyle \langle \Psi\mid\Phi\rangle &= \big(a^*\langle 0\mid + b^*\langle 1\mid\big)\big(c\mid 0\rangle + d\mid 1\rangle\big)\\ &= \displaystyle a^*c \langle 0\mid 0\rangle + a^*\langle 0\mid 1\rangle + b^*c\langle 1\mid 0\rangle + b^*d\langle 1\mid 1\rangle\\ &= a^*c + b^*d \end{array}$

Using the above definition of an inner product, the norm of a vector is defined as

$\displaystyle \mid\left|\Psi\right\rangle\mid = \displaystyle \sqrt{\langle \Psi \mid \Psi \rangle} =\displaystyle \sqrt{a^*a + b^*b}$

Geometrically, the norm is the length of the ket $\mid \Psi\rangle$.

Quantum computations are done using quantum operators. They are also called quantum gates. Operators are linear mappings that take a state to another state. That is, an operator $\mathbf{A}$ acts on $a\left| 0 \right\rangle + b\left| 1\right\rangle$ to give another vector $c\left| 0 \right\rangle + d\left| 1\right\rangle$. We write this as

$\displaystyle \mathbf{A}(a\left| 0\right\rangle + b\left| 1\right\rangle) = c\left| 0\right\rangle + d\left| 1\right\rangle$

Since the basis vectors $\left| 0\right\rangle$ and $\left| 1\right\rangle$ are also vectors, operators can also operate on them. An example of a very important operator and it’s action on the basis vectors is the Hadamard operator:

$\begin{array}{rl} \displaystyle \mathbf{H} \left| 0 \right\rangle &= \displaystyle \frac{1}{\sqrt{2}}(\left| 0 \right\rangle + \left| 1\right\rangle)\\ \displaystyle \mathbf{H} \left| 1 \right\rangle &= \displaystyle \frac{1}{\sqrt{2}}(\left| 0 \right\rangle - \left| 1\right\rangle) \end{array}$

By knowing the action of an operator on the basis vectors, we can determine the matrix representation of an operator. For the Hadamard operator, the matrix representations are:

$\displaystyle \mathbf{H} \left| 0 \right\rangle = \displaystyle \frac{1}{\sqrt{2}}(\left| 0 \right\rangle + \left| 1\right\rangle) = \frac{1}{\sqrt{2}} \begin{bmatrix} 1\\ 1 \end{bmatrix}$

and

$\displaystyle \mathbf{H} \left| 1 \right\rangle = \displaystyle \frac{1}{\sqrt{2}}(\left| 0 \right\rangle - \left| 1\right\rangle) = \frac{1}{\sqrt{2}} \begin{bmatrix} 1\\ -1 \end{bmatrix}$

Therefore the matrix representation of the Hadamard operator is

$\displaystyle \mathbf{H}= \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$

The identity operator is defined as the operator that maps a vector into itself and is symbolized as $\mathbf{I}$:

$\displaystyle \mathbf{I}\left|\Psi\right\rangle = \left|\Psi\right\rangle$

The NOT operator is defined as

$\begin{array}{rl} \mathbf{X}\left|0\right\rangle &= \left|1\right\rangle\\ \mathbf{X}\left|1\right\rangle &= \left|0\right\rangle \end{array}$

What it does is transform the $\left|0\right\rangle$ to $\left|1\right\rangle$ and vice versa, just like the classical bits.

Operators are linear. We can use linearity to derive the resulting vector when an operator acts on a general QBit:

$\displaystyle \mathbf{A}(a\left| 0\right\rangle + b\left| 1\right\rangle) = a\mathbf{A} \left| 0\right\rangle + b\mathbf{A} \left| 1\right\rangle)$

If $\mathbf{A}$ is the Hadamard operator, that is, $\mathbf{A} = \mathbf{H}$, then the above operation becomes:

$\displaystyle \mathbf{H}(a\left| 0\right\rangle + b\left| 1\right\rangle) = a\mathbf{H} \left| 0\right\rangle + b\mathbf{H} \left| 1\right\rangle)$

Since we know that:

$\begin{array}{rl} \displaystyle \mathbf{H} \left| 0 \right\rangle &= \displaystyle \frac{1}{\sqrt{2}}(\left| 0 \right\rangle + \left| 1\right\rangle)\\ \displaystyle \mathbf{H} \left| 1 \right\rangle &= \displaystyle \frac{1}{\sqrt{2}}(\left| 0 \right\rangle - \left| 1\right\rangle) \end{array}$

We can then write this as:

$\begin{array}{rl} \displaystyle \mathbf{H}(a\left| 0\right\rangle + b\left| 1\right\rangle) &= \displaystyle a\mathbf{H} \left| 0\right\rangle + b\mathbf{H} \left| 1\right\rangle)\\ &= \displaystyle a\frac{1}{\sqrt{2}}\big(\left| 0\right\rangle + \left| 1\right\rangle\big) + b\frac{1}{\sqrt{2}}\big(\left| 0\right\rangle - \left| 1\right\rangle\big)\\ &= \displaystyle \frac{a+b}{\sqrt{2}} \left| 0\right\rangle + \frac{a-b}{\sqrt{2}} \left| 1\right\rangle \end{array}$

Let see what the operators look like when they operate on bra vectors. Let’s start with the Hadamard operator acting on a general QBit above.

$\begin{array}{rl} \displaystyle \mathbf{H} \mid 0 \rangle &= \displaystyle \frac{1}{\sqrt{2}}(\mid 0 \rangle + \mid 1\rangle) \rightarrow \langle 0\mid \mathbf{H^\dagger} = \displaystyle \frac{1}{\sqrt{2}}(\langle 0 \mid + \langle 1\mid)\\ \displaystyle \mathbf{H} \mid 1 \rangle &= \displaystyle \frac{1}{\sqrt{2}}(\mid 0 \rangle - \mid 1\rangle) \rightarrow \langle 1\mid \mathbf{H^\dagger} = \displaystyle \frac{1}{\sqrt{2}}(\langle 0 \mid - \langle 1\mid) \end{array}$

where we symbolize $\mathbf{H^\dagger}$ as the operator corresponding to the Hadamard operator acting on bras.

The matrix representation of the Hadamard operator acting on bras is therefore:

$\mathbf{H^\dagger} = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1\\ 1 & -1 \end{bmatrix} = \mathbf{H}$

In general, the matrix representation of $\mathbf{H^\dagger}$ is the conjugate transpose of the matrix of $\mathbf{H}$. In simple terms, this means take the transpose of $\mathbf{H}$ and apply the complex conjugates to each element. It’s amazing that the Hadamard operator is equal to its conjugate transpose. The types of operators that behave that way are called Hermitian operators.

Let $\mathbf{A}$ be an operator and $\left| \Psi\right\rangle$ a vector and let $\Phi = \mathbf{A}\left|\Psi\right\rangle$, then the norm of $\Phi$ is

$\displaystyle \langle\Phi\mid\Phi\rangle = \langle \Psi\mid \mathbf{A^\dagger}\mathbf{A}\mid \Psi\rangle = \langle\Psi\mid\Psi\rangle$

This means that

$\displaystyle \mathbf{A^\dagger}\mathbf{A} = \mathbf{I}$

The kind of operator that satisfies the above relationship is called Unitary.

Now that we have gained knowledge of some of the tools, we can now describe how a quantum computation is set up. We need QBits for the input and QBits for the output. The simplest setup is a one QBit input and one QBit output. Let $\left| x\right\rangle$ and $\left| y\right\rangle$ be the input and output QBits,respectively. The general state of this quantum system is a superposition of the following states:

$\left| 0 \right\rangle \otimes \left| 0 \right\rangle, \left| 0 \right\rangle \otimes \left| 1 \right\rangle, \left| 1 \right\rangle \otimes \left| 0 \right\rangle, \left| 1 \right\rangle \otimes \left| 1 \right\rangle$

which could also be written as

$\left|00\right\rangle, \left|01\right\rangle, \left|10\right\rangle, \left|11\right\rangle,$

or, if we take them as binary representation of numbers, we can write them concisely as

$\left|0\right\rangle, \left|1\right\rangle,\left|2\right\rangle,\left|3\right\rangle,$

Using the above basis vectors, we can write a general 2-QBit system as:

$\displaystyle \left|\Psi\right\rangle = c_1\left|0\right\rangle + c_1\left|1\right\rangle + c_1\left|2\right\rangle + c_1\left|3\right\rangle = \sum_{i=0}^{2^n-1} c_i\left|i\right\rangle$

where the numbers $c_i$ are complex and n=2. The summation is up to $2^n-1$ since the maximum number n QBits can represent is $2^n-1$. The summation on the right also gives us the general form of a QBit for an n-QBit system.

As we saw earlier, the quantum operators (or gates) are the ones used to compute from a given QBit inputs. Let $\mathbf{U}_f$ represent a unitary operator implementing the function f. The function f is a function that takes the numbers from the domain $\{0,1\}$ to $\{0,1\}$, that is,

$\displaystyle f: \{0,1\}\rightarrow \{0,1\}$

For a two-QBit system, the form of quantum computation is

$\displaystyle \mathbf{U}_f\left|x\right\rangle \left|y\right\rangle = \left|x\right\rangle \left|x\oplus f(x)\right\rangle$

where the symbol $\oplus$ represent bitwise OR operation. The table below will give you the results of the bitwise OR operation for every combination of values in $\{0,1\}$:

$\begin{array}{cc} 0 \oplus 0 &= 0\\ 0 \oplus 1 &= 1\\ 1 \oplus 0 &= 1\\ 1 \oplus 1 &= 0 \end{array}$

A simple but important example of a unitary operator acting on two QBits is the $\mathbf{C_{\text{NOT}}}$ gate, defined as:

$\displaystyle \mathbf{C_{\text{NOT}}}\left|x\right\rangle\left|y\right\rangle = \left|x\right\rangle\left|y \oplus x\right\rangle$

Here is the complete action of the $\mathbf{C_{\text{NOT}}}$:

$\begin{tabular}{c|c|c} \text{Input} & \text{Output} & \text{Result}\\ 0 & 0 & 0\\ 0 & 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 0 \end{tabular}$

If you study the table above, you’ll notice that if the input QBit is in the state $\left|0\right\rangle$, the output QBit stays the same. However, if the input QBit is in $\left|1\right\rangle$, the output QBit is flipped. The input QBit in this case controls the flipping of the second QBit. The input QBit is said to be the control bit. That’s why it’s called a $\mathbf{C_{\text{NOT}}}$ which stands for Controlled-NOT gate.

Let’s now go back to our original problem. There is a positive number $a$ that is less than $2^n$ . We want to find this number using quantum computation. We are given a black box operator $\mathbf{U}_f$ whose action on a bra is

$\displaystyle \mathbf{U}_f \left|x\right\rangle\left|y\right\rangle = \left|x\right\rangle\left| y \oplus f(x)\right\rangle$

where

$\displaystyle f(x) = x_0 a_0 \oplus x_1 a_1 \oplus \cdots x_{n-1}a_{n-1} = x \cdot a$

where $a$ is the unknown number we are going to guess and $x_ia_i$ are the i-th bits of x and a.

So how many times do we have to apply $\mathbf{U}_f$ in order to guess the number $a$?

To solve this, we need $n$ input QBits and 1 output QBit. We will initialize our QBits to $\left|0\right\rangle$. So the initial configuration is

$\displaystyle \underbrace{\left|000...0\right\rangle}_{\text{n number of zeroes}}\otimes\left|1\right\rangle$

Notice how we separate the input and output qubits.

Next we apply the Hadamard operator to each QBit:

$\displaystyle \mathbf{H}^{\otimes n}\otimes \mathbf{H} \left|000...0\right\rangle\left|1\right\rangle = \mathbf{H}^{\otimes n} \left|000...0\right\rangle\otimes \mathbf{H}\left|1\right\rangle$

We have seen the Hadamard operator earlier. For the sake of convenience we’ll repeat it here:

$\begin{array}{rl} \displaystyle \mathbf{H} \left| 0 \right\rangle &= \displaystyle \frac{1}{\sqrt{2}}(\left| 0 \right\rangle + \left| 1 \right\rangle)\\ \displaystyle \mathbf{H} \left| 1 \right\rangle &= \displaystyle \frac{1}{\sqrt{2}}(\left| 0 \right\rangle - \left| 1\right\rangle) \end{array}$

We can generalize this by letting x be either 0 or 1:

$\begin{array}{rl} \displaystyle \mathbf{H}\left| x\right\rangle &= \frac{1}{\sqrt{2}}\big(\left|0\right\rangle + (-1)^x \left|1\right\rangle \end{array}$

We can use this to compute the action on two QBits and generalize:

$\begin{array}{rl} \displaystyle \mathbf{H}^{\otimes 2}\left| x\right\rangle &= \mathbf{H}^{\otimes 2}\left| x_0x_1\right\rangle = \mathbf{H}\left| x_0\right\rangle \otimes \mathbf{H}\left| x_1\right\rangle\\ &= \displaystyle \frac{1}{\sqrt{2}}\big(\left|0\right\rangle + (-1)^{x_0} \left|1\right\rangle \otimes \frac{1}{\sqrt{2}}\big(\left|0\right\rangle + (-1)^{x_1} \left|1\right\rangle\\ &= \displaystyle \big(\frac{1}{\sqrt{2}}\big)^2 \big( \left|00\right\rangle + (-1)^{x_0} \left|01\right\rangle + (-1)^{x_1}\left|10\right\rangle + (-1)^{x_1 + x_0}\left|11\right\rangle\\ &= \displaystyle \big(\frac{1}{\sqrt{2}}\big)^2 \big( (-1)^{0\cdot x_1 + 0\cdot x_0} \left|00\right\rangle + (-1)^{0\cdot x_1 + 1\cdot x_0} \left|01\right\rangle + (-1)^{1\cdot x_1 + 0\cdot x_0}\left|10\right\rangle + (-1)^{1\cdot x_1 + 1\cdot x_0}\left|11\right\rangle\\ &= \displaystyle \big(\frac{1}{\sqrt{2}}\big)^2 \big( (-1)^{0\cdot x_1 + 0\cdot x_0} \left|0\right\rangle + (-1)^{0\cdot x_1 + 1\cdot x_0} \left|1\right\rangle + (-1)^{1\cdot x_1 + 0\cdot x_0}\left|2\right\rangle + (-1)^{1\cdot x_1 + 1\cdot x_0}\left|3\right\rangle\\ &= \displaystyle \big(\frac{1}{\sqrt{2}}\big)^2 \sum_{y=0}^{2^2-1} (-1)^{x\cdot y}\left|y\right\rangle \end{array}$

In general,

$\displaystyle \mathbf{H}^{\otimes n}\left| x\right\rangle = \frac{1}{2^{n/2}}\sum_{y=0}^{2^n-1} (-1)^{x\cdot y}\left|y\right\rangle$

Using the above formula, the action of $\mathbf{H}^{\otimes n}$ on $\left|0\right\rangle$ is

$\displaystyle \mathbf{H}^{\otimes n} \left|0\right\rangle = \frac{1}{2^{n/2}}\sum_{y=0}^{2^n-1} \left|y\right\rangle$

The next step is to apply our operator $\mathbf{U}_{f}$ which was defined above:

$\begin{array}{rl} \displaystyle \mathbf{U}_f\mathbf{H}^{\otimes n}\left| 0\right\rangle \otimes \frac{1}{\sqrt{2}} \big( \left|0\right\rangle - \left|1\right\rangle\big) &= \displaystyle \frac{1}{2^{n/2}}\sum_{y=0}^{2^n-1} \mathbf{U}_f\left|y\right\rangle \otimes \frac{1}{\sqrt{2}} \big( \left|0\right\rangle - \left|1\right\rangle\big)\\ &= \displaystyle \frac{1}{2^{n/2}}\sum_{y=0}^{2^n-1} \frac{1}{\sqrt{2}} \big( \mathbf{U}_f\left|y\right\rangle \otimes \left|0\right\rangle - \mathbf{U}_f\left|y\right\rangle \otimes \left|1\right\rangle\big)\\ &= \displaystyle \frac{1}{2^{n/2}}\sum_{y=0}^{2^n-1} \frac{1}{\sqrt{2}} \big( \left|y\right\rangle \otimes \left|0\oplus f(y)\right\rangle - \left|y\right\rangle \otimes \left|1\oplus f(y)\right\rangle\big)\\ \end{array}$

Let’s break this down a bit. Since the value of $f(y)$ is either 0 or 1, we have 2 cases:

When $f(y) = 0$,

$\displaystyle \left|y\right\rangle \otimes \left|0\oplus f(y)\right\rangle = \left|y\right\rangle \otimes \left|0\right\rangle$
$\displaystyle \left|y\right\rangle \otimes \left|1\oplus f(y)\right\rangle = \left|y\right\rangle \otimes \left|1\right\rangle$

which means

$\displaystyle \frac{1}{2^{n/2}}\sum_{y=0}^{2^n-1} \frac{1}{\sqrt{2}} \big( \left|y\right\rangle \otimes \left|0\oplus f(y)\right\rangle - \left|y\right\rangle \otimes \left|1\oplus f(y)\right\rangle\big) = \frac{1}{2^{n/2}}\sum_{y=0}^{2^n-1} \left|y\right\rangle \otimes \frac{1}{\sqrt{2}} \big( \left|0\right\rangle - \left|1\right\rangle\big)$

When $f(y) = 1$,

$\displaystyle \left|y\right\rangle \otimes \left|0\oplus f(y)\right\rangle = \left|y\right\rangle \otimes \left|1\right\rangle$
$\displaystyle \left|y\right\rangle \otimes \left|1\oplus f(y)\right\rangle = \left|y\right\rangle \otimes \left|0\right\rangle$

which means

$\displaystyle \frac{1}{2^{n/2}}\sum_{y=0}^{2^n-1} \frac{1}{\sqrt{2}} \big( \left|y\right\rangle \otimes \left|0\oplus f(y)\right\rangle - \left|y\right\rangle \otimes \left|1\oplus f(y)\right\rangle\big) = \frac{1}{2^{n/2}}\sum_{y=0}^{2^n-1} (-1) \left|y\right\rangle \otimes \frac{1}{\sqrt{2}} \big( \left|0\right\rangle - \left|1\right\rangle\big)$

Combining these 2 we have

$\begin{array}{rl} \displaystyle \mathbf{U}_f\mathbf{H}^{\otimes n}\left| 0\right\rangle \otimes \frac{1}{\sqrt{2}} \big( \left|0\right\rangle - \left|1\right\rangle\big) &= \displaystyle \frac{1}{2^{n/2}}\sum_{y=0}^{2^n-1} \frac{1}{\sqrt{2}} \big( \left|y\right\rangle \otimes \left|0\oplus f(y)\right\rangle - \left|y\right\rangle \otimes \left|1\oplus f(y)\right\rangle\big)\\ &= \displaystyle \frac{1}{2^{n/2}}\sum_{y=0}^{2^n-1} (-1)^{f(y)} \left|y\right\rangle \otimes \frac{1}{\sqrt{2}} \big( \left|0\right\rangle - \left|1\right\rangle\big) \end{array}$

Finally, getting the Hadamard action on this gives:

$\begin{array}{rl} \displaystyle \mathbf{H}^{\otimes n}\otimes\mathbf{H}\Big[\mathbf{U}_f\mathbf{H}^{\otimes n}\left| 0\right\rangle \otimes \frac{1}{\sqrt{2}} \big( \left|0\right\rangle - \left|1\right\rangle\big)\Big] &=\mathbf{H}^{\otimes n} \mathbf{U}_f\mathbf{H}^{\otimes n}\left| 0\right\rangle \otimes \mathbf{H}\Big[\frac{1}{\sqrt{2}} \big( \left|0\right\rangle - \left|1\right\rangle\big)\Big]\\ &= \underbrace{\mathbf{H}^{\otimes n} \Big[\displaystyle \frac{1}{2^{n/2}}\sum_{y=0}^{2^n-1} (-1)^{f(y)} \left|y\right\rangle \Big]}_{A} \otimes \underbrace{\mathbf{H}\Big[\frac{1}{\sqrt{2}} \big( \left|0\right\rangle - \left|1\right\rangle\big)\Big]}_{B} \end{array}$

Expanding underbrace B gives us:

$\begin{array}{rl} \displaystyle \mathbf{H}\Big[\frac{1}{\sqrt{2}} \big( \left|0\right\rangle - \left|1\right\rangle\big)\Big] &= \displaystyle \frac{1}{\sqrt{2}}\big(\mathbf{H}\left|0\right\rangle - \mathbf{H}\left|1\right\rangle\big)\\ &= \displaystyle \frac{1}{\sqrt{2}}\Big[\frac{1}{\sqrt{2}} \big( \left|0\right\rangle + \left|1\right\rangle \big) - \frac{1}{\sqrt{2}}\big( \left|0\right\rangle - \left|1\right\rangle\big) \Big]\\ &= \displaystyle \frac{1}{2}\Big[ 2\left|1\right\rangle \Big]\\ &= \left|1\right\rangle \end{array}$

Expanding underbrace A above:

$\begin{array}{rl} \mathbf{H}^{\otimes n} \Big[\displaystyle \frac{1}{2^{n/2}}\sum_{y=0}^{2^n-1} (-1)^{f(y)} \left|y\right\rangle \Big] &= \displaystyle \frac{1}{2^{n/2}}\sum_{y=0}^{2^n-1} (-1)^{f(y)}\mathbf{H}^{\otimes n} \left|y\right\rangle \end{array}$

We have found earlier that

$\displaystyle \mathbf{H}^{\otimes n}\left| y\right\rangle = \frac{1}{2^{n/2}}\sum_{x=0}^{2^n-1} (-1)^{x\cdot y}\left|x\right\rangle$

Substituting this to the above and noting that

$\displaystyle f(y) = y\cdot a = \sum_{i=0}^{n-1} y_ia_i \mod 2$,

we get:

$\begin{array}{rl} \mathbf{H}^{\otimes n} \Big[\displaystyle \frac{1}{2^{n/2}}\sum_{y=0}^{2^n-1} (-1)^{f(y)} \left|y\right\rangle \Big] &= \displaystyle \frac{1}{2^{n/2}}\sum_{y=0}^{2^n-1} (-1)^{f(y)}\mathbf{H}^{\otimes n} \left|y\right\rangle \\ &= \displaystyle \frac{1}{2^{n}}\sum_{y=0}^{2^n-1} \sum_{x=0}^{2^n-1} (-1)^{f(y)}(-1)^{y\cdot x}\left|x\right\rangle\\ &= \displaystyle \frac{1}{2^{n}}\sum_{y=0}^{2^n-1} \sum_{x=0}^{2^n-1} (-1)^{y\cdot a}(-1)^{y\cdot x}\left|x\right\rangle\\ &= \displaystyle \frac{1}{2^{n}}\sum_{x=0}^{2^n-1} \underbrace{\sum_{y=0}^{2^n-1} (-1)^{(a+x)\cdot y}}\left|x\right\rangle\\ \end{array}$

where we have interchanged the order of the summation. To simplify the term with the underbrace, notice that

$\begin{array}{rl} \displaystyle \Big[1+ (-1)^{z_0}\Big]\Big[1+(-1)^{z_1}\Big] &= 1 + (-1)^{z_0} + (-1)^{z_1} + (-1)^{z_0+z_1}\\ &= \displaystyle (-1)^{0\cdot z_0 + 0\cdot z_1} + (-1)^{1\cdot z_0 + 0\cdot z_1} + (-1)^{0\cdot z_0 + 1\cdot z_1} + (-1)^{1\cdot z_0+ 1\cdot z_1}\\ &= \displaystyle(-1)^{0\cdot z} + (-1)^{1\cdot z} + (-1)^{2\cdot z} + (-1)^{3\cdot z}\\ &= \displaystyle \sum_{y=0}^{2^2-1} (-1)^{y\cdot z} \end{array}$

We can therefore write the factor in underbrace as

$\begin{array}{rl} \mathbf{H}^{\otimes n} \Big[\displaystyle \frac{1}{2^{n/2}}\sum_{y=0}^{2^n-1} (-1)^{f(y)} \left|y\right\rangle \Big] &= \displaystyle \frac{1}{2^{n}}\sum_{x=0}^{2^n-1} \underbrace{\sum_{y=0}^{2^n-1} (-1)^{(a+x)\cdot y}}\left|x\right\rangle\\ &= \displaystyle \frac{1}{2^{n}}\sum_{x=0}^{2^n-1} \prod_{i=0}^{n-1} \Big[ \underbrace{1 +(-1)^{(a_i+x_i)}}\Big] \left|x\right\rangle\\ \end{array}$

Notice that

$\displaystyle 1 +(-1)^{(a_i+x_i)} = \begin{cases} 0 & x\ne a\\ 2 & x=a \end{cases}$

that is, the product $\prod_{i=0}^{n-1} \Big[1 + (-1)^{(a_i+x_i)}\Big] = 0$ unless $x=a$. Therefore

$\begin{array}{rl} \mathbf{H}^{\otimes n} \Big[\displaystyle \frac{1}{2^{n/2}}\sum_{y=0}^{2^n-1} (-1)^{f(y)} \left|y\right\rangle \Big] &= \displaystyle \frac{1}{2^{n}}\sum_{x=0}^{2^n-1} \prod_{i=0}^{n-1} \Big[ \underbrace{1 +(-1)^{(a_i+x_i)}}\Big] \left|x\right\rangle\\ &= \displaystyle \frac{1}{2^{n}} 2^n \left|a\right\rangle\\ &= \left|a\right\rangle \end{array}$

Therefore, the quantum computation gives the answer in one application of $\mathbf{U}_f$:

$\displaystyle \mathbf{H}^{\otimes n+1}\mathbf{U}_f \mathbf{H}^{\otimes n+1} \left|0\right\rangle = \left| a\right\rangle \left| 1\right\rangle$

So what just happened? We began with a superposition of states and finished with the correct answer in one application of the black box operator $\mathbf{U}_f$. That’s the power of Quantum Computing!

## A Sound Correction

As I was taking my coffee over breakfast today, I realized that in the previous post, I did not incorporate the time it took for the sound waves to reach my ear when I pressed the stop button of the stopwatch. Sound waves travel at 340.29 meters per second. At a height of 25 meters, it would take 0.073 seconds for the sound of the explosion to reach the ground. This should be negligible for the purposes of our computation. However, what is really the effect if we incorporate this minor correction?

As seen in the figure below, the recorded time is composed of the time it took for the skyrocket to reach the maximum height plus the time it took for the sound waves to reach my ear, that is,

$t_r = t_a + t_s$

where $t_r$ is the recorded time, $t_a$ is the actual time the skyrocket reached its maximum height and $t_s$ is the time it took for the sound waves to travel from the maximum height to the ground.

We can rewrite the height as

$\displaystyle h_{\text{max}} = - \frac{gt_a^2}{2} + v_i t_a$

Since $v_i = gt_a$,

$\displaystyle h_{\text{max}} = - \frac{gt_a^2}{2} + gt_a^2$
$\displaystyle = \frac{gt_a^2}{2}$

At the maximum height, $h_{\text{max}}$, it would take the sound waves $t_s$ seconds to travel, that is,

$\displaystyle h_{\text{max}} = v_s t_s$

where $v_s$ is the speed of sound. Therefore,

$\displaystyle t_sv_s = \frac{gt_a^2}{2}$
$\displaystyle (t_r- t_a)v_s = \frac{gt_a^2}{2}$
$\displaystyle v_st_r - v_st_a = \frac{gt_a^2}{2}$
$\displaystyle \frac{gt_a^2}{2} + v_st_a - v_st_r = 0$

The last equation above is a quadratic equation which we can solve for $t_a$ using the quadratic formula:

$\displaystyle t_a = \frac{-v_s \pm \sqrt{v_s^2 - 4(1/2)gv_st_r}}{2(1/2)g}$

Substituting the values $g = 9.8$, $v_s=340.29$, and $t_r = 2.3$, we get

$\displaystyle t_a = 2.22$

Using this result, the maximum height is computed to be

$\displaystyle h_{\text{max}} = \frac{gt_a^2}{2} = 24.33$

Comparing this with our previous computation of $h_{\text{max}} = 25.829$, we find that we have overestimated the maximum height by about 1.49 meters. It’s not really that bad so we can just drop the effect of sound.

## New Year, New Heights and the Projectile

I spent my new year celebration at our friend’s place with 2 other colleagues. It was started with a dinner at about 9:30 pm and we bought some bottles of wine in addition to the spirits we already brought. At about 10:30, a street party was setup in the vicinity and about 5 other families joined in a potluck. Marijo’s brother started the fireworks at about that time with David and Gerard (my colleagues) taking turns setting them off. I did not attempt to set them off because I did a lot those things way back as a child and still lucky enough to have my fingers intact.

This is a video of our 2012 New Year’s Celebration:

As Gerard was flying off skyrockets (or kwitis as they are called in my language) David asked me “How high do you think these things go up?”. That was a really good question which got me to thinking. I said “Let’s compute!” So I took my iphone and launched its built-in stopwatch. Gerard flew about 3 skyrockets and I took the time it takes for them to fly until they blow up in the air. The average was found to be 2.3 seconds.

Independent of Mass

Legend has it that Galileo Galilei performed an experiment at the Leaning Tower of Pisa. He dropped objects of different masses to see which of them falls first. Starting from the heaviest to the lightest object, what he found was that, in a vacuum, they reach the ground at the same length of time when dropped from the same height. Using this result, we can compute for the distance travelled by any object under the influence of gravity. At heights near the earth’s surface, the acceleration of objects in the presence of gravity alone is given by

$\displaystyle \frac{d^2h}{dt^2}= \frac{dv}{dt} = -g$

where $h$ is the vertical distance (height), $v$ is the velocity and $g$ is the acceleration due to gravity given by $g = 9.8 \text{m/s}^2$.

The equation above is a simple differential equation which we can solve for the velocity at any time $t$ by integrating both sides:

$\displaystyle \int^{v}_{v_i} dv = \int^{t}_{t_i} -g dt$

which by the Fundamental Theorem of Calculus gives us

$\displaystyle v - v_i = -g(t - t_i)$
$\displaystyle v = -gt + v_i + t_i$

If we take initial time of the rocket launch to be zero, that is, $t_i=0$, we have

$\displaystyle v = \frac{dh}{dt}= -gt + v_i$

We don’t know the initial velocity $v_i$ of the rocket. However, at the maximum height attained by the rocket, the velocity is zero. Using this fact, we can solve for the initial velocity:

$\displaystyle 0 = -gt_{\text{max}} + v_i$
$\displaystyle v_i = gt_{\text{max}}$

where $t_{\text{max}}$ is the time the rocket reached maximum height.

At $t_{\text{max}}=2.3$ seconds, the initial velocity is therefore $v_i = 9.8 * 2.3 = 22.5$ m/s.

Maximum height

We can solve for the height as a function of time by integrating both sides of the velocity equation:

$\displaystyle \int^{h}_{h_i} dh = \int^{t}_{t_i} -gt dt + v_i dt$
$\displaystyle h - h_i = -\frac{gt^2}{2} + v_i t \big|^t_{t_i}$

Since the initial height is zero , that is , $h_i = 0$ and the initial time is zero $t_i = 0$, we have

$\displaystyle h = -\frac{gt^2}{2} + v_i t$

Since at t=2.3 seconds, the rocket reaches the maximum height, we have

$\displaystyle h_{\text{max}} = -\frac{9.8 \times (2.3)^2}{2} + 22.5 * 2.3 = 25.829 \text{ meters}$

Does this make sense? The average height of a building storey is about 3 meters. This is about 8 or 9 storeys high which I think makes sense.

It’s good that my new year not only started with a warm welcome from friends but it also appealed to my physics curiosity.

Thank you to Marijo Condes and family for letting us spend a memorable New Year’s Eve.

## Topology and the Causality of Spacetime

While preparing for tomorrow’s first day of office for 2011, I stumbled upon a hard-copy of my undergraduate thesis. I realized that I don’t have any backup of this piece of work. Thanks to the JotNot application of iPhone, I was able to scan my thesis and convert it to PDF.

Below are samples of the scanned pages. Click on each thumbnail to get the full resolution.

So, if you want to understand how Stephen Hawking and Roger Penrose arrived at their Singularity Theorems, you can read it from the PDF version of my thesis:

Topology And The Causality Of Spacetime

N.B., the file is 40 MB so have some patience.

Einstein’s Theory of General Relativity is one ofthe greatest intellectual achievements in this century. It radically changed our way of looking at the world. lt particularly freed us from our usual Euclidean way of looking at the universe, However, even without the use of Einstein’s equation we can already say something about the universe we live in. It has something to do with the manifold structure of spacetime and the causality conditions imposed bythe speed of light, in that no signal could travel at speeds greater than the speed of light. At this topological level, we impose certain conditions that our spacetime should posses in order for it to be called a reasonable model of our universe.

This thesis is a review article of the causal structure of spacetime. By causal structure, we mean those properties a spacetime should possess so that two pairs of points in it can be joined by a causal curve. A basic notion such as this can already give many results in terms of our understanding of the universe.

When we say that a given model of the universe is reasonable , we mean the following: (i) a lorentz metric can be defined on it,(ii) it shoud be orientable in space and time, (iii) it does not contain closed timelike curves and those curves, though not closed but are “almost closed” , which will be made more precise later, (iii) it possesses a surface( achronal) where we can define initial data set that will determine the evolution of the universe. `

In Chapter ll, we are going to review those aspects of mathematics that are useful in causal analysis. We will start with a review of manifold theory. We will define what we mean by a manifold and all other defined structures on it. We will notice that even without the metric, many consequences of the conditions enumerated above will be derived The only thing we assume on our manifold is that it allows the existence of a Lorentz metric.

In Chapter III, we will show that not all manifolds admit a Lorentz metric. In fact it does not make sense to talk of the surface of the sphere as a two dimensional model of spcetime since a Lorentz metric cannot be defined on the sphere. We will also show that compact spacetimes are of little interest to cosmology because they allow the existence of closed timelike curves.

Chapter IV is a brief chapter that applies the concepts introduced in Chapter III to the proof of Hawking’s Singularity Theorem. Here we will define what we mean by a singularity and learn that a generic class of solutions of Einstein’s equation is singular. Singularities do not tell us that the theory itself is defective, but that they are really physical entities that exist.

Although causal analysis is already a mature subject, it has only been available to a handful of people because it’s nature is in a way abstract. The purpose therefore of this review is to present more details of the subject and providing proofs to some statements that have been omitted in standards texts.

## John Wheeler, A great physicist!

John Archibald Wheeler is one of my most admired physicist. He just died recently and I want to make a small tribute to him to did so much in General Relativity. Wheeler is the person who coined the word “black hole”, a concept which captivated my imagination when I was yet a kid and a concept which I eventually studied on my own in the University. He wrote one of the best books in General Relativity entitled “Gravitation”. This is a thick and heavy book full of physics and mathematics. It introduces advanced mathematical concepts as you progress in your study of Relativity in a very geometric way. This book has full of illustrations that really whets your appetite for studying advanced physics.

I have bought many books authored by Wheeler. One of them is “Exploring Black Holes“, with Taylor as co-author. I bought this book in Borders bookstore in Singapore. Unfortunately, we don’t have these kinds of books in the Philippines. A friend of mine also lent me a layman’s book written by Wheeler entitled “Geons, Black Holes & Quantum Foam”. This book gave accounts on Wheeler’s contribution to the Manhattan Project and the other great people whom he worked with.

I have a professor before who took his PhD in US who told me that whenever Wheeler gives a lecture at 7 am in the morning, he will always attend it no matter how cold it is in New York. That’s how big an impact Wheeler had on him.

To the great man Wheeler, thank you for inspiring us to study one of the greatest theories in the 20th century!