Cirq Programming 3: The Deutsch Jozsa Algorithm
Ok — here goes! In this blog post, I will be explaining a part of chapter 9 of Quantum Computing as a High School Module, the Deutsch Jozsa Algorithm.
Quantum algorithms require the usage of quantum gates, so it is natural to move to simple quantum algorithms after learning about quantum gates. Quantum algorithms are just algorithms that are made for quantum computers that do the job of classical systems better. The more notable algorithms, like Shor’s Algorithm, are actually applicable in the real world. However, the most simple quantum algorithms only prove that quantum computing can be faster than classical systems.
The Deutsch Jozsa Algorithm is one of those simple quantum algorithms that proves that quantum algorithms can be faster than quantum systems. The algorithm is a quicker way to determine whether a hidden function is constant, or balanced, but it should be made clear that this does not provide any real world application. A function is constant if the qubit(s) that the function was applied to outputs 0 or 1 all of the time no matter what the input is. On the other hand, a function is balanced if the qubit(s) that the function was applied to outputs 0 and 1 50% of the time each.
The simplest version of this algorithm is called Deutsch’s Problem, where the function is only applied to one qubit and the solution is whether the function is constant or balanced. In this case, there are only 4 possible combinations for the secret function which we will call f. First, f(0) = 0 and f(1) = 0. Second, f(0) = 1 and f(1) = 0. Third, f(0) = 0 and f(1) = 1. Fourth, f(0) = 1 and f(1) = 1. Here, the first and the fourth combinations would be constant, and the second and third combinations would be balanced.
A classical system would require 2 measurements to figure out the solution to this problem, one measurement occurring when the qubit was 0 and the second when the qubit started as 1. For example, if you measure that f(0) = 0, you still need to measure using the function a second time in order to determine what happens in f(1); if f(1) = 0, then you now know that the function is balanced, and if f(1) = 1, then you know that the function is balanced.
A quantum system, however, only needs to measure one qubit once to determine whether the secret function is constant or balanced. This is due to the superposition and parallelism of quantum computers which allow these quantum systems to calculate all of the possibilities at once. First, initialize two qubits into the state of 1. Then, apply Hadamard gates to both qubits. This puts the qubits into a non entangled, superposition state of all of the possible inputs (00, 01, 10, 11). After this, apply the secret function to the two qubits. Next, you apply a second Hadamard gate to the first qubit. This second gate takes the qubit out of superposition, putting the qubit back into a definite state. Finally, you can measure the state of this qubit. If the qubit is measured as 0, then the function was balanced, and if the qubit was measured as 1, then the function was constant.
Deutsch’s problem only deals with 2 qubits, but the Deutsch Jozsa Algorithm can solve this problem no matter how many qubits there are. But as mentioned before, this algorithm does not serve any practical purpose, and only proves that quantum computers can be faster than classical systems. What was mentioned in this post is just an overview of the algorithm, and does not go in depth into the math of the algorithm. Aside from a mathematical representation it is also possible to represent the Deutsch Jozsa Algorithm using the Mach Zehnder interferometer and phase shifters.
For more information about the mathematical side of the algorithm, you can view Qiskit’s article about the Deutsch Jozsa Algorithm here, and for more information on the Deutsch Jozsa in chapter 9 of Quantum Computing as a High School Module here.
The Deutsch Jozsa Algorithm, like all other quantum algorithms, can be programmed using quantum languages, like Google’s Cirq. The Cirq code of the Deutsch Algorithm is shown below.
As shown above, besides the main function, there are two additional functions in addition to the main function. The first of these functions is the “make_oracle” function. In the main function, there is a section where the secret function seems to be defined as an integer. Then, depending on whether it is a 0 or a 1, the secret function is then defined as balanced or constant. The second function besides the main function is the “make_deutsch_circuit” function. This function is pretty self-explanatory, and it just creates the quantum circuit of the Deutsch Jozsa Algorithm mentioned earlier where both qubits are put into superposition by hadamard gates.
Finally, there is the main function where both of the functions mentioned above are called. First, the main function chooses the qubits that will be used in the circuit. Then, after defining the secret function, the circuit is created and also printed out onto the screen to be viewed. Finally, the circuit is simulated using the simulator and the results of the simulation are printed onto the screen. An example of an output from the code can be viewed below.
