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$ Apr 2 '20 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
    Apr 2 '20 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
    Apr 2 '20 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$ Apr 2 '20 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
    Apr 2 '20 at 22:20

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
    Apr 3 '20 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$ Apr 3 '20 at 3:54
  • $\begingroup$ thank you! wish i could accept it twice :) $\endgroup$
    – neutrino
    Apr 3 '20 at 4:08
  • $\begingroup$ Happy to help :-) $\endgroup$ Apr 3 '20 at 4:27
  • $\begingroup$ also, −|0sub1⟩⊗|f~(0sub2)⟩ get simplified into f~(0sub2)⟩ because 0 state times 0 state = 0 state? $\endgroup$
    – neutrino
    Apr 4 '20 at 3:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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