1
$\begingroup$

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 enter image description here

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 enter image description here

enter image description here

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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:

                                              enter image description here

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – JaZZyCooL
    Feb 15 at 15:09
  • $\begingroup$ @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. $\endgroup$
    – Giorgos Giapitzakis
    Feb 15 at 15:36
  • $\begingroup$ @JaZZyCooL You can read more about Deutsch-Jozsa here. $\endgroup$
    – Giorgos Giapitzakis
    Feb 15 at 15:41
  • $\begingroup$ 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> $\endgroup$
    – JaZZyCooL
    Feb 15 at 15:48
  • 1
    $\begingroup$ I see that makes a lot of sense thank you :) $\endgroup$
    – JaZZyCooL
    Feb 15 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.