Quantum computation, algorithms and some walks.. pt.1

During the last meeting of the ECRYPT-NET project in Leuven, I gave an introduction to Quantum Algorithms. In the first part, I explained quantum computation, it is natural that we need to have a base. In this post, I will give more detailed explanation of it. First, we need to understand the concept of superposition in quantum physics. To achieve this, we are going to go back to the idea from Schrödinger, i.e., a cat that may be simultaneously both alive and dead. This phenomenon is called superposition in quantum physics and quantum computers take advantage of this. If you are interested about how physically implement a quantum processor you can see at [2].

Well, computers aren't made with cats inside. Computers use bits and registers to work. So, how is it possible to compute with a quantum computer? How is it possible to represent bits? How is it possible to take advantage of the superposition?

Quantum Notation

First, let's learn about the Dirac notation, that is commonly used in Quantum physics and in most of the literature about quantum computers.  Since Blogger doesn't allow me to create mathematical equations, I will get some help from physciense blog and pick some images from them:

 
The Dirac notation could be a little bit different. If you want to check about it, I selected some nice lecture notes in the following links: Lecture 1 and Lecture 2.

So, the bra-ket notation is just vectors and we are going to use this to represent our qubit, yes we call the bit of a quantum computer by this name. In classical computers we represent a bit with 0 and 1 but in quantum computers it is a little bit different. We can represent the states as follows:

As the image show to us, the qubit is 0,1 or a superposition of 0 and 1. However, if we measure, i.e., if we see the qubit we lose the superposition. In other words, our state collapses and we cannot take advantage of the superposition anymore. In the same way that in classical computers we have gates, the quantum computer also has gates. One very famous gate is the Hadamard gate. This gate has the property to put a qubit in the superposition state. We can see the action of this gate in the following image:

Quantum Algorithms

Now, we know what is a qubit and how we can operate with it. We can move for the next step and create some algorithms to solve problems. The most common and very well-known example came from Deutsch and Jozsa. It is known by Deutsch-Jozsa problem and consist of:

• Input:  f: {0,1}^n to {0,1} either constant or balanced
• Output:   0 iff the function f is constant
• Constraints: f is a black-box

In the classical computers we can represent this problem such as:

If we solve this problem with a quantum computer, we are going to make exactly 1 query. The function f will be implemented as a black-box in the quantum computer and it will be:

However, if we just use this implementation, it is not enough to solve the problem. In order to solve this, we are going to create a quantum circuit and use Hadamard gates. In fact, the Hadamard gates are going to help us to take advantage of the superposition. We are going to have this circuit:

Now, we have the circuit to determine if a function is constant or balanced. Nevertheless, how do  we compute this circuit? How does it work? In order to answer these questions, we work out the qubit after each gate. In the end we have the final measure. Suppose that we just have one qubit and we start it in state 0 and pass through it the first gate. We are going to have this:

 After this, we can see that we put our qubit in a superposition state. Now, we go to our function and call our black box. The result of it can be seen as:

The third step, we are going to use the interferences to "reconstruct" the qubit. In the last step, we are going to compute now the last gate and see what is "expected" when we measure:

In the end, we have that final state, i.e., if the function is constant "f(0)=1" then we are going to have the result as qubit in 0. However, if the function is balanced "f(1)=1" then we are going to have the qubit in 1. The algorithm can be generalized and it works for a system with "n"-qubits. It is possible to find more information in [1]. Also, you can check this class.

In my next blog entry, I will talk about  Shor's, Grover's algorithms and Random quantum walks. However, we just saw the begging of quantum algorithms. If you want more information about it, you can check the slides from my presentation in Leuven on my website.

[1] David Deutsch and Richard Jozsa (1992). "Rapid solutions of problems by quantum computation". Proceedings of the Royal Society of London A.

[2] Gambetta, Jay M., Jerry M. Chow, and Matthias Steffen. "Building logical qubits in a superconducting quantum computing system." arXiv preprint arXiv:1510.04375 (2015).