# 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.