= Solution
{c}
Normalize the second <qubit> as $|-\rangle=(|0\rangle-|1\rangle)/\sqrt2$. Since a <Pauli X gate> changes $|-\rangle$ to $-|-\rangle$, the <Boolean quantum oracle> acts as
$$
U_f|x\rangle|-\rangle=(-1)^{f(x)}|x\rangle|-\rangle.
$$
This <quantum phase kickback> leaves the second <qubit> uncorrelated with the first. Put $b=f(0)\oplus f(1)$: $b=0$ for a <constant function> and $b=1$ for a <balanced Boolean function>. Apart from the irrelevant <global phase> $(-1)^{f(0)}$, the first <qubit> and environment reach
$$
\frac{|0\rangle|e_0\rangle+(-1)^b|1\rangle|e_1\rangle}{\sqrt2}.
$$
The population-preserving interaction commutes with the <quantum oracle> on this answer-register input, so its placement before or after the oracle, between the two <Hadamard gates>, gives the same result. Substitute $\varphi=\pi b$ into <3/b>:
$$
\boxed{P(0\mid b)=\frac{1+(-1)^b v\cos\alpha}{2},\qquad
P(1\mid b)=\frac{1-(-1)^b v\cos\alpha}{2}.}
$$
The printed <Deutsch algorithm> uses the rule \b[zero means <constant function>; one means <balanced Boolean function>]. With that rule, the <Deutsch algorithm with pure dephasing> succeeds for either class with
$$
\boxed{P_{\rm correct}^{\rm printed}=\frac{1+v\cos\alpha}{2}.}
$$
For real nonnegative environment overlap this is $(1+v)/2$, ranging from certainty at $v=1$ to random guessing at $v=0$. For general complex overlap, a coherent shift can invert the printed answer: for example $v=1,\alpha=\pi$ makes the printed rule always wrong. If the overlap is known but the printed <quantum measurement> is retained, choose the better labeling of its outcomes; this gives
$$
\boxed{P_{\rm correct}^{\rm relabeled}=\frac{1+|v\cos\alpha|}{2}.}
$$
There is a further improvement if a known $\alpha$ can be compensated by the <phase gate> $P_{-\alpha}$ before the final <Hadamard gate>. It removes the coherent shift without reversing any actual <quantum decoherence>, and yields
$$
\boxed{P_{\rm correct}^{\rm compensated}=\frac{1+v}{2}.}
$$
This is optimal when only the first <qubit> is accessible, with equal prior <probabilities> for the two classes. Before the final <Hadamard gate>, their <reduced density matrices> are
$$
\rho_b=\frac12\begin{pmatrix}1&(-1)^b\overline c\\(-1)^bc&1\end{pmatrix}.
$$
The difference $\rho_0-\rho_1$ has <eigenvalues> $\pm v$, giving <trace distance> $v$. The <Holevo–Helstrom theorem> therefore bounds the success <probability> by $(1+v)/2$, exactly attained by the compensated procedure. A known phase shift and loss of coherence have different effects: at $v=0$ the two <density matrices> coincide and no measurement on the available <qubit> can reveal the answer.
Back to article page
