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$.
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$.