Understanding Deutsch's Algorithm in Quantum Computing
Deutsch's Algorithm is a fundamental quantum algorithm designed to solve the problem of determining if a given function is constant or balanced. This algorithm leverages quantum principles such as superposition and entanglement to provide a more efficient solution compared to classical methods. By employing quantum gates like Hadamard and an unknown function gate U, Deutsch's Algorithm showcases the power of quantum computation in addressing specific problem sets.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Quantum Algorithms We have now gotten to know some of the quantum gates. Quantum algorithms are composed by combining the gates. For many problem waiting to be solved, we do not yet have a good quantum algorithm. However, for example factorization, search, and some simulation algoritms have been invented. We will now take a look at the simplest existing quantum algorithm: Deutsch algorithm
Deutschs Problem The Deutsch algorithm is made to answer the following problem: Given a function f: {0,1} {0,1}. The function is either: 1. f(0) = f(1) a constant function or 2. f(0) f(1) a balanced function . Which one is it?
Classical Solution Classically the problem can be answered by testing the unknown function twice. The U gate contains the unknown function. For example the first test the second test f(1) f(0) 0 0 1 We input value one to the U gate. If the measurement gives us zero, the function is constant. If the measurement gives us one, the function is balanced. We input value zero to the U gate. The measurement gives us zero.
Deutschs Algorithm The quantum algoritm for answering the problem is this. Here we now have two qubits (marked by the subscripts). The H gates are the familiar Hadamard gates and the U gate again contains the unknown function f.
Deutschs Algorithm Let s first divide the problem into pieces and then write down the state of the qubits at every step.
Deutschs Algorithm Remember that the Hadamard gate s operation on a qubit is 1 | 0 + | |0 1 2 1 | 0 | |1 1 2 |01| |?1 = 12 |?2 =1 The state of the two qubits is expressed as a product of them. |11 | 02 | |01+ 12 2
Deutschs Algorithm |?2 =1 Let s open the brackets. |11 | 02 | |01+ 12 2 =1 |01 |02 |01 |12+ |11 |02 |11 |12 2
Deutschs Algorithm The operation of the U gate on the state is |?1 |?2 |?1 |? + ?(?)2 |?3 =1 |01 |0 + ?(0)2 |01 |1 + ?(0)2+ |11 |0 + ?(1)2 |11 |1 + ?(1)2 2 =1 |01 |?(0)2 |01 |1 + ?(0)2+ |11 |?(1)2 |11 |1 + ?(1)2 2
Deutschs Algorithm We can divide the examination into two parts according to the nature of the unknown function. 1 2 1 2 |01 |?(0)2 |01 |1 + ?(0)2+ |11 |?(0)2 |11 |1 + ?(0)2 if ? 0 = ?(1) |?3 = |01 |?(0)2 |01 |1 + ?(0)2+ |11 |1 + ?(0)2 |11 |?(0)2 if ? 0 ?(1)
Deutschs Algorithm By reordering the terms, we get a bit simpler equations. 1 1 |01+ |11 |?(0)2 |1 + ?(0)2 if ? 0 = ?(1) 2 2 |?3 = 1 1 |01 |11 |?(0)2 |1 + ?(0)2 if ? 0 ?(1) 2 2
Deutschs Algorithm Applying the H gate twice, we end up in the original state 1 | 0 + | |1 1 |1 2 1 | 0 | |0 1 |0 2 1 |01 |?(0)2 |1 + ?(0)2 if ? 0 = ?(1) 2 |?3 = 1 |11 |?(0)2 |1 + ?(0)2 if ? 0 ?(1) 2
Deutschs Algorithm If we now measure the uppermost qubit s value, we get to know if the function is constant or balanced. 1 |01 |?(0)2 |1 + ?(0)2 if ? 0 = ?(1) 2 |?3 = 1 |11 |?(0)2 |1 + ?(0)2 if ? 0 ?(1) 2
Other Quantum Algorithms Even if it might feel quite complicated, the Deutsch algorithm is the simplest example of quantum algorithms. Maybe the most famous (and more complicated) ones are: Shor s algorithm for integer factorization. It solves the following problem: given an integer N, find its prime factors. Grover s algorithm for inverting a function. It finds the input parameter x when it is given the solution of a function for that input y = f(x). The both of them can be used, for example, in cracking passwords. Reference: https://en.wikipedia.org/wiki/Quantum_algorithm
What Did We Learn? We can built up quantum algorithms almost as we did with classical logic circuits. Quantum algorithms become early quite complicated but not impossible to understand.* Because it is so complicated to come up with new quantum algorithms, we do not actually have an algorithm for every problem waiting to be solved. Maybe you will be the next person to find a quantum algorithm for solving a problem! *If you struggled with the Deutsch algorithm, don t worry. It is quite a tough nut to crack. Try to go it through slowly and with thought.
