Introduction to Grover's Algorithm

Another algorithm that has an important place among quantum algorithms is the Grover algorithm. It was developed by the Indian physicist Lov Grover in 1997.

I described the Deutsch-Jozsa algorithm algorithm in my previous articles. Although the Deutsch-Jozsa algorithm helps us find the characteristics of the functions and gives us good information about the working principles of the quantum algorithm, it has no application to a real physical problem.

Grover's algorithm allows us to solve real physical problems.

In this article, I will give information about the working principle of the Grover algorithm and its application as an example.

Let's imagine two cities, A and B!

Suppose there is more than one way to get from A to B. What we want is to find the shortest path among the existing path options.

When we want to solve this problem through a classical algorithm, it will deal with each option one by one with iterations and reach the result. However, Grover's algorithm will do this with iteration. Thanks to this situation, we will reach the desired result in a shorter and faster way.

Grover's algorithm passes the problem through two stages while doing this.

Stage 1: It evaluates how many qubits we have and makes the amplitude of the probable result negative, but leaves the amplitudes of the qubits with no real solution positive.

Stage 2: It will increase the amplitude of the qubit that it considers as its real solution, that is, the qubit that has negative amplitude, and will make it positive again. The amplitudes of the other qubits will be shorter than in their original form.

Let's take a look at the details of this algorithm.

Considering our example again, let's have x₁, x₂, …… x*, .…..x_N path options between cities A and B, and x* represents the shortest path.

Performing step 1 first will make the actual solution qubit x* change, which seems possible.

Our operator that will change the amplitude of the x* solution is as follows;

Now let's look at how to increase the amplitude of the x* qubit.

The operator to increase the size of the x* amplitude is given below.

In this way, the amplitude of x* is increased and the amplitudes of other qubits are shortened. The Grover algorithm can perform this process with as many iterations and reach the solution in a short time.

Reference

https://www.youtube.com/watch?v=jhmaI4Hm444&list=PLqNc_xpYGu775P7iJA7Kvfxmv_Fm9wwHj&index=4

https://quantum-computing.ibm.com/composer/docs/iqx/guide/grovers-algorithm

Comments

Bloch Sphere – Geometric Representation of Quantum State

It is very difficult to visualize quantum states before our eyes. The Bloch sphere represents quantum state functions quite well. The Bloch sphere is named after physicist Felix Bloch. As you can see in the Bloch sphere figure below, it geometrically shows the pure states of two-level quantum mechanical systems. The poles of the Bloch sphere consist of bits |0⟩ and |1⟩. Classically, the point on the sphere indicates either 0 or 1. However, from a quantum mechanics point of view, quantum bits contain possibilities to be found on the entire surface of the sphere. Traditionally, the z-axis represents the |0⟩ qubit, and the z-axis the |1⟩ qubit. When the wave function in superposition is measured, the state function collapses to one of the two poles no matter where it is on the sphere. The probability of collapsing into either pole depends on which pole the vector representing the qubit is closest to. The angle θ that the vector makes with the z-axis determines this probabilit...

Quantum Phase Estimation - Calculating an Eigenvalue

We continue our series of fundamental and ongoing quantum algorithms. In today's post, we'll look at the eigenvalue calculation that is familiar to anyone in both the basic sciences and engineering. We will consider a slightly different situation, of course, our work is quantum. Let's consider the quantum state of a system! When we make an observation, we obtain real observation values by calculating the eigenvalues and eigenvectors of the state in that system, the mathematical calculation that helps us to have information about the position, momentum, or energy of that system. So, how can we find the eigenvalues of the unitary operators, which act on a system without changing its size, that is, preserve its physical size? To solve this problem, we will examine the Quantum Phase Estimation solution. In order to find the eigenvalues of the unit operator U, we need to find the value of the phase ϕ, which is inside the exponential value. However, it is not that easy. A qua...

Shor's Protocol - Example Solution

Finally, we have come to the famous Shor's definition of the algorithm in this article. Before applying this algorithm, we examined in detail the three mathematical operations required for our algorithm. These three necessary mathematical expressions were modular arithmetics, quantum Fourier transform , and quantum phase estimation . As you may remember, Shor's algorithm is an algorithm that gives prime factor values of large numbers. To show that this protocol works, we will write an algorithm that gives the prime factors of 15. The binary equivalent of the decimal number 15 consists of 1111 qubits. Now let's examine Shor's protocol in detail. If we write it in a regular way, we can write the state vector | ψ 3 > as follows. Now, let's measure the last four qubits. In this case, we would have measured the situations |1>, |2>, |4>, |8> with 25% probability. Suppose we have reached the state |8> with a probability of 25% in our measurement re...

Era Quantic | Quantum Computing and Information Articles

Search This Blog