Inputting superpositions into unitary gates

In what follows, we will consider a few different scenarios where some unitary operator is acted on a superposition of states, and a subsequent measurement is made.

Let $U$ be any $n$-qubit unitary, $\ket{\psi_1}$ and $\ket{\psi_2}$ be orthogonal $n$-qubit states, and $a_1, a_2\in\{0,1\}^n$ such that the following property holds. For each $j\in\{1,2\}$, if $U\ket{\psi_j}$ is measured in the computational basis then the outcome is the  computational basis state  $\ket{a_j}$ with probability $1$. Let $\alpha_1, \alpha_2\in\mathbb{C}$ be such that $|\alpha_1|^2+|\alpha_2|^2=1$.

 These assumptions imply the following constraints on the states $U\ket{\psi_1}$ and
\[
 (\ket{a_1}\bra{a_1}+\ket{a_2}\bra{a_2})U\ket{\psi_j}=\ket{a_j}.
\]
 Therefore, it must be the case that
\[
 U\ket{\psi_1}=\ket{a_1} \ \ \ \text{and} \ \ \ U\ket{\psi_2}=\ket{a_2}.
\]

 Now consider the state $\ket{\psi}=\alpha_1\ket{\psi_1}+\alpha_2\ket{\psi_2}$. Then
 \[\begin{align*}
U \ket{\psi}&=\alpha_1U\ket{\psi_1}+\alpha_2U\ket{\psi_2} \\
&=\alpha_1\ket{a_1}+\alpha_2\ket{a_2}.
 \end{align*}\]
So if $U\ket{\psi}$ is measured in the computational basis, the state $\ket{a_1}$ will be observed with probability
\[\begin{align*}
|\bra{a_1}U \ket{\psi}|^2&=|\alpha_1U\bra{a_1}\ket{\psi_1}+\alpha_2\bra{a_1}U\ket{\psi_2}|^2 \\
&=|\alpha_1\bra{a_1}\ket{a_1}+\alpha_2\bra{a_1}\ket{a_2}|^2 \\
&=|\alpha_1|^2. \\
\end{align*}\]
Likewise, if $U\ket{\psi}$ is measured in the computational basis, the state $\ket{a_2}$ will be observed with probability
\[\begin{align*}
|\bra{a_2}U \ket{\psi}|^2&=|\alpha_1\bra{a_2}U\ket{\psi_1}+\alpha_2\bra{a_2}U\ket{\psi_2}|^2 \\
&=|\alpha_1\bra{a_2}\ket{a_1}+\alpha_2\bra{a_2}\ket{a_2}|^2 \\
&=|\alpha_2|^2.
\end{align*}\]

Now consider a slightly modified scenario. Let $U$ be any $n$-qubit unitary, $\ket{\psi_1}$ and $\ket{\psi_2}$ be orthogonal $n$-qubit states, and $a_1, b_1, a_2, b_2\in\{0,1\}^n$ such that the following property holds. For each $j\in\{1,2\}$, if $U\ket{\psi_j}$ is measured in the computational basis then the outcome is the  computational basis state  the outcome is
\[
\left\{ \begin{array}{ll}
a_j& \ \text{with probability} \ p_j \\
b_j& \ \text{with probability} \ q_j
\end{array},
\right.
\]
where $p_k+q_k=1$. Let $\alpha_1, \alpha_2\in\mathbb{C}$ be such that $|\alpha_1|^2+|\alpha_2|^2=1$.

Here it will be shown by counterexample that it does not necessarily follow that if $U(\alpha_1\ket{\psi_1}+\alpha_2\ket{\psi_2})$ is measured in the computational basis then the outcome is
\[
\left\{
\begin{array}{ll}
a_1& \ \text{with probability} \ p_1|\alpha_1|^2 \\
b_1& \ \text{with probability} \ q_1|\alpha_1|^2 \\
a_2& \ \text{with probability} \ p_2|\alpha_2|^2 \\
b_2& \ \text{with probability} \ q_2|\alpha_2|^2.
\end{array}
\right.
\]

A counter example will now be constructed. Let $\ket{\psi_1}=\ket{+}=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$ and $\ket{\psi_2}=\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$. Then $\ket{\psi_1}$ and $\ket{\psi_2}$ are orthogonal since
\[
\ip{\psi_1}{\psi_2}=\frac{1}{2}(\bra{0}+\bra{1})(\ket{0}-\ket{1})=\frac{1}{2}(\ip{0}{0}-\ip{1}{1})-\frac{1}{2}(1-1)=0.
\]
 Consider the unitary operator (Pauli-$z$) defined as  $Z\ket{0}=\ket{0}$ and $Z\ket{1}=-\ket{1}$. Consequently,
 \[ \begin{align*}
Z\ket{\psi_1}={\sqrt{2}}Z(\ket{0}+\ket{1})={\sqrt{2}}(Z\ket{0}+Z\ket{1})={\sqrt{2}}(\ket{0}-\ket{1})=\ket{\psi_2}, \\
Z\ket{\psi_2}={\sqrt{2}}Z(\ket{0}-\ket{1})={\sqrt{2}}(Z\ket{0}-Z\ket{1})={\sqrt{2}}(\ket{0}+\ket{1})=\ket{\psi_1}.
 \end{align*}\]
 Let $a_1=a_2=0$ and $b_1=b_2=1$, with $p_j=q_j=1/2$ so that $p_j+q_j=1$. Then measuring in the computational basis it is seen that
 \[\begin{align*}
 |\bra{a_1}Z\ket{\psi_1}|^2 &= |\ip{0}{\psi_2}|^2=\left|\frac{1}{\sqrt{2}}\bra{0}(\ket{0}-\ket{1})\right|^2=\frac{1}{2}|\ip{0}{0}-\ip{0}{1}|^2=\frac{1}{2}|1|^2=\frac{1}{2}=p_1 \\
  |\bra{a_2}Z\ket{\psi_2}|^2 &= |\ip{0}{\psi_1}|^2=\left|\frac{1}{\sqrt{2}}\bra{0}(\ket{0}+\ket{1})\right|^2=\frac{1}{2}|\ip{0}{0}+\ip{0}{1}|^2=\frac{1}{2}|1|^2=\frac{1}{2}=p_2 \\
   |\bra{b_1}Z\ket{\psi_1}|^2 &= |\ip{1}{\psi_2}|^2=\left|\frac{1}{\sqrt{2}}\bra{1}(\ket{0}-\ket{1})\right|^2=\frac{1}{2}|\ip{1}{0}-\ip{1}{1}|^2=\frac{1}{2}|-1|^2=\frac{1}{2}=q_1 \\
  |\bra{b_2}Z\ket{\psi_2}|^2 &= |\ip{1}{\psi_1}|^2=\left|\frac{1}{\sqrt{2}}\bra{1}(\ket{0}+\ket{1})\right|^2=\frac{1}{2}|\ip{1}{0}+\ip{1}{1}|^2=\frac{1}{2}|1|^2=\frac{1}{2}=q_2
 \end{align*}\]
 It has just been shown that this construction satisfies all the assumptions of the problem statement.

 Now let $\alpha_1=\alpha_2=\frac{1}{\sqrt{2}}$ be such that $|\alpha_1|^2+|\alpha_2|^2=1$, and consider the state
\[
  \ket{\psi}=\alpha_1\ket{\psi_1}+\alpha_2\ket{\psi_2}=\frac{1}{2}(\ket{0}+\ket{1})+\frac{1}{2}(\ket{0}-\ket{1})=\ket{0}.
\]
 Then $Z\ket{\psi}=Z\ket{0}$, which implies that
\[
 \bra{a_1}Z\ket{\psi}=\ip{0}{0}=1.
\]
 Therefore, the state is observed with probability $1$ and not with probability $p_1|\alpha_1|^2=\frac{1}{2}|\frac{1}{\sqrt{2}}|^2=\frac{1}{4}$ as it is falsely claimed. This discrepancy is sufficient to  say that the statement cannot hold in general.


Now, one final scenario will be analyzed. Let $W$ denote a generalized $n$-qubit controlled-$U$ gate (i.e. for all $x,y\in \{0,1\}^n$, $W\ket{x}\ket{y}=\ket{x}U^x\ket{y}$ and let $\ket{\psi_1}, \ket{\psi_2}$ be two orthogonal eigenvectors of $U$. Let $V$ be any $n$-qubit unitary. Also, let $\ket{\phi}$ ne any $n$-qubit initial state for the control qubits of $W$. Suppose that the following property holds. For each $j\in\{1,2\}$, if the first register of $(V\otimes I)W\ket{\phi}\ket{\psi_j}$ is measured in the computational basis then the outcome is $a_j$ with probability $p_j$, and $b_j$ with probability $q_j$. 

 Express $\ket{\phi}$ in the general form
\[
 \ket{\phi}=\SUM{x=0}{2^n-1}\beta_x\ket{x} \ \text{with} \ \SUM{x=0}{2^n-1}|\beta_x|^2=1,
\]
 and let
\[
 U\ket{\psi_j}=e_j\ket{\psi_j} \ \text{which implies} \  U^x\ket{\psi_j}=e_j^x\ket{\psi_j},
\]
 where $e_j$ is the eigenvalue of the state $\ket{\psi}$.

 Then
\[ \begin{align*}
 (V\otimes I)W\ket{\phi}\ket{\psi_j}&=(V\otimes I)W\SUM{x=0}{2^n-1}\beta_x\ket{x}\ket{\psi_j} \\
 &=(V\otimes I)\SUM{x=0}{2^n-1}W\beta_x\ket{x}\ket{\psi_j} \\
 &=\SUM{x=0}{2^n-1}\beta_xV\ket{x}U^x\ket{\psi_j} \\
  &=\SUM{x=0}{2^n-1}\beta_xV\ket{x}e^x_j\ket{\psi_j} \\
    &=\SUM{x=0}{2^n-1}\beta_xe^x_jV\ket{x}\ket{\psi_j} .
 \end{align*}\]
 Now let
\[
 \ket{S_j}:=\SUM{x=0}{2^n-1}\beta_xe^x_jV\ket{x},
\]
 and consider measuring subject to the constraints imposed by the assumptions described above:
\[
 (\ket{a_j}\bra{a_j}\otimes I)\ket{S_j}=\delta_j\ket{a_j} \\
 (\ket{b_j}\bra{b_j}\otimes I)\ket{S_j}=\gamma_j\ket{b_j},
\]
 where $\delta_j,\gamma_j\in \mathbb{C}$ such that $|\delta_j|^2=p_j$ and $|\gamma_j|^2=q_j$. Hence the states $\ket{S_j}$ are given as
\[
 \ket{S_j}=\delta_j\ket{a_j}+\gamma_j\ket{b_j}.
\]

 Now consider the following:
 \[ \begin{align*}
 (V\otimes I)W\ket{\phi}(\alpha_1\ket{\psi_1}_+\alpha_2\ket{\psi_j})&=(V\otimes I)W\SUM{x=0}{2^n-1}\beta_x\ket{x}(\alpha_1\ket{\psi_1}_+\alpha_2\ket{\psi_j})\\
 &=(V\otimes I)\SUM{x=0}{2^n-1}W\beta_x\ket{x}(\alpha_1\ket{\psi_1}_+\alpha_2\ket{\psi_j}) \\
 &=\SUM{x=0}{2^n-1}\beta_xV\ket{x}U^x(\alpha_1\ket{\psi_1}_+\alpha_2\ket{\psi_j}) \\
  &=\SUM{x=0}{2^n-1}\beta_xV\ket{x}(\alpha_1U^x\ket{\psi_1}_+\alpha_2U^x\ket{\psi_j}) \\
  &=\SUM{x=0}{2^n-1}\beta_xV\ket{x}(\alpha_1e_1^x\ket{\psi_1}_+\alpha_2e_2^x\ket{\psi_j}) \\
    &=\alpha_1\SUM{x=0}{2^n-1}\beta_xe^x_1V\ket{x}\ket{\psi_1} +\alpha_2\SUM{x=0}{2^n-1}\beta_xe^x_2V\ket{x}\ket{\psi_2}\\
        &=\alpha_1\ket{S_1}\ket{\psi_1} +\alpha_2\ket{S_2}\ket{\psi_2} \\
        &=\alpha_1( \delta_1\ket{a_1}+\gamma_1\ket{b_1})\ket{\psi_1} +\alpha_2( \delta_2\ket{a_2}+\gamma_2\ket{b_2})\ket{\psi_2} \\
        &=:\ket{\Omega}.
 \end{align*}\]
 Now consider the following measurement outcomes for the state $\ket{\Omega}$:
\[ \begin{align*}
 &(\ket{a_j}\bra{a_j}\otimes I)\ket{\Omega}=\\
 &\alpha_1( \delta_1\ket{a_j}\bra{a_j}\ket{a_1}+\gamma_1\ket{a_j}\bra{a_j}\ket{b_1})\ket{\psi_1} +\alpha_2( \delta_2\ket{a_j}\bra{a_j}\ket{a_2}+\gamma_2\ket{a_j}\bra{a_j}\ket{b_2})\ket{\psi_2}=\alpha_j\delta_j\ket{a_j}\ket{\psi_j}\\
 \\
  &(\ket{b_j}\bra{b_j}\otimes I)\ket{\Omega}=\\
 &\alpha_1( \delta_1\ket{b_j}\bra{b_j}\ket{a_1}+\gamma_1\ket{b_j}\bra{b_j}\ket{b_1})\ket{\psi_1} +\alpha_2( \delta_2\ket{b_j}\bra{b_j}\ket{a_2}+\gamma_2\ket{b_j}\bra{b_j}\ket{b_2})\ket{\psi_2}=\alpha_j\gamma_j\ket{b_j}\ket{\psi_j}
 \end{align*}\]
 Recalling that $|\delta_j|^2=p_j$ and $|\gamma_j|^2=q_j$ as shown above, this yields the probability distribution given as
\[
 \left\{
 \begin{array}{ll}
 a_1 \ \text{with probability} \ p_1|\alpha_1|^2 \\
 b_1 \ \text{with probability} \ q_1|\alpha_1|^2 \\
 a_2 \ \text{with probability} \ p_2|\alpha_2|^2 \\
 b_1 \ \text{with probability} \ q_2|\alpha_2|^2.
 \end{array}
 \right.
\]