The Deutsch-Jozsa Algorithm
To understand how the Deutsch-Jozsa Algorithm works, let's have an input where n=1. The process will be the same regardless of the value of n. If all measurements of n equal to 0, the function was constant. If at least one of the measurements results in a 1, the function would’ve been balanced.

In our example, since n=1, if the result is 0, the function would’ve been constant. Otherwise, if the result is 1, the function would be balanced.

To implement the circuit, we need 2 qubits: the first qubit, q0 , will be our “data qubit” (x), and the second qubit, q1 , will be our “helper/ancilla qubit” (y). We then initialize the qubits with q0 into the |0> state and q1 into the |1> state (We do this by applying an X gate).

Mathematically, it would look like this:

Next, we need to put the qubits in a superposition by applying 2 H gates; an H gate on q0 , and another on q1 . (Ignore the ID , it’s just a placeholder so my Hadamard gates are aligned)

After applying the Hadamard gates on q0 and q1 , we can expand the equation such that it looks like the following:

Now, we need to implement Uₕ , the quantum oracle/unitary operation. Uₕ does 2 things: it implements the function, h(x), and outputs the XOR of the bits of h(x) and the bits of the helper/ancilla qubit. If h(x) is a constant function (h(x) = 0), we don’t need to do anything, but if h(x) is a balanced function (h(x) = 1), all we need to do is to apply an X gate to the helper/ancilla qubit. Uₕ is a lot harder to figure out for balanced functions and is more complicated when n gets larger.

For our n=1 example, the oracle performs a CNOT gate, with q0 as the control qubit and q1 as the target qubit. After implementing Uₕ , the helper/ancilla qubit has a state of y XOR h(x) . This means that if the data qubit is |0> , the helper/ancilla qubit will be y XOR h(0) . If the data qubit is |1> , the helper/ancilla qubit will be y XOR h(1) instead.

We can actually rewrite the states mathematically like this:

And we can factor out the helper/ancilla qubit so it looks like this:

We apply another 2 H gates to our qubits. We do this so the |1> terms can cancel out if h(0) = h(1) and if h(0) ≠ h(1), the |0> terms will be canceled. In other words, for the data qubit, |0> becomes |0> + |1> , and |1> becomes |0> - |1> . For the helper/ancilla qubit, if it’s a |0> - |1> , it will become a |1> .

Now, with a bit more math and simplifying, we can get this:
['Ryan Lam']
['Technology', 'Physics', 'Tech', 'Quantum Computing', 'Computer Science']