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.


1 Answer 1


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$
    – user4961
    Jan 15, 2019 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$ Jan 15, 2019 at 16:59

Your Answer

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