The density matrix is in the eye of the beholder

Consider the following scenario. Alice first flips a biased coin that has outcome $0$ with probability $\cos^2(\pi/8)$ and $1$ with probability $\sin^2(\pi/8)$. If the coin value is $0$ she creates the state $\ket{0}$ and if the coin value is $1$ she creates the state $\ket{1}$. Then Alice sends the state that she created to Bob, but does not send the coin value.

From Alice's perspective (who knows the coin value), the density matrix of the state she created will be either
\[
\rho_A^0=\ket{0}\bra{0}=\begin{pmatrix} 1 &0 \\ 0 & 0 \end{pmatrix} \ \ \ \text{or} \ \ \ \rho_A^1=\ket{1}\bra{1}=\begin{pmatrix} 0 &0 \\ 0 & 1 \end{pmatrix}.
\]
 What is the density matrix of the state from Bob's perspective (who does not know the coin value)?

 Assuming that Bob at least knows that the biased coin results in outcome $0$ with probability $\cos^2(\pi/8)$ and $1$ with probability $\sin^2(\pi/8)$, and also that Alice sends him either the state $\ket{0}\bra{0}$ or the state $\ket{1}\bra{1}$ depending on whether or not the coin value was $0$ or $1$, respectively, then Bob's density matrix $\rho_B$ will be given as the statistical mixture of the two cases:
\[\begin{align*}
 \rho_B=&\cos^2(\pi/8)\ket{0}\bra{0}+\sin^2(\pi/8)\ket{0}\bra{0} \\
 =&\cos^2(\pi/8)\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}+\sin^2(\pi/8)\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}  \\
 =&\begin{pmatrix} \cos^2(\pi/8) & 0 \\ 0 &\sin^2(\pi/8) \end{pmatrix}.
\end{align*}\]

Suppose that, upon receiving the state from Alice, Bob measures it in the computational basis. The measurement process yields a classical bit and an output state $\ket{0}$ or $\ket{1}$. Will Bob's density matrix for the state (with Bob knowing the classical measurement outcome) be the same as Alice's?

 When Bob measures his density matrix $\rho_B$ the resulting density matrix will either be
\[ \begin{align*}
 \rho_B^0=\ket{0}\bra{0} = \rho_A^0 \ \ \ &\text{if Alice flipped} \  0, \\
 \rho_B^1=\ket{1}\bra{1} = \rho_A^1 \ \ \ &\text{if Alice flipped}  \ 1.
 \end{align*}\]

 In either case, Bob's resulting density matrix, $\rho_B^0$ or $\rho_B^1$, after the measurement is the same as Alice's density matrix, $\rho_B^0$ or $\rho_B^1$, depending on the coin value Alice flipped in the original state's construction.

 Suppose that we modify the above scenario to one where Alice flips a fair coin (where outcomes $0$ and $1$ occur with probability $1/2$ each) and if the coin value is $0$ she creates the state $\ket{\psi_0}=\cos(\pi/8)\ket{0}+\sin(\pi/8)\ket{1}$ and if the coin value is $1$ she creates the state $\ket{\psi_1}=\cos(\pi/8)\ket{0}+\sin(\pi/8)\ket{1}$. Alice send the state (but not the coin value) to Bob.

From Alice's perspective (who knows the coin value), the density matrix of the state she created will be either $\rho_A^0= \ket{\psi_0}\bra{\psi_0}$ or  $\rho_A^1\ket{\psi_1}\bra{\psi_1}$ , where \[\begin{align*}
\rho_A^0=&(\cos(\pi/8)\ket{0}+\sin(\pi/8)\ket{1})(\cos(\pi/8)\bra{0}+\sin(\pi/8)\bra{1}) \\
 =&\cos^2(\pi/8)\ket{0}\bra{0}+\cos(\pi/8)\sin(\pi/8)\ket{0}\bra{1}+\cos(\pi/8)\sin(\pi/8)\ket{1}\bra{0}+\sin^2(\pi/8)\ket{1}\bra{1} \\
 =&\cos^2(\pi/8)\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}+\cos(\pi/8)\sin(\pi/8)\begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}+ \cos(\pi/8)\sin(\pi/8)\begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}+\sin^2(\pi/8)\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}  \\
 =&\begin{pmatrix} \cos^2(\pi/8) & \cos(\pi/8)\sin(\pi/8) \\ \cos(\pi/8)\sin(\pi/8) &\sin^2(\pi/8)\end{pmatrix},
\end{align*}\]
 or
 \[ \begin{align*}
\rho_A^1=&(\cos(\pi/8)\ket{0}-\sin(\pi/8)\ket{1})(\cos(\pi/8)\bra{0}-\sin(\pi/8)\bra{1}) \\
 =&\cos^2(\pi/8)\ket{0}\bra{0}-\cos(\pi/8)\sin(\pi/8)\ket{0}\bra{1}-\cos(\pi/8)\sin(\pi/8)\ket{1}\bra{0}+\sin^2(\pi/8)\ket{1}\bra{1} \\
 =&\cos^2(\pi/8)\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}-\cos(\pi/8)\sin(\pi/8)\begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}- \cos(\pi/8)\sin(\pi/8)\begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}+\sin^2(\pi/8)\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}  \\
 =&\begin{pmatrix} \cos^2(\pi/8) & -\cos(\pi/8)\sin(\pi/8) \\ -\cos(\pi/8)\sin(\pi/8) &\sin^2(\pi/8)\end{pmatrix}.
\end{align*}\]

 Then the density matrix of the state from Bob's perspective $\rho_B$ (who does not know the coin value) will be the statistical mixture
\[ \begin{align*}
 \rho_B=&\frac{1}{2}\rho_A^0+\frac{1}{2}\rho_A^1 \\
 =&\frac{1}{2}\begin{pmatrix} \cos^2(\pi/8) & \cos(\pi/8)\sin(\pi/8) \\ \cos(\pi/8)\sin(\pi/8) &\sin^2(\pi/8)\end{pmatrix}+\frac{1}{2}\begin{pmatrix} \cos^2(\pi/8) & -\cos(\pi/8)\sin(\pi/8) \\ -\cos(\pi/8)\sin(\pi/8) &\sin^2(\pi/8)\end{pmatrix} \\
 =&\begin{pmatrix} \cos^2(\pi/8) & 0 \\ 0 &\sin^2(\pi/8)\end{pmatrix}.
 \end{align*}\]

Suppose that, upon receiving the state from Alice, Bob measures it in the computational basis, yielding a classical bit and an output state $\ket{0}$ or $\ket{1}$. Bob knows the classical bit outcome from his measurement, but does not reveal this to Alice. Will Bob's density matrix for the output state be the same as Alice's.

 If Bob measures his state $\rho_B$, the resulting state will be either
\[ \begin{align*}
 \rho_B^0=\ket{0}\bra{0}, \ \ \ &\text{with probability} \ \cos^2(\pi/8), \\
& \text{or} \\
 \rho_B^1=\ket{1}\bra{1}, \ \ \ &\text{with probability} \ \sin^2(\pi/8).
 \end{align*}\]

 However, if Alice does not learn of the resulting state produced by Bob's  measurement, than her lack of knowledge yields the density matrix $\rho'_A$ consisting of the statistical mixture given by

 \[\begin{align*}
 \rho'_A=&\cos^2(\pi/8)\ket{0}\bra{0} +\sin^2(\pi/8)\ket{1}\bra{1} \\
 &=\begin{pmatrix} \cos^2(\pi/8) & 0 \\ 0 &\sin^2(\pi/8)\end{pmatrix}.
 \end{align*}\]
  Thus, Bob's density matrix is not the same as Alice's regardless of the measurement outcome: $\rho_B^0\neq \rho'_A$ and $\rho_B^1\neq \rho'_A$.

The trace distance between pure states

In this post, the relationship between two distance measures on density operators will be analyzed for a few specific cases. Namely, the trace distance and the Euclidean distance of two pure states will be studied.

The trace norm is defined as $||M||_{Tr}=Tr(\sqrt{M^\dagger M})$, and the trace distance between two density operators $\rho$ and $\sigma$ is given by $||\rho-\sigma||_{Tr}$.

Let's calculate an expression for the trace distance between $\ket{0}$ and $\cos(\theta)\ket{0}+\sin(\theta)\ket{1}$ as a function of $\theta$.

Let
\[
\rho=\ket{0}\bra{0}=\begin{pmatrix} 1&0\\0&0\end{pmatrix}
\]
 and
\[ \begin{align*}
 \sigma&=(\cos(\theta)\ket{0}+\sin(\theta)\ket{1})(\cos(\theta)\bra{0}+\sin(\theta)\bra{1})\\
 \sigma&=\cos^2(\theta)\ket{0}\bra{0}+\cos(\theta)\sin(\theta)\ket{0}\bra{1}+\cos(\theta)\sin(\theta)\ket{1}\bra{0}+\sin^2(\theta)\ket{1}\bra{1} \\
 \sigma&=\begin{pmatrix}\cos^2(\theta)&\cos(\theta)\sin(\theta)\\ \cos(\theta)\sin(\theta)&\sin^2(\theta)
 \end{pmatrix}.
 \end{align*}\]

In this case, since both $\rho$ and $\sigma$ are density operators, they are Hermitian. Thus, $(\rho-\sigma)^\dagger=(\rho-\sigma)$  implying that $(\rho-\sigma)^\dagger(\rho-\sigma)=(\rho-\sigma)^2$. Then
\[
\rho-\sigma=\begin{pmatrix}1-\cos^2(\theta)&-\cos(\theta)\sin(\theta)\\ -\cos(\theta)\sin(\theta)&-\sin^2(\theta)\end{pmatrix}=\begin{pmatrix}\sin^2(\theta)&-\cos(\theta)\sin(\theta)\\ -\cos(\theta)\sin(\theta)&-\sin^2(\theta)\end{pmatrix},
\]
from which it follows that
\[\begin{align*}
(\rho-\sigma)^2&=\begin{pmatrix}\sin^2(\theta)&-\cos(\theta)\sin(\theta)\\ -\cos(\theta)\sin(\theta)&-\sin^2(\theta)\end{pmatrix}\begin{pmatrix}\sin^2(\theta)&-\cos(\theta)\sin(\theta)\\ -\cos(\theta)\sin(\theta)&-\sin^2(\theta)\end{pmatrix}\\
&=\begin{pmatrix}\sin^4(\theta)+\cos^2(\theta)\sin^2(\theta)&-\sin^2(\theta)\cos(\theta)\sin(\theta)+\sin^2(\theta)cos(\theta)\sin(\theta) \\ -\sin^2(\theta)\cos(\theta)\sin(\theta) +\sin^2(\theta)cos(\theta)\sin(\theta)&\sin^4(\theta)+\cos^2(\theta)\sin^2(\theta)\end{pmatrix} \\
&=\begin{pmatrix}
\sin^2(\theta)&0 \\
0&\sin^2(\theta).
\end{pmatrix}
\end{align*}\]
 Thus,
\[
 \sqrt{(\rho-\sigma)^2}=\begin{pmatrix}
\sqrt{\sin^2(\theta)}&0 \\
0&\sqrt{\sin^2(\theta)}\end{pmatrix}
=\begin{pmatrix}
|\sin(\theta)|&0 \\
0&|\sin(\theta)|\end{pmatrix},
\]
and therefore
\[
||(\rho-\sigma)||_{Tr}=Tr\begin{pmatrix}
|\sin(\theta)|&0 \\
0&|\sin(\theta)|\end{pmatrix}=2|\sin(\theta)|.\]

As another example, lets now calculate an expression for the Euclidean distance between the two points in the Bloch sphere that correspond to the pure states $\ket{0}$ and $\cos(\theta)\ket{0}+\sin(\theta)\ket{1}$.

In the Bloch sphere representation, a general density matrix can be expressed as
\[
\frac{1}{2}(I+c_xX+c_yY+c_zZ),
\]
where $X$, $Y$, $Z$ are the Pauli matrices, and the vector $(c_x,c_y,c_z)$ gives the coordinates of the density matrix on the Bloch sphere. In such a representation, $\rho$ and $\sigma$ can be expressed as follows:
\[\begin{align*}
\rho=&\frac{1}{2}(I+Z),\\
\sigma=&\frac{1}{2}(I+2\cos(\theta)\sin(\theta)X+\cos(2\theta)Z),
\end{align*}\]
so that the
coordinate vectors for the Block sphere representations of $\rho$ and $\sigma$ are given by, respectively,
\[\begin{align*}
v_{\rho}=&(0,0,1) \\
v_{\sigma}=&(2\cos(\theta)\sin(\theta),0,\cos(2\theta)).
\end{align*}\]
 Then the Euclidean distance between $\rho$ and $\sigma$ on the Block sphere is given by
 \[\begin{align*}
 ||v_\rho-v_\sigma||_2&=\sqrt{(-2\cos(\theta)\sin(\theta))^2+(1-\cos(2\theta))^2}\\
 &=\sqrt{4\cos^2(\theta)\sin^2(\theta)+4\sin^4(\theta)} \\
 &=\sqrt{4\sin^2(\theta)(\cos^2(\theta)+\sin^2(\theta))}\\
 &=\sqrt{4\sin^2(\theta)}\\
 &=2|\sin(\theta)|.
 \end{align*}\]

 Hence, $||(\rho-\sigma)||_{Tr}=||v_\rho-v_\sigma||_2=2|\sin(\theta)|$, and the two distance measures agree.

Now we'll repeat the calculations done above for these two states: $\rho=\begin{pmatrix} 1/2 &0 \\ 0 & 1/2 \end{pmatrix}$ and the pure state $\cos(\theta)\ket{0}+\sin(\theta)\ket{1}$ as a function of $\theta$.

 As calculatedabove, the density matrix corresponding to the state $\cos(\theta)\ket{0}+\sin(\theta)\ket{1}$ is given by
\[
 \sigma:=\begin{pmatrix}\cos^2(\theta)&\cos(\theta)\sin(\theta)\\ \cos(\theta)\sin(\theta)&\sin^2(\theta)
 \end{pmatrix}
\]

 Calculating the relevant matrices in order to determine the trace distance $||(\rho-\sigma)||_{Tr}=Tr(\sqrt{(\rho-\sigma)^2})$ yields

 \[\begin{align*}
 \rho-\sigma=\begin{pmatrix}\frac{1}{2}-\cos^2(\theta)&\cos(\theta)\sin(\theta)\\ \cos(\theta)\sin(\theta)&\frac{1}{2}-\sin^2(\theta)
 \end{pmatrix},
 \end{align*}\]
 and after some further calculation
\[ \begin{align*}
 (\rho-\sigma)^2&=\begin{pmatrix}\frac{1}{2}-\cos^2(\theta)&\cos(\theta)\sin(\theta)\\ \cos(\theta)\sin(\theta)&\frac{1}{2}-\sin^2(\theta)
 \end{pmatrix}\begin{pmatrix}\frac{1}{2}-\cos^2(\theta)&\cos(\theta)\sin(\theta)\\ \cos(\theta)\sin(\theta)&\frac{1}{2}-\sin^2(\theta)
 \end{pmatrix}\\
 &=\begin{pmatrix}
 \frac{1}{4}&0\\
 0&\frac{1}{4}
 \end{pmatrix},
 \end{align*}\]
 which implies that
\[
 \sqrt{ (\rho-\sigma)^2}=\begin{pmatrix}
\sqrt{ \frac{1}{4}}&0\\
 0&\sqrt{\frac{1}{4}}
 \end{pmatrix}=\begin{pmatrix}
\frac{1}{2}&0\\
 0&\frac{1}{2}
 \end{pmatrix}
\]
 Therefore,
\[
 ||(\rho-\sigma)||_{Tr}=Tr(\sqrt{(\rho-\sigma)^2})=Tr\begin{pmatrix}
\frac{1}{2}&0\\
 0&\frac{1}{2}
 \end{pmatrix}=1
\]
 is the trace distance between the two state $\rho$ and $\sigma$.

 Now, to calculate the Euclidean distance between the two states in the Block sphere representation observe that

\[ \begin{align*}
\rho=&\frac{1}{2}I,\\
\sigma=&\frac{1}{2}(I+2\cos(\theta)\sin(\theta)X+\cos(2\theta)Z),
\end{align*}\]
so that the
coordinate vectors for the Block sphere representations of $\rho$ and $\sigma$ are given by, respectively,
\[\begin{align*}
v_{\rho}=&(0,0,0) \\
v_{\sigma}=&(2\cos(\theta)\sin(\theta),0,\cos(2\theta)).
\end{align*}\]

 The Euclidean distance is then given by
 \[ \begin{align*}
 ||v_\rho-v_\sigma||_2&=\sqrt{(-2\cos(\theta)\sin(\theta))^2+(-\cos(2\theta))^2}\\
 &=\sqrt{4\cos^2(\theta)\sin^2(\theta)+\cos^2(2\theta)} \\
 &=\sqrt{4\cos^2(\theta)\sin^2(\theta)+(\cos^2(\theta)-\sin^2(\theta))^2}\\
 &=\sqrt{2\cos^2(\theta)\sin^2(\theta)+\cos^4(\theta)+\sin^4(\theta))^2}\\
&=\sqrt{2\cos^2(\theta)\sin^2(\theta)+\cos^4(\theta)+\sin^4(\theta))^2}\\
 &=\sqrt{(\cos^2(\theta)+\sin^2(\theta))^2}\\
 &=\sqrt{1^2}\\
 &=1,
 \end{align*}\]
 and so the trace distance of $\rho$ and $\sigma$ agrees with their Euclidean distance on the Block sphere since $||(\rho-\sigma)||_{Tr}=||v_\rho-v_\sigma||_2=1$.

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.
\]

Period inversion

Let $p$ and $q$ be integers greater than $1$, and let $pq$ denote their product. Recall that the quantum Fourier transform modulo $pq$ is the $pq$-dimensional unitary operation defined as
\[
F_{pq}\ket{x}=\frac{1}{\sqrt{pq}}\SUM{y=0}{pq-1}\omega_{pq}^{xy}\ket{y},
\]
for each $x\in\mathbb{Z}_{pq}$, where $\omega_{N}=e^{i2\pi/N}$.

Define two quantum states $\ket{\psi_1}$ and $\ket{\psi_2}$ as
\[
\ket{\psi_1}=\frac{1}{\sqrt{q}}\SUM{x=0}{q-1}\ket{xp} \ \ \ \text{and} \ \ \ \ket{\psi_2}=\frac{1}{\sqrt{p}}\SUM{x=0}{p-1}\ket{xq}.
\]

Then
\[\begin{align*}
F_{pq}\ket{\psi_1}&=\frac{1}{q\sqrt{p}}\SUM{x=0}{q-1}\SUM{y=0}{pq-1}\omega_{pq}^{xpy}\ket{y} \\
&=\frac{1}{q\sqrt{p}}\SUM{y=0}{pq-1}\left(\SUM{x=0}{q-1}\omega_{q}^{xy})\right)\ket{y} \\
&=\frac{1}{q\sqrt{p}}\SUM{n=0}{p-1}\left(\SUM{x=0}{q-1}1\right)\ket{nq} \\
&=\frac{1}{q\sqrt{p}}\SUM{n=0}{p-1}q\ket{nq} \\
&=\frac{1}{\sqrt{p}}\SUM{n=0}{p-1}\ket{nq} \\
&=\ket{\psi_1},
\end{align*}\]
where the third and fourth lines follows from the general fact that
\[\SUM{x=0}{N-1}\omega_{N}^{xy}=\left\{
\begin{array}{ll} N \  &\text{if} \ y=0 (\text{mod} \ N) \\
0 &\text{if} \ y\neq 0 (\text{mod} \ N)
\end{array}
\right.,
\]
and that $y=0 (\text{mod} \ q)$ implies that $y=nq$ for some integer $n$.

Let $s=\{0,1,\dots, p-1\}$, and define $\ket{\psi_3}$ (a ``shifted" version of $\ket{\psi_1}$) as
\[\ket{\psi_3}=\frac{1}{\sqrt{q}}\SUM{x=0}{q-1}\ket{s+xp}.\]

Then
\[\begin{align*}
F_{pq}\ket{\psi_3}&=\frac{1}{q\sqrt{p}}\SUM{x=0}{q-1}\SUM{y=0}{pq-1}\omega_{pq}^{(s+xp)y}\ket{y} \\
&=\frac{1}{q\sqrt{p}}\SUM{x=0}{q-1}\SUM{y=0}{pq-1}\omega_{pq}^{sy}\omega_{pq}^{xpy}\ket{y} \\
&=\frac{1}{q\sqrt{p}}\SUM{y=0}{pq-1}\omega_{pq}^{sy}\SUM{x=0}{q-1}\omega_{q}^{xy}\ket{y} \\
&=\frac{1}{q\sqrt{p}}\SUM{n=0}{p-1}\omega_{pq}^{snq}\SUM{x=0}{q-1}1\ket{nq} \\
&=\frac{1}{q\sqrt{p}}\SUM{n=0}{p-1}\omega_{p}^{sn}q\ket{nq} \\
&=\frac{1}{\sqrt{p}}\SUM{n=0}{p-1}\omega_{pq}^{sn}\ket{nq}.
\end{align*}\]

 Let $\alpha_{y}$ denote the amplitude of the state $\ket{y}$ in the super position described in $F_{pq}\ket{\psi_1}$ just derived. Since any state $\ket{y}\neq\ket{nq}$ for some $n\in\{0,1,\dots,p-1\}$ does not appear in the superposition $F_{pq}\ket{\psi_1}$, this implies that the amplitude $\alpha_y$ for such states is $0$ and will be observed with probability $0$. On the contrary, for any state $\ket{y}\neq\ket{nq}$ for some $n\in\{0,1,\dots,p-1\}$, the corresponding amplitude is given by $\alpha_{y}=\frac{1}{\sqrt{p}}\omega_{pq}^{sn}$. Therefore the probability of observing the state $\ket{y}\neq\ket{nq}$ is $|\alpha_y|^2=\frac{1}{\sqrt{p}}\omega_{pq}^{sn}\frac{1}{\sqrt{p}}\overline{\omega}_{pq}^{sn}=\frac{1}{p}$. Hence, if $F_{pq}\ket{\psi_1}$ is measured in the computation basis, only some state $\ket{nq}$ representing an integer multiple of $q$ will be observed with uniform probability of $\frac{1}{p}$.

Simon's problem modulo $m$

Throughout, the following notation and results will be used. Let $\omega_N=e^{i2\pi/N}$. The following sum can be evaluated as so:
\[
\SUM{x=0}{N-1}\omega_N^{xy}
\left\{
\begin{array}{ll}
N \ \ \text{if} \ \ y\equiv0 \ (\text{modulo} \ N) \\
0 \ \ \text{if} \ \ y\equiv0 \ (\text{modulo} \ N).
\end{array}
\right.
\]


 Let $m$ be some $n$-bit number $(2^{n-1}<m<2^m)$ and assume that we are given a black box computing $f : \mathbb{Z}_m\times\mathbb{Z}_m$ that is promised to have the property that $f(a_1, a_2)=f(b_1,b_2)$ if and only if $(a_1,a_2)-(b_1,b_2)\in S$, where $S=\{k(r,1) ; k\in \mathbb{Z}_m\}$ for some unknown $r\in\mathbb{Z}_m$. Let the goal be to compute $r$.

For each $a\in\mathbb{Z}_m$, define $S_a=S+(a,0)=\{(kr+a,k) : k\in\mathbb{Z}_m\}$. It will now be proved that $S_0, S_1, \dots, S_{m-1}$ for a partition of $\mathbb{Z}_m\times\mathbb{Z}_m$.

Here, it will be shown that $a\neq b$ implies that $S_a\cap S_b=\emptyset$, where without loss of generality $a,b\in\mathbb{Z}_m$ are such that $a,b\in\{0,1, \dots, m-1\}$. Moreover, for $x,y\in\mathbb{Z}$, write $x\equiv y$ if $x=y(\text{mod}\ m)$. Thus, assume that $a\neq b$. Consider any $s\in S_a$ so that $s=(kr+a,k)$ for some $k\in\mathbb{Z}_m$. Now suppose for the sake of contradiction that $s\in S_b$ so that $s=(k'r+b,k')$ for some $k'\in\mathbb{Z}_m$. Then $(kr+a, k)=(k'r+b, k')$, which implies that $k\equiv k' \ \text{and} \ kr+a\equiv k'r+b$. Furthermore, since $k\equiv k'$ implies $k-k'\equiv0$, then $kr+a\equiv k'r+a$ implies $a-b\equiv (k-k')r\equiv 0$. This then implies that $a\equiv b$ or that $a=b$ contradicting the original assumption that $a=b$. Thus, for every $s\in S_a$, $s\notin S_b$. By the same reasoning it can similarly be shown that for every $t\in S_b$, $t\notin S_a$. Therefore, if $a\neq b$, then it must be the case that $S_a\cap S_b=\emptyset$

Now it will be shown that $S_0\cup S_1\cup\dots\cup S_{m-1}=\mathbb{Z}_m\times\mathbb{Z}_m$. Since $S_a\subseteq\mathbb{Z}_m\times\mathbb{Z}_m$ for all $a\in\{0,1,\dots, m-1\}$, then if $s\in S_a$, for some $a$, it follows that $s\in\mathbb{Z}_m\times\mathbb{Z}_m$.  Instead, consider an arbitrary $s=(j,k)\in\mathbb{Z}_m\times\mathbb{Z}_m$. Let $c\in\{0,1,\dots, m-1\}$ be such that $c\equiv j-kr$. Observe that  $kr+c\equiv kr+j-kr\equiv j$, and therefore $s=(j,k)=(kr+c,k)\in S_c$. Hence, for any $s\in\mathbb{Z}_m\times\mathbb{Z}_m$ there exists some $S_c$ such that $s\in S_c$. Hence, $S_0\cup S_1\cup\dots\cup S_{m-1}=\mathbb{Z}_m\times\mathbb{Z}_m$.

The results of (i) and (ii) together imply that the sets $S_0, S_1, \dots, S_{m-1}$ form a partition of $\mathbb{Z}_m\times\mathbb{Z_m}$.


Here, we prove that $f(x_1,x_2)=f(y_1,y_2)$ if and only if $(x_1,x_2)$ and $(y_1,y_2)$ are in the same element of the above partition (in other words, $(x_1,x_2),(y_1,y_2)\in S_a$ for some $s$).

First, suppose that $(x_1,x_2),(y_1,y_2)\in S_a$ for some $a$. Then there exists $k,k'\in\mathbb{Z}_m$ such that $(x_1,x_2)=(kr+a, k)$ and $(y_1,y_2)=(k'r+a,k')$. This implies that
\[
\begin{align*}
(x_1,x_2)-(y_1,y_2)&=(kr+a, k)-(k'r+a,k')\\
&=(kr+a-k'r-a,k-k')\\
&=((k-k')r,k-k')\\
&=(k-k')(r,1)\in S.
\end{align*}
\]
Then provided with the promise on $f$, it follows that $f(x_1,x_2)=f(y_1,y_2)$.

Suppose instead that $f(x_1,x_2)=f(y_1,y_2)$. The promise on $f$ then implies that $(x_1,x_2)-(y_1,y_2)\in S$, which means that $(x_1,x_2)-(y_1,y_2)=k(r,1)$ for some $k\in \mathbb{Z}_m$. Since
\[
(x_1,x_2)-(y_1,y_2)=(x_1-y_1,x_2-y_2)=k(r,1)=(kr,k),
\]
this implies that $x_2-y_2=k$. Moreover, since $kr=(x_2-y_2)r=x_1-y_1$ this implies that $x_2r-x_1=y_2r-y_1$. Let $c=x_2r-x_1=y_2r-y_1$. Now note that for any $(z_1,z_2\in S_a$ for some $a$, $(z_1,z_2)=(nr+a,n)$ for some $n$. This is equivalent to the condition $z_1=z_2r+a$. Therefore, since $x_2r-x_1=c$ and $y_2r-y_1=c$, it follows that $x_1=x_2r+c$ and $y_1=y_2r+c$. Hence, $(x_1,x_2),(y_1,y_2)\in S_c$ showing that if $f(x_1,x_2)=f(y_1,y_2)$, $(x_1,x_2)$ and $(y_1,y_2)$ belong to the same set $S_c$.

It has now been shown that $f(x_1,x_2)=f(y_1,y_2)$ if and only if $(x_1,x_2)$ and $(y_1,y_2)$ are in the same element of the above partition.


Consider the state
\[
\ket{\psi}=\frac{1}{m}\displaystyle\sum_{x_1=0}^{m-1}\SUM{x_2=0}{m-1}\ket{x_1}\ket{x_2}\ket{f(x_1,x_2)}.
\]
Since $f(x_1,x_2)=f(y_1,y_2)$ if $(x_1,x_2),(y_1,y_2)\in S_a$ for some $a$. The state $\ket{\psi}$ is an entangled state which can be equivalently expressed as
\[\begin{align*}
\ket{\psi}&=\frac{1}{m}\SUM{a=0}{m-1}\SUM{k=0}{m-1}\ket{kr+a}\ket{k}\ket{f(kr+a,k)}\\
&=\frac{1}{m}\SUM{a=0}{m-1}\SUM{k=0}{m-1}\ket{kr+a}\ket{k}\ket{f_a}.
\end{align*}\]
Here the state of the third register has been labelled with $f_a$, which denotes the value of $f(kr+a,k)$, since this value does not depend on $k$ due to the promise that $f(kr+a,k)=f(k'r+a,k')$ for any $k$ and $k'$.

Then applying the Fourier transform $F_m^\dagger$ to the first two registers yields the state:
\[\begin{align*}
\ket{\overline{\psi}}:=(F_m^\dagger\otimes F_m^\dagger\otimes I)\ket{\psi}&=\frac{1}{m}\SUM{a=0}{m-1}\SUM{k=0}{m-1}F_m^\dagger\ket{kr+a}F_m^\dagger\ket{k}\ket{f_a}\\
&=\frac{1}{m^2}\SUM{a=0}{m-1}\SUM{k=0}{m-1}\SUM{s_1=0}{m-1}\SUM{s_2=0}{m-1}\omega_m^{-(kr+a)s_1}\omega_m^{-ks_2}\ket{s_1}\ket{s_2}\ket{f_a} \\
&=\frac{1}{m^2}\SUM{a=0}{m-1}\SUM{k=0}{m-1}\SUM{s_1=0}{m-1}\SUM{s_2=0}{m-1}\omega_m^{-(kr+a,k)\cdot(s_1,s_2)}\ket{s_1}\ket{s_2}\ket{f_a} \\
&=\frac{1}{m^2}\SUM{a=0}{m-1}\SUM{k=0}{m-1}\SUM{s_1=0}{m-1}\SUM{s_2=0}{m-1}\omega_m^{-k(r,1)\cdot(s_1,s_2)-as_1}\ket{s_1}\ket{s_2}\ket{f_a}
\end{align*}\]

 Now define the sets $R^\perp, R\subseteq \mathbb{Z}_m\times\mathbb{Z}_m$ as
\[\begin{align*}
R^\perp&:=\{(s_1,s_2)\in\mathbb{Z}_m\times\mathbb{Z}_m : (r,1)\cdot(s_1,s_2)=0\} \\
R&:=\{ (s_1,s_2)\in\mathbb{Z}_m\times\mathbb{Z}_m : (r,1)\cdot(s_1,s_2)\neq0\}.
\end{align*}\]
These two sets $R$ and $R^\perp$ partition $\mathbb{Z}_m\times\mathbb{Z}_m$ since for every element $(s_1,s_2)\in\mathbb{Z}_m\times\mathbb{Z}_m$ either $(r,1)\cdot(s_1,s_2)=0$ or $(r,1)\cdot(s_1,s_2)\neq0$. This allows the sum over $s_1$ and $s_2$ in the state for $\ket{\overline{\psi}}$ to be split into two sums. That is,
\[\begin{align*}
\ket{\overline{\psi}}&=\frac{1}{m^2}\SUM{k=0}{m-1}\SUM{a=0}{m-1}\SUM{(s_1,s_2)\in R^\perp}{}\omega_m^{-k(r,1)\cdot(s_1,s_2)-as_1}\ket{s_1}\ket{s_2}\ket{f_a}+\frac{1}{m^2}\SUM{k=0}{m-1}\SUM{a=0}{m-1}\SUM{(s_1,s_2)\in R}{}\omega_m^{-k(r,1)\cdot(s_1,s_2)-as_1}\ket{s_1}\ket{s_2}\ket{f_a}.
\end{align*}\]

Consider just the first summation ranging over$(s_1,s_2)\in R^\perp$ contained in $\ket{\overline{\psi}}$. In this case, $(r,1)\cdot(s_1,s_2)=0$, so the summation becomes
\[\begin{align*}
&\frac{1}{m^2}\SUM{k=0}{m-1}\SUM{a=0}{m-1}\SUM{(s_1,s_2)\in R^\perp}{}\omega_m^{-k(r,1)\cdot(s_1,s_2)-as_1}\ket{s_1}\ket{s_2}\ket{f_a} \\
=&\frac{1}{m^2}\SUM{k=0}{m-1}\SUM{a=0}{m-1}\SUM{(s_1,s_2)\in R^\perp}{}\omega_m^{-as_1}\ket{s_1}\ket{s_2}\ket{f_a} \\
=&\frac{1}{m}\SUM{a=0}{m-1}\SUM{(s_1,s_2)\in R^\perp}{}\omega_m^{-as_1}\ket{s_1}\ket{s_2}\ket{f_a}
\end{align*}\]
Now consider the second summation contained in $\ket{\overline{\psi}}$, which ranges over $(s_1,s_2)\in R$. This implies that $(r,1)\cdot(s_1,s_2)\neq0$, so that
\[\begin{align*}
&\frac{1}{m^2}\SUM{k=0}{m-1}\SUM{a=0}{m-1}\SUM{(s_1,s_2)\in R}{}\omega_m^{-k(r,1)\cdot(s_1,s_2)-\overline{a}s_1}\ket{s_1}\ket{s_2}\ket{f_a}=0,
\end{align*}\]
which implies that no states of the form $\ket{s_1}\ket{s_2}$ where $(s_1,s_2)\in R$ appear in the superposition in $\ket{\overline{\psi}}$. Hence the final state is of the form
\[
 \ket{\overline{\psi}}=\frac{1}{m^2}\SUM{a=0}{m-1}\SUM{(s_1,s_2)\in R^\perp}{}\omega_m^{-as_1}\ket{s_1}\ket{s_2}\ket{f_a},
\]
 and measuring $\ket{\overline{\psi}}$ will yield some state $\ket{s_1}\ket{s_2}$ such that $(s_1,s_2)\in R^\perp$ with probability
\[
\left|\frac{1}{m}\SUM{a=0}{m-1}\omega_m^{-as_1}\right|^2=\frac{1}{m^2}\SUM{a=0}{m-1}|\omega_m^{-as_1}|^2=\frac{1}{m^2}\SUM{a=0}{m-1}|1=\frac{m}{m^2}=\frac{1}{m}.
\]