After placing the Hadamards on the 2 qubits (both initialized in the $|1\rangle$ state) in the circuit, we are given:

$ |\psi_{b}\rangle = \frac{1}{2}(|0_{1}0_{2}\rangle -|1_{1}0_{2}\rangle -|0_{1}1_{2}\rangle +|1_{1}1_{2}\rangle) $

the above state is run through the f-cnot, and we are given a superposition:

$ |\psi_{c}\rangle = \frac{1}{2}(|0_{1}f(0_{2})\rangle -|1_{1}f(1_{2})\rangle -|0_{1}\tilde f(0_{2})\rangle +|1_{1}\tilde f(1_{2})\rangle ) $.

In order to compute whether the function is balanced or not, we can use some factoring:

If $ f(0)=f(1) $ we can factor out: $ |\psi_{c}\rangle = \frac{1}{2}(|0_{1}\rangle -|1_{1}\rangle)(|f (0_{2})\rangle - |\tilde f (0_{2})\rangle) $

If $ f(0)=\tilde f(1) $ we can factor out: $ |\psi_{c}\rangle = \frac{1}{2}(|0_{1}\rangle +|1_{1}\rangle)(|f (0_{2})\rangle - |\tilde f (0_{2})\rangle) $


How are these two factored-out states for $ f_1 $ and $ \tilde f_1 $, actually pulled out of the original superposition? Like, how are they actually factored?

  • $\begingroup$ What do you mean by "actually factored"? Do you need the step-by-step walkthrough for the math, or something different? Have you checked other questions in the "deutsch-jozsa-algorithm" tag, such as quantumcomputing.stackexchange.com/questions/9838/…, that offer that walkthrough? $\endgroup$ Commented Apr 2, 2020 at 17:43
  • $\begingroup$ haha, yup, i just mean a walkthrough, as you mentioned. I'm having a little trouble following the provided example, could you help to simply walk through the example i provided? I'm sorry, i'm new to this. $\endgroup$
    – neutrino
    Commented Apr 2, 2020 at 17:49
  • $\begingroup$ and to quickly add, yes, i definitely have searched answers! thanks again for encouraging me to look back at them $\endgroup$
    – neutrino
    Commented Apr 2, 2020 at 17:52
  • $\begingroup$ Could you clarify what exactly you're having trouble with? I could just paste the walkthrough from my previous answer but if you're finding something specific unclear in it, it will remain unclear :-) Also, you're starting with qubits in |11> before applying the Hadamards, but the typical Deutsch algorithm starts in |01> - could this contribute to your confusion? $\endgroup$ Commented Apr 2, 2020 at 21:55
  • $\begingroup$ for sure . . . its just the algebra part, ie how from the ψc⟩=1/2(|0f(0)⟩−|1f(1)⟩−|0f~(0)⟩+|1f~(1)⟩) state can we "pull out" (for example, if f(0)=f(1) ) |ψc⟩=1/2(|0⟩−|1⟩)(|f(0)⟩−|f(0)⟩). .. cause there are only half as many terms. is there cancelling out? $\endgroup$
    – neutrino
    Commented Apr 2, 2020 at 22:20

1 Answer 1


Let's see how to get from $ |\psi_{c}\rangle = \frac{1}{2}(|0_{1}f(0_{2})\rangle -|1_{1}f(1_{2})\rangle -|0_{1}\tilde f(0_{2})\rangle +|1_{1}\tilde f(1_{2})\rangle ) $ to the case of $ f(0)=f(1) $:

$$\frac{1}{2}(|0_{1}f(0_{2})\rangle -|1_{1}f(1_{2})\rangle -|0_{1}\tilde f(0_{2})\rangle +|1_{1}\tilde f(1_{2})\rangle ) = \\ = \frac{1}{2}(|0_{1}f(0_{2})\rangle -|1_{1}\color{blue}{f(0_{2})}\rangle -|0_{1}\tilde f(0_{2})\rangle +|1_{1}\color{blue}{\tilde f(0_{2})}\rangle ) = \\ = \frac{1}{2}(|0_{1}\color{blue}{\rangle \otimes |}f(0_{2})\rangle -|1_{1}\color{blue}{\rangle \otimes |}f(0_{2})\rangle -|0_{1}\color{blue}{\rangle \otimes |}\tilde f(0_{2})\rangle +|1_{1}\color{blue}{\rangle \otimes |}\tilde f(0_{2})\rangle ) = \\ = \frac{1}{2}(|0_{1}\rangle \otimes |f(0_{2})\rangle -\color{blue}{|0_{1}\rangle \otimes |\tilde f(0_{2})\rangle-|1_{1}\rangle \otimes |f(0_{2})\rangle} +|1_{1}\rangle \otimes |\tilde f(0_{2})\rangle ) = \\ = \frac{1}{2}\Big(|0_{1}\rangle \otimes \big(|f(0_{2})\rangle - |\tilde f(0_{2})\rangle \big)-|1_{1}\rangle \otimes \big(|f(0_{2})\rangle -|\tilde f(0_{2})\rangle \big) \Big) = \\ = \frac{1}{2} \big(|0_{1}\rangle - |1_{1}\rangle \big) \otimes \big(|f(0_{2})\rangle - |\tilde f(0_{2})\rangle \big) $$

And that's exactly the expression in the question. You can see that the number of terms remains the same if you open all brackets, 4.

  • $\begingroup$ Amazing! and thanks for this thoughtful response. In the first step, how are the f(1sub2) just flipped into f(0sub2)? I think this is where im missing some understanding. $\endgroup$
    – neutrino
    Commented Apr 3, 2020 at 3:43
  • 1
    $\begingroup$ That's because they are equal (f(0) = f(1)). In the other case the not-f(1) will change into f(0) $\endgroup$ Commented Apr 3, 2020 at 3:54
  • $\begingroup$ thank you! wish i could accept it twice :) $\endgroup$
    – neutrino
    Commented Apr 3, 2020 at 4:08
  • $\begingroup$ Happy to help :-) $\endgroup$ Commented Apr 3, 2020 at 4:27
  • $\begingroup$ also, −|0sub1⟩⊗|f~(0sub2)⟩ get simplified into f~(0sub2)⟩ because 0 state times 0 state = 0 state? $\endgroup$
    – neutrino
    Commented Apr 4, 2020 at 3:17

Your Answer

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

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