Blog

ProjectBlog: Quantum Algorithms

Blog: Quantum Algorithms


In previous articles we introduced the main topics related to Quantum Computing ( https://medium.com/@agus.bignu97/quantum-computing-7662907581e5) in order to have a basic idea of what is it and the definitions we need to know so that one is capable of understanding the entire work.

Quantum computing algorithms can be divided into three groups: algorithms based on the quantum version of the Fourier transform, search algorithms and quantum simulations. In this section some well-known and relevant algorithms of quantum computing will be introduced, we will proceed to explain their purpose and their logic and, in turn, we will analyze in detail their respective circuits [1].

The algorithms to analyze are the following:
1. Deutsch Algorithm
2. Grover Algorithm
Deutsch’s algorithm combines what is known as quantum parallelism with another quantum phenomenon called interference. The problem that this algorithm tries to solve is how to determine if the function 𝑓(𝑥) of binary variable and binary image is constant or alternates with a minimum number of calls to the function 𝑓(𝑥). It is shown that classically two calls are needed while in the quantum algorithm is enough with one. It is the first quantum algorithm that showed quantum superiority.

The circuit of this algorithm is as follows:

Figure 1: Quantum circuit of the Deutsch algorithm. [2].

In figure 1 one can see that we have two qubits to which a Hadamard gate is applied. This gateway is to prepare the qubit in a superposition. In this case we have as input

(1)

with the help of the Hadamard gates we put the qubits into the following superposition states

(2)

getting

(3)

In figure 1, we have the Uf gate that performs the following action

(4)

U stands for unitary and for practical purposes we will treat it as a black box. This gate affects the state

(5)

by adding the following term

(6)

Applied, then, to (3) we obtain

(7)

Finally, we apply another Hadamard gate to the first qubit, remaining (7) as follows

(8)

The established conditions tell us that if

(9)

is 0 and 1 in other cases. In order to keep things easy to read, we rewrite (8)

(10)

In this way, by measuring the first qubit, we can determine 𝑓(0)⊕𝑓(1). That is, the system allows us to know a global property of the function in a single evaluation. With a “classic” device we would have taken at least two evaluations. It should be noted that if we were in classical computing, we could not obtain information from the two solutions at the same time. However, in quantum computing solutions can interfere with each other to give us a global solution, as we got.

Finally we are going to analyze Grover’s algorithm. We will do it without introducing too much into the circuit, unlike the other example. This algorithm belongs to a special class of quantum algorithms called quantum search algorithms.

This type of algorithm attempts to solve the following problem: given a search space of size 𝑁, and without prior knowledge of what it contains, we want to find an element of that search space that satisfies a known property in the shortest possible time. Classically N operations are needed to solve this type of algorithms, but in the quantum version they are solved making √𝑁 operations.

The algorithm works in the following way [3]: before observing the search set we have no idea which element fulfills our property. Moreover, all positions have the same probability. In this way, we can express it in terms of a state called uniform superposition (Hadamard transformation)

(11)

Since all positions have the same probability, when measuring the probability we would obtain 1/𝑁 = 1/2^𝑛. This is where we use a procedure called amplitude amplification. This increases the probability of obtaining the correct item in the final state. Next we will ennumerate the steps to carry out the algorithm

  1. We begin the amplitude amplification in |𝑠⟩. This state is build as follows
(12)

The initial state is

(13)

2. We apply a reflection 𝑈𝑓 to the state

(14)

Geometrically corresponds to a reflection of the |𝜓t⟩ state over -|𝑤⟩.

3. We apply a new reflection 𝑈s to the state |𝑠⟩. This reflection is as follows 𝑈𝑠=2|𝑠⟩⟨𝑠|−1. In this way, the resultant state is

(15)

We perform a rotation of the initial state to the winning state.

4. Return to step 1.

We repeat this algorithm several times until reaching the winning state. In the end, as we said at the beginning we will end up doing √𝑁 operations.

Figure 2: Algorithm described above. [4]

Conclusions

All in all, we have introduced two important algorithms in Quantum Computing. Understanding these algorithms will make the reading of future articles easier.

With this article we finished the theoretical basis of Quantum Computing. In the next articles we are going to explain the theoretical basis of Artificial Intelligence.

Keep it up!

References

[1] Michael A. Nielsen & Isaac L. Chuang. Quantum Computation and Quantum Information, 10th Anniversary Edition. Cambridge University Press, 2009.

[2] Michael A. Nielsen & Isaac L. Chuang. Quantum Computation and Quantum Information, 10th Anniversary Edition. Figure 1.19. Quantum circuit implementing Deutsch’s algorithm. Cambridge University Press, 2009.

[3] IBM Q Experience. https://quantumexperience.ng.bluemix.net/qx/tutorial?sectionId=full-user-guide&page=004-Quantum_Algorithms~2F070-Grover%27s_Algorithm

[4] IBM Q Experience. https://quantumexperience.ng.bluemix.net/qx/tutorial?sectionId=full-user-guide&page=004-Quantum_Algorithms~2F070-Grover%27s_Algorithm Fig. 5

Source: Artificial Intelligence on Medium

Leave a Reply

Your email address will not be published. Required fields are marked *

Back To Top
a

Display your work in a bold & confident manner. Sometimes it’s easy for your creativity to stand out from the crowd.

Social