# Deustch-Jozsa algorithm for a specific problem, doesn't make sense?

I am trying to implement Deustch-Jozsa Algorithm where function f(x) = 0 for even and f(x) = 1 for odd, for a four-bit number. After writing the numbers out I found a pattern as described below

Therefore as you can see the from the image, all I need to do is add the CNOT gate to the last register so to implement the oracle and here is my circuit that I have written for the same. Here is the circuit and output for the same

My question is shouldn't the output be '1111' since this is a balanced function. The number corresponding in the circuit is 2 = '0010' and the output is showcased for the same. I would highly appreciate breakdown. Also the does the circuit implement the oracle where f(x) = 0 is even and for

Your oracle is correct. The mistake here is that you initialized $$q_1$$ to $$|1\rangle$$ instead of the ancilla qubit. So the proper circuit here would be something like this:

This would give the state $$|1000\rangle$$ with probability $$1$$, which shows that $$f(x)$$ is balanced.

For your second question, recall that Deutsch-Jozsa algorithm guarantees that either the final measurement will give $$|0\rangle^{\otimes n}$$ with probability $$1$$, in which case our function is constant, or it will yield some other state, in which case we have a function that's balanced. Our measured state need not be $$|1\rangle^{\otimes n}$$ to deduce that $$f(x)$$ is balanced.

• so the reason for me initializing the Q1 -> to |1> is because I was trying to encode the input to number 4 which corresponds to |0100> from the table I created in the first image. Also The reason I didn't initialize the ancilla qubit to |1> is because whenever the number is odd I want the oracle to output |1> and if it is even I want |0>. As you can see from the image above for even numbers the last qubit is always |0> therefore for even it will output |0>, but for odd numbers the last digit is |1> changing the output to |1> for the output. Again would appreciate clarification if not correct. Commented Feb 15, 2023 at 15:09
• @JaZZyCooL I don't understand what you mean by encoding an input. The only thing Deutsch-Jozsa expects is an oracle $U_f$ which maps $|x\rangle |y\rangle \to |x\rangle |y\oplus f(x)\rangle$ and given that it determines if $f$ is balanced or constant. It accepts no other input. Also, you need the ancilla to the state $H|1\rangle$ in order to induce phase kickback. Commented Feb 15, 2023 at 15:36
• @JaZZyCooL You can read more about Deutsch-Jozsa here. Commented Feb 15, 2023 at 15:41
• I am sorry I should have made it clear basically for even number values my oracle should output 0 and for odd number values oracle should output 1, which is why I kept the anicalla qubit to |0> since natually for even numbers the last digit is qubit is |0> which makes the oracle keep the f(x) to 0 and only change to |1> if the last qubit is |1>. Basically f(x) is a four bit function where for even number f(x)=0 and for odd f(x)=1 and using Deutsch-Jozsa I am trying to figure out whether it is balanced or not. Therefore, for oracle giving me the correct output I kept ancilla |0> Commented Feb 15, 2023 at 15:48
• I see that makes a lot of sense thank you :) Commented Feb 15, 2023 at 15:59