# Deutsch–Jozsa algorithm: why is $f$ constant?

I'm trying to understand how the Deutsch–Jozsa algorithm works with the following circuit:

Circuit in Quirk

Since we have the top 2 wires measuring $$|0\rangle$$ with 100% probability, it means $$U_f$$ is constant. And that's what I'm having trouble understanding...what exactly is constant?

If I isolate $$U_f$$ I get this: Oracle function

I understand the concept of balanced and constant functions, and that an n-bit binary string will have $$2^n$$ mappings, which gives $$2^n$$ possible functions. So how can I see that $$f$$ is constant in the isolated circuit above?

## 1 Answer

The circuit you gave implements an oracle for a function $$f(x) = 0$$, which is constant.

You can observe that there are no gates leading from the top two wires (inputs $$|x\rangle$$) to the bottom wire (output $$|y\rangle$$). Since the oracle is supposed to transform $$|x\rangle|y\rangle$$ into $$|x\rangle|y \oplus f(x)\rangle$$, and $$|y\rangle$$ always remains unaffected, you can see that $$f(x) = 0$$.

• Wow, you are fantastic, thanks. I'm new to quantum programming, so I'll need to meditate on this. Is there a way to "extract" the oracle function to a classical form? Like a matrix or something. – Fernando Mar 23 '19 at 4:06
• You can reverse-engineer the matrix of the unitary representing the oracle by applying the circuit (stripped of the H before and after oracle application) to all basis vectors in turn and writing down the amplitudes of the results. For example, for your oracle you'll start with your "isolated" Uf to get the oracle effect on 00; then you'll flip the state of the first qubit to get the oracle effect on 10, and so on. (By the way, your circuit swaps the two inputs to the oracle, so strictly speaking it's not an implementation of an oracle - oracles are supposed to leave their inputs unchanged.) – Mariia Mykhailova Mar 23 '19 at 4:36
• Ok, I'll read more and try some stuff on my own. If case of trouble, I can post a more specific question. Спасибо )) – Fernando Mar 23 '19 at 8:15