# Kaye Exercise 6.3.1, Deutsch algorithm modification

This exercise is worded as follows:

In the Deutsch algorithm, when we consider $$U_f$$ as a single-qubit operator $$\hat{U_{f(x)}}$$, $$\frac{|0\rangle - |1\rangle}{\sqrt{2}}$$ is an eigenstate of $$\hat{U_{f(x)}}$$, whose associated eigenvalue gives us the answer to the Deutsch problem. Suppose we were not able to prepare this eigenstate directly. Show that if we instead input $$|0\rangle$$ to the target qubit, and otherwise run the same algorithm, we get an algorithm that gives the correct answer with probability $$\frac{3}{4}$$. Furthermore, show that with probability $$\frac{1}{2}$$ we know for certainty that the algorithm has produced the correct answer.

After a similar analysis to the original one, I was able to come up with the fact that if $$f$$ is constant, we will always measure $$0$$ while if it is balanced, we will measure $$1$$ with probability $$\frac{1}{2}$$. I find the wording of this problem a bit confusing. The only way I can get a probability of $$3/4$$ is by assuming that $$f$$ is equally likely to be constant or balanced and write $$P(\text{correct output}) = P(\text{measure }1|f \text{ constat})P(f \text{ constant}) +P(\text{measure } 1|f \text{ balanced})P(f \text{ balanced})$$ but nowhere in the problem is that assumption present. But if that is not the case then the second part of the question makes no sense. Any input here is appreciated.

PS: In the problem a hint is given which says to write $$|0\rangle$$ in the basis of eigenvectors of $$U_f$$ which I did not really use but I'm adding it here for completeness.

As suggested in the hint, we can rewrite $$|0\rangle$$ in the basis given by eigenstates of $$\hat{U}_f$$: $$|0\rangle = \frac{1}{\sqrt{2}}|+\rangle + \frac{1}{\sqrt{2}}|-\rangle.$$ Then we get: \begin{align*} U_f |+\rangle|0\rangle &= U_f |+\rangle \left(\frac{1}{\sqrt{2}}|+\rangle + \frac{1}{\sqrt{2}}|-\rangle \right) \\ \tag{1} &= \frac{1}{\sqrt{2}}U_f |+\rangle|+\rangle + \frac{1}{\sqrt{2}}U_f |+\rangle|-\rangle. \end{align*} Now, let's examine each term in Eq (1) separately. First, consider the term $$U_f |+\rangle|-\rangle$$. This is the usual Deutsch algorithm which always produces the correct output. Indeed, applying $$H$$ to $$U_f |+\rangle|-\rangle$$ and then measuring the first register will yield $$|0\rangle$$ or $$|1\rangle$$ whenever $$f$$ is constant or balanced, respectively. Therefore, the term $$U_f |+\rangle|-\rangle$$ will always produce the correct output. From the Eq (1), it follows that the probability of ending up with the term that is guaranteed to produce the correct output is $$\left |\frac{1}{\sqrt{2}}\right |^2 = \frac{1}{2}$$. This answers the second part of the question.
Next, let's look at the term $$U_f |+\rangle|+\rangle$$. This term will always yield the same result regardless of what $$f$$ is. Note that: \begin{align*} U_f |+\rangle|+\rangle &= \frac{1}{\sqrt{2}}\left( U_f|0\rangle |+\rangle + U_f|1\rangle |+\rangle \right)\\ &= \frac{1}{\sqrt{2}}\left(|0\rangle |+\rangle + |1\rangle |+\rangle \right)\\ &= |+\rangle |+\rangle. \end{align*} Applying $$H$$ and measuring the first register will always result in $$|0\rangle$$. So, for $$f$$ balanced, this term will always produce incorrect output. By looking at Eq (1), we can see that the probability of ending up with the "partially correct" algorithm $$U_f |+\rangle|+\rangle$$ is also $$\left |\frac{1}{\sqrt{2}}\right |^2 = \frac{1}{2}$$.
We can interpret Eq (1) as a uniform superposition of the correct Deutsch algorithm $$U_f|+\rangle|-\rangle$$ and partially correct Deutsch algorithm $$U_f|+\rangle|+\rangle$$. When performing the measurement, we will end up with an output from one of the two algorithms with probability $$\frac{1}{2}$$.