Skip to main content

Deutsch Algorithm

 

The Deutsch algorithm was discovered by David Deutsch in 1985. The main motivation for this algorithm is the problem of how many steps to determine the characteristic of a given function.

Classical computers, therefore, classical algorithms can determine the character of the given function in at least two steps. Because, as you know, classical computers are made by processing the 0 or 1 bits separately.

However, for the solution to our motivation problem, the characteristic of the function can be found in one step by quantum computers, that is, by quantum algorithms. As a result of measuring our qubits in superposition, as a matter of fact of quantum physics, enables us to reach the desired result in one step.

As David Deutsch said “Computers are physical objects, and computations are physical processes. What computers can or cannot compute is determined by the laws of physics alone. . .”

Let's take a basic look at this easy algorithm.

Let's define a function that maps 0 and 1 to 0 and 1.

 

Let this function have the following characteristics;

It solves the characteristic of the function defined above in at least two steps.

With the quantum algorithm, I wrote below, the characteristic of this function can be solved in one step.

Now let's pass the state vector |Ļˆ2> through the Hadamard operator.

Finally, when we measure the state vector, we find that if we get |0> it is a constant function, and if we get |1> we find that it is a balanced function.





Reference

https://people.vcu.edu/~sgharibian/courses/CMSC491/notes/Lecture%206%20-%20Deutsch%27s%20algorithm.pdf

Labels:

Comments

Post a Comment

Popular posts from this blog

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...
1 comment
Read more

Bernstein–Vazirani Algorithm

  Quantum computers currently available are not sufficient to solve every existing classical problem due to their own characteristics. This does not mean that they are inferior to classical computers, or that, on the contrary, quantum computers should give all kinds of advantages over classical computers. Popular quantum algorithms solved in quantum computers are algorithms created by taking advantage of the superposition and entanglement properties of particles. So, they are algorithms created to show the prominent features of quantum properties. Today I will talk about an enjoyable algorithm that demonstrates the efficiency and speed of these quantum features. Known as the Bernstein - Vazirani algorithm is a quantum algorithm invented by Ethan Bernstein and Umesh Vazirani in 1992. The purpose of this algorithm, which is a game, is to find a desired number. To put it more clearly, let's keep in mind a string of binary numbers, for example, 1011001. Next, let's write an algori...
Post a Comment
Read more

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...
Post a Comment
Read more