# How are the two states factored out of Deutsch's circuit?

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)$$

Question:

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?

• 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? – Mariia Mykhailova Apr 2 at 17:43
• 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. – neutrino Apr 2 at 17:49
• and to quickly add, yes, i definitely have searched answers! thanks again for encouraging me to look back at them – neutrino Apr 2 at 17:52
• 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? – Mariia Mykhailova Apr 2 at 21:55
• 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? – neutrino Apr 2 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)$$