The impossibillity of evaluating a function at two inputs with a single query

Consider functions of the form $f : \{0,1\}\to\{0,1\}$, and a query oracle for such a function given as a unitary operator $U_f$ defined as $\ket{a,b}\mapsto\ket{a,b\oplus f(a)}$ for $a,b\in\{0,1\}$. In an attempt to obtain information about the values $f(0)$ and $f(1)$, assume the methods use only two qubits and can be expressed as a circuit of the form



where $V$ and $W$ are two-qubit unitaries and the last two gates labelled with $X$ are measurements in the computational basis.

Label the four possible functions under consideration as follows:

\[f_{00}(x) = \left\{
\begin{array}{rl}
0,& x=0 \\
0,&x=1
\end{array}\right.;\]
\[f_{01}(x) = \left\{
\begin{array}{rl}
0,& x=0 \\
1,&x=1
\end{array}\right.;\]

\[f_{10}(x) = \left\{
\begin{array}{rl}
1,& x=0 \\
0,&x=1
\end{array}\right.;\]
\[f_{11}(x) = \left\{
\begin{array}{rl}
1,& x=0 \\
1,&x=1
\end{array}\right..\]

Let $\ket{\psi}=\alpha_{00}\ket{00}+\alpha_{01}\ket{01}+\alpha_{10}\ket{10}+\alpha_{11}\ket{11}$, where
\[|\alpha_{00}|^2+|\alpha_{01}|^2+|\alpha_{10}|^2+|\alpha_{11}|^2=1,\]
be the general form of the state that results after the $V$ gate is applied in the circuit. For each of the four functions, the states that results after the query gate $U_{f_{ij}}$ is applied to $\ket{\psi}$ are given by:

\[
\begin{align*}
 \ket{\psi_{00}}:=U_{f_{00}}\ket{\psi}&=\alpha_{00}\ket{0,0\oplus f_{00}(0)}+\alpha_{01}\ket{0,1\oplus f_{00}(0)}+\alpha_{10}\ket{1,0\oplus f_{00}(1)}+\alpha_{11}\ket{1,1\oplus f_{00}(1)} \\
 &=\alpha_{00}\ket{00}+\alpha_{01}\ket{01}+\alpha_{10}\ket{10}+\alpha_{11}\ket{11}, \\
 \\
  \ket{\psi_{01}}:=U_{f_{01}}\ket{\psi}&=\alpha_{00}\ket{0,0\oplus f_{01}(0)}+\alpha_{01}\ket{0,1\oplus f_{01}(0)}+\alpha_{10}\ket{1,0\oplus f_{01}(1)}+\alpha_{11}\ket{1,1\oplus f_{01}(1)} \\
 &=\alpha_{00}\ket{00}+\alpha_{01}\ket{01}+\alpha_{11}\ket{10}+\alpha_{10}\ket{11}, \\
 \\
  \ket{\psi_{10}}:=U_{f_{10}}\ket{\psi}&=\alpha_{00}\ket{0,0\oplus f_{10}(0)}+\alpha_{01}\ket{0,1\oplus f_{10}(0)}+\alpha_{10}\ket{1,0\oplus f_{10}(1)}+\alpha_{11}\ket{1,1\oplus f_{10}(1)} \\
 &=\alpha_{01}\ket{00}+\alpha_{00}\ket{01}+\alpha_{10}\ket{10}+\alpha_{11}\ket{11}, \\
 \\
  \ket{\psi_{11}}:=U_{f_{11}}\ket{\psi}&=\alpha_{00}\ket{0,0\oplus f_{11}(0)}+\alpha_{01}\ket{0,1\oplus f_{11}(0)}+\alpha_{10}\ket{1,0\oplus f_{11}(1)}+\alpha_{11}\ket{1,1\oplus f_{11}(1)} \\
 &=\alpha_{01}\ket{00}+\alpha_{00}\ket{01}+\alpha_{11}\ket{10}+\alpha_{10}\ket{11}, \\
 \end{align*}
\]

For any measurement to be able to distinguish the four states $\ket{\psi_{ij}}$ it must be the case that the states $\ket{\psi_{ij}}$ are mutually orthogonal. The unitary gate $W$ would then serve the purpose of rotating these states into the four computational basis states, which would then be distinguished by the measurements made on the two qubits. Observe that the four functions satisfy the properties that $f_{00}(0)=f_{01}(0)=0$ and $f_{10}(0)=f_{11}(0)=1$. Therefore, in order for a measurement to be able to determine the value of $f_{ij}(0)$, the following orthogonality constraints must hold:
\[
\ip{\psi_{00}}{\psi_{10}}=0 \ \text{and} \ \ip{\psi_{00}}{\psi_{11}}=0
\]

Computing these inner products with these constraints imposed gives

\[\begin{align*}
\ip{\psi_{00}}{\psi_{10}}=\overline{\alpha_{00}}\alpha_{01}+\overline{\alpha_{01}}\alpha_{00}+\overline{\alpha_{10}}\alpha_{10}+\overline{\alpha_{11}}\alpha_{11}=0,
\\
\ip{\psi_{00}}{\psi_{11}}=\overline{\alpha_{00}}\alpha_{01}+\overline{\alpha_{01}}\alpha_{00}+\overline{\alpha_{10}}\alpha_{11}+\overline{\alpha_{11}}\alpha_{10}=0,
\end{align*}
\]

which implies that
\[
\begin{align*}
&\overline{\alpha_{10}}\alpha_{10}+\overline{\alpha_{11}}\alpha_{11}=\overline{\alpha_{10}}\alpha_{11}+\overline{\alpha_{11}}\alpha_{10}, \\
\implies &(\overline{\alpha_{10}}-\overline{\alpha_{11}})(\alpha_{10}-\alpha_{11})=0, \\
\implies&\alpha_{10}-\alpha_{11}=0,
\end{align*}
\]
so that $\alpha_{10}=\alpha_{11}$.

The orthogonality conditions mentioned in above were chosen so that that the value of $f(0)$ can be determined perfectly. The result of these constraints implied that $\alpha_{10}=\alpha_{11}$. By letting $\alpha=\alpha_{10}=\alpha_{11}$ it is seen that
\[
\begin{align*}
\ket{\psi_{00}}=\alpha_{00}\ket{00}+\alpha_{01}\ket{01}+\alpha\ket{10}+\alpha\ket{11}=\ket{\psi_{01}}, \\
  \ket{\psi_{10}}=\alpha_{01}\ket{00}+\alpha_{00}\ket{01}+\alpha\ket{10}+\alpha\ket{11}=  \ket{\psi_{11}}.
\end{align*}
\]
Thus $\ket{\psi_{00}}$ and $\ket{\psi_{01}}$ are really the same state, and $  \ket{\psi_{10}}$ and $ \ket{\psi_{11}}$ are the same state.

  In an attempt to also determine the value of $f(1)$ observe that $f_{00}(1)=f_{10}(1)=0$ and that $f_{01}(1)=f_{11}(1)=1$. Therefore, in order to be able to determine the value of $f_{ij}(1)$ it must also be the case that $\ip{\psi_{00}}{\psi_{01}}=0$ and $\ip{\psi_{10}}{\psi_{11}}=0$, but since the constraints for determining $f_{ij}(0)$ implied that $\ket{\psi_{00}}=\ket{\psi_{01}}$, it is actually the case that $\ip{\psi_{00}}{\psi_{01}}=1\neq0$. Hence, the orthogonality constraints that must hold in order for both the values of $f_{ij}(0)$ and $f_{ij}(1)$ to hold can not be satisfied simultaneously.
 
  In order to be determine the value of $f_{ij}(1)$ perfectly provided that that value of $f_{ij}(0)$ can be determined perfectly, the states $\ket{\psi_{00}}$, and $\ket{\psi_{01}}$ must be perfectly distinguishable, and also the states $\ket{\psi_{10}}$, and $\ket{\psi_{11}}$ must also be distinguishable. However, since$\ket{\psi_{00}}=\ket{\psi_{01}}$ and $\ket{\psi_{00}}=\ket{\psi_{01}}$ such a distinguishing procedure is impossible, and would only be able to succeed with probability at most $1/2$.

Distinguishing between pairs of quantum states

 In each of the following cases,  we will suppose that one of two single qubit states $\ket{a}$ and $\ket{b}$ is selected randomly with probability $1/2$, but we are not told which. The goal is to guess which state was selected with as high a probability as we can achieve. What will be described is a distinguishing procedure in the form of a unitary operation followed by a measurement in the computational basis, and its success probability.

CASE: (i)

$\ket{a}=\ket{0}$ and $\ket{b}=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$

The inner product of the two states $\ket{a}$ and $\ket{b}$ is:
\[\ip{a}{b}=\bra{0}\super{\ket{0}+\ket{1}}=\frac{1}{\sqrt{2}}(\ip{0}{0}+\ip{0}{1})=\frac{1}{\sqrt{2}},\]
since $\ip{i}{j}=\delta_{ij}$ for all $i,j\in\{0,1\}$. Then using the geometrical relation $\ip{a}{b}=\cos{\phi}$, where $\phi\in[0,2\pi)$ denotes the angle between the two states $\ket{a}$ and $\ket{b}$, it is seen that in this case
\[\phi=\arccos{\frac{1}{\sqrt{2}}}=\frac{\pi}{4}.\]
In general, two pure states can only be perfectly distinguished if they are orthogonal. That is, if $\phi=\frac{\pi}{2},\frac{3\pi}{2}$. Therefore, in this case the two states $\ket{a}$ and $\ket{b}$ cannot be perfectly distinguished.

Consider the unitary operation $R$ that rotates states by $\theta=\frac{\pi}{8}$ given by:
\[
R=\begin{pmatrix}
\cos{\frac{\pi}{8}}&-\sin{\frac{\pi}{8}} \\
\sin{\frac{\pi}{8}}&\cos{\frac{\pi}{8}}
\end{pmatrix}
\]
Then applying $R$ to the two computational basis states $\ket{0}$ and $\ket{1}$ gives:
\[\begin{array}{rcl}
R\ket{0}&=&\cos{\frac{\pi}{8}}\ket{0}+\sin{\frac{\pi}{8}}\ket{1}\\
R\ket{1}&=&-\sin{\frac{\pi}{8}}\ket{0}+\cos{\frac{\pi}{8}}\ket{1}
\end{array}\]

Therefore, applying $R$ to the states $\ket{a}$ and $\ket{b}$ yields:
\[\begin{array}{rcl}
R\ket{a}=R\ket{0}&=&\cos{\frac{\pi}{8}}\ket{0}+\sin{\frac{\pi}{8}}\ket{1},\\
R\ket{b}=\frac{1}{\sqrt{2}}R(\ket{0}+\ket{1})
&=&\frac{1}{\sqrt{2}}(\cos{\frac{\pi}{8}}\ket{0}+\sin{\frac{\pi}{8}}\ket{1}-\sin{\frac{\pi}{8}}\ket{0}+\cos{\frac{\pi}{8}}\ket{1})\\
&=&\frac{1}{\sqrt{2}}((\cos{\frac{\pi}{8}}-\sin{\frac{\pi}{8}})\ket{0}+(\cos{\frac{\pi}{8}}+\sin{\frac{\pi}{8}})\ket{1})
\end{array}\]
Since $R$ is unitary the inner product of $R\ket{a}$ and $R\ket{b}$ is preserved, and also the angle $\phi=\frac{\pi}{4}$ between the states is preserved.

 When either $R\ket{a}$ or $R\ket{b}$ are measured in the computational basis what will result is one of the basis states $\ket{0}$ or $\ket{1}$, but with certain probability. If the state happened to be $R\ket{a}$, then the probability of observing $\ket{0}$ and $\ket{1}$ is $\cos^2{\frac{\pi}{8}}$ and $\sin^2{\frac{\pi}{8}}$, respectively. If instead the state $R\ket{b}$ was measured, the probability of observing $\ket{0}$ would be $\sin^2{\frac{\pi}{8}}$, and the probability of observing $\ket{1}$ would be $\cos^2{\frac{\pi}{8}}$.

 Thus when either $\ket{a}$ or $\ket{b}$ is given uniformly at random, first apply $R$ to the state and then measure. If $\ket{0}$ is observed guess the state $\ket{a}=\ket{0}$, and if the state $\ket{b}$ is observed guess the state $\ket{b}=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$.

 The probability of guessing the state correctly is given by $\frac{1}{2}(1+\sin{\phi})$, where $\phi=\arccos({\ip{a}{b}})$ is the angle between the states. In this case, with $\phi=\frac{\pi}{4}$, the probability of successfully guessing the correct state is $\frac{1}{2}(1+\sin{\frac{\pi}{4}})\approx .50$.



Case: (ii)

 $\ket{a}=\super{\ket{0}+i\ket{1}}$ and $\ket{b}=\super{i\ket{0}+\ket{1}}$

Consider the inner product between $\ket{a}$ and $\ket{b}$:
\[\ip{a}{b}=(\super{\bra{0}-i\bra{1}})(\super{i\ket{0}+\ket{1}})=\frac{1}{2}(i\ip{0}{0}+\ip{0}{1}+\ip{1}{0}-i\ip{1}{1})=\frac{i}{2}-\frac{i}{2}=0\]
Hence, the two states are orthogonal so the angle between them is $\phi=\frac{\pi}{2}$. There must exist a unitary transformation $U$ that maps these two states to the computational basis states $\ket{0}$ and $\ket{1}$. Consider the following unitary map:
\[
U=\frac{1}{\sqrt{2}}\begin{pmatrix}
1&-i \\
i&-1\end{pmatrix},\]
and observe that
\[
U\ket{a}=\frac{1}{\sqrt{2}}\begin{pmatrix}
1&-i \\
i&-1\end{pmatrix}
\begin{pmatrix}
\frac{1}{\sqrt{2}}\\
\frac{i}{\sqrt{2}}
\end{pmatrix}=
\begin{pmatrix}
1\\
0
\end{pmatrix},\]
\[U\ket{b}=\frac{1}{\sqrt{2}}\begin{pmatrix}
1&-i \\
i&-1\end{pmatrix}
\begin{pmatrix}
\frac{i}{\sqrt{2}}\\
\frac{1}{\sqrt{2}}
\end{pmatrix}=
\begin{pmatrix}
0\\
1
\end{pmatrix},
\]
Then by applying the unitary operation $U$ to either of the states $\ket{a}$ or $\ket{b}$ chosen uniformly at random, and then measuring in the computational basis, either the state $\ket{0}$ or $\ket{1}$ will be observed with certainty. If $\ket{0}$ is observed, then the original state was $\ket{a}=\super{\ket{0}+i\ket{1}}$. Otherwise, if the state $\ket{1}$ was observed, then the original state was $\ket{b}=\super{i\ket{0}+\ket{1}}$. Since these states are orthogonal, the probability of success with the procedure is $1$.



Case: (iii)
$\ket{a}=\cos\theta\ket{0}+\sin\theta\ket{1}$ and $\ket{b}=\cos\theta\ket{0}-\sin\theta\ket{1}$, where $\theta\in[0,2\pi)$ is known.

The inner product of the states $\ket{a}$ and $\ket{b}$ is given by:
\[\begin{array}{rcl}\ip{a}{b}&=&(\cos\theta\bra{0}+\sin\theta\bra{1})(\cos\theta\ket{0}-\sin\theta\ket{1})\\
&=&\cos^2{\theta}\ip{0}{0}+\cos{\theta}\sin{\theta}\ip{0}{1}-(\sin{\theta}\cos{\theta}\ip{1}{0}+\sin^2{\theta}\ip{1}{1} \\
&=&\cos^2{\theta}-\sin^2{\theta} \\
&=&\cos{2\theta}
\end{array}\]

Therefore the angle between the two states is $\phi=2\theta$. If $\theta=0$, then $\phi=2\theta=0$ and the states are actually the same. In this case, there is no improved way of distinguishing between the two states besides merely guessing with a $50/50$ chance. Otherwise, consider the unitary operator $R$ that performs a rotation by $\pi/4$:
\[R=\begin{pmatrix}\cos{\frac{\pi}{4}}&-\sin{\frac{\pi}{4}} \\
\sin{\frac{\pi}{4}}&\cos{\frac{\pi}{4}}
\end{pmatrix}\]

Geometrical considerations show that applying $R$ to the states $\ket{a}$ and $\ket{b}$ yields:
\[\begin{array}{rcl}R\ket{a}&=&\cos{(\theta-\pi/4)}\ket{0}+\sin{(\theta-\pi/4)}\ket{1},\\
R\ket{b}&=&\cos{(\theta+\pi/4)}\ket{0}+\sin{(\theta+\pi/4)}\ket{1}.
\end{array}\]
Then if $R\ket{a}$ is measured in the computation basis,$\ket{0} $will be observed with probability $\cos^2{(\theta-\pi/4)}$ and $\ket{1}$ will be observed with probability $\sin^2{(\theta-\pi/4)}$. On the other hand, if the state $R\ket{b}$ is measured, the states $\ket{0}$ and $\ket{1}$ will be observed with probability $\cos^2{(\theta+\pi/4)}$ and $\sin^2{(\theta+\pi/4)}$, respectively.

Therefore, for $0\leq\theta\leq\pi/2$ or $\pi\leq\theta\leq3\pi/2$, if the state $\ket{0}$ is observed, guess that the original state was $\ket{a}$. For $\pi/2\leq\theta\leq\pi/2$ or $3\pi/2\leq\theta\leq2\pi$, if $\ket{1}$ is observed, then guess that the original state was $\ket{b}$. This method has a probability of success given by $P=\frac{1}{2}(1+\sin{(2\theta)})$.