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 and 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
such that . The numbers a and b are complex numbers and the symbol is defined as
where 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 or 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 in state and in state .
If the state of a QBit is a superposition of basis states and , 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 and can be written as 1×2 matrices:
Using this representation, we can write a general QBit as:
So now we know that every QBit is a linear combination of ket vectors and . These ket vectors have a corresponding “bra” vectors and . In matrix representation, the bra basis vectors are defined as:
For a general QBit , the corresponding bra vector is
There is an operation between bra and ket vectors of the basis states called inner product which is defined as:
Using the above rules, we can define the inner product of any two QBits and as
Using the above definition of an inner product, the norm of a vector is defined as
Geometrically, the norm is the length of the ket .
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 acts on to give another vector . We write this as
Since the basis vectors and 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:
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:
Therefore the matrix representation of the Hadamard operator is
The identity operator is defined as the operator that maps a vector into itself and is symbolized as :
The NOT operator is defined as
What it does is transform the to 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:
If is the Hadamard operator, that is, , then the above operation becomes:
Since we know that:
We can then write this as:
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.
where we symbolize as the operator corresponding to the Hadamard operator acting on bras.
The matrix representation of the Hadamard operator acting on bras is therefore:
In general, the matrix representation of is the conjugate transpose of the matrix of . In simple terms, this means take the transpose of 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 be an operator and a vector and let , then the norm of is
This means that
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 and be the input and output QBits,respectively. The general state of this quantum system is a superposition of the following states:
which could also be written as
or, if we take them as binary representation of numbers, we can write them concisely as
Using the above basis vectors, we can write a general 2-QBit system as:
where the numbers are complex and n=2. The summation is up to since the maximum number n QBits can represent is . 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 represent a unitary operator implementing the function f. The function f is a function that takes the numbers from the domain to , that is,
For a two-QBit system, the form of quantum computation is
where the symbol represent bitwise OR operation. The table below will give you the results of the bitwise OR operation for every combination of values in :
A simple but important example of a unitary operator acting on two QBits is the gate, defined as:
Here is the complete action of the :
If you study the table above, you’ll notice that if the input QBit is in the state , the output QBit stays the same. However, if the input QBit is in , 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 which stands for Controlled-NOT gate.
Let’s now go back to our original problem. There is a positive number that is less than . We want to find this number using quantum computation. We are given a black box operator whose action on a bra is
where is the unknown number we are going to guess and are the i-th bits of x and a.
So how many times do we have to apply in order to guess the number ?
To solve this, we need input QBits and 1 output QBit. We will initialize our QBits to . So the initial configuration is
Notice how we separate the input and output qubits.
Next we apply the Hadamard operator to each QBit:
We have seen the Hadamard operator earlier. For the sake of convenience we’ll repeat it here:
We can generalize this by letting x be either 0 or 1:
We can use this to compute the action on two QBits and generalize:
Using the above formula, the action of on is
The next step is to apply our operator which was defined above:
Let’s break this down a bit. Since the value of is either 0 or 1, we have 2 cases:
Combining these 2 we have
Finally, getting the Hadamard action on this gives:
Expanding underbrace B gives us:
Expanding underbrace A above:
We have found earlier that
Substituting this to the above and noting that
where we have interchanged the order of the summation. To simplify the term with the underbrace, notice that
We can therefore write the factor in underbrace as
that is, the product unless . Therefore
Therefore, the quantum computation gives the answer in one application of :
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 . That’s the power of Quantum Computing!