I am currently working on the algorithm of Deutsch. The algorithm defines two starting states, which are for $|x\rangle = |0\rangle$ and for $|y\rangle = |1\rangle$. So far, that's clear to me. But what would happen if you change the input bits, lets say the qubits are initially in the state: $|x\rangle = |0\rangle$ and $ |y\rangle = |0\rangle$, what are the implications for the algorithm? And what would happen, if the bits in the original algorithm were switched: $|x\rangle = |1\rangle$ and for $|y\rangle = |0\rangle$ does the last idea just switch the last bit in the final states?

Suppose the input bits are 0 and 0 (according to my calculation): I apply the H matrix to both input bits: $$ H(|0\rangle)H(|0\rangle)=|+\rangle\cdot|+\rangle$$ $$=\frac{1}{2}(|00\rangle+|01\rangle+|10\rangle+|11\rangle)$$ By $f'$ I mean the negation of $f$ $$\frac{1}{2}(|0,f(0)\rangle+|0,f'(0)\rangle+|1,f(1)\rangle+|1,f'(1)\rangle))$$ Now let's say $ f (0) = f (1) $ (constant) then: $$\frac{1}{2}((|0\rangle+|1\rangle)(|f(0)\rangle+|f'(0)\rangle))$$ But what would happen if $ f (0) = f '(1)$ (balanced)?

I hope that my question has come across as understandable.


TL;DR: You won't be able to distinguish the constant and balanced function scenarios if you start with $|y\rangle = |0\rangle$.

If you start with $|x\rangle = |0\rangle$ and $|y\rangle = |0\rangle$:

For a balanced function $ f (0) = f '(1)$ you'll get

$$\frac{1}{2}(|0,f(0)\rangle+|0,f'(0)\rangle+|1,f(1)\rangle+|1,f'(1)\rangle)) = $$

$$= \frac{1}{2}(|0,f(0)\rangle+|0,f'(0)\rangle+|1,f'(0)\rangle+|1,f(0)\rangle)) = $$

$$= \frac{1}{2}((|0\rangle+|1\rangle)(|f(0)\rangle+|f'(0)\rangle))$$

Which is the same result as you'd get for a constant function. That's why you need to start with $|y\rangle = |1\rangle$ - you need to get a phase difference between the two scenarios somehow.

If you start with $|x\rangle = |1\rangle$ and $|y\rangle = |0\rangle$, you get the same outcome: the state both for balanced and for constant scenarios is the same, and you can't distinguish them. (The math is very straightforward so I won't write it out here).

  • $\begingroup$ Thanks for your answer, that helped me a lot. I had almost thought of what you wrote, thank you for confirming that. I have now calculated it for all possible inputs (possible refers to 2 bits). For the input $|0\rangle|0\rangle$ or $|1\rangle|0\rangle$ the algorithm does not work, but interestingly for $|1\rangle|1\rangle$ and (as in the original) $|0\rangle|1\rangle$. Can you confirm that as well? $\endgroup$ – QuantaMag Jan 15 at 16:41
  • $\begingroup$ I haven't done the math, but it should work, since the phase comes from y and not from x. $\endgroup$ – Mariia Mykhailova Jan 15 at 16:59

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.