0

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?

Mariia Mykhailova
  • 9,010
  • 1
  • 12
  • 39
neutrino
  • 351
  • 1
  • 8
  • 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 https://quantumcomputing.stackexchange.com/questions/9838/understanding-steps-in-deutschs-algorithm, that offer that walkthrough? – Mariia Mykhailova Apr 02 '20 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 02 '20 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 02 '20 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 02 '20 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 02 '20 at 22:20

1 Answers1

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.

Mariia Mykhailova
  • 9,010
  • 1
  • 12
  • 39