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

Constructing a Toffoli gate out of two-qubit gates

The Toffoli gate (controlled-controlled-NOT) is a 3-qubit gate, and here it will be shown how to implement it with 2-qubit gates. The construction is given by the following quantum circuit.


Here, the unitary gate $V$ is given by
\[
V=\frac{1}{\sqrt{2}}\begin{pmatrix}
\omega & \overline{\omega} \\
\overline{\omega} & \omega
\end{pmatrix}
\]
where $\omega=e^{i\pi/4}$ and $\overline{\omega}=e^{-i\pi/4}$ is the complex conjugate of $\omega$, and thus
\[
V^{\dagger}=V^{-1}=\frac{1}{\sqrt{2}}\begin{pmatrix}
\overline{\omega} & \omega \\
\omega & \overline{\omega}
\end{pmatrix}
\]

 Consider the product of $V$ with itself:
\[
V^2=\frac{1}{2}\begin{pmatrix}
\omega & \overline{\omega} \\
\overline{\omega} & \omega
\end{pmatrix}
\begin{pmatrix}
\omega & \overline{\omega} \\
\overline{\omega} & \omega
\end{pmatrix}=
\frac{1}{2}\begin{pmatrix}
\omega^2+\overline{\omega}^2 & \omega\overline{\omega}+\overline{\omega}\omega \\
\overline{\omega}\omega+\omega\overline{\omega} & \overline{\omega}^2+\omega^2
\end{pmatrix}.
\]

Now
\[\begin{align*}
 \omega^2+\overline{\omega}^2=& e^{i\pi/2}+e^{-i\pi/2}=i-i=0 \\
\overline{\omega}^2+\omega^2=& e^{-i\pi/2}+e^{i\pi/2}=-i+i=0 \\
\omega\overline{\omega}+\overline{\omega}\omega=&e^{i\pi/4}e^{-i\pi/4}+e^{-i\pi/4}e^{i\pi/4}=1+1=2 \\
\overline{\omega}\omega+\omega\overline{\omega}=&e^{-i\pi/4}e^{i\pi/4}+e^{i\pi/4}e^{i\pi/4}=1+1=2,
\end{align*}\]
and therefore
\[
V^2=
\frac{1}{2}\begin{pmatrix}
\omega^2+\overline{\omega}^2 & \omega\overline{\omega}+\overline{\omega}\omega \\
\overline{\omega}\omega+\omega\overline{\omega} & \overline{\omega}^2+\omega^2
\end{pmatrix}=
\frac{1}{2}\begin{pmatrix}
0&2\\
2&0
\end{pmatrix}
=\begin{pmatrix}
0&1\\
1&0
\end{pmatrix}
=X.
\]


 Let $\ket{\psi}=\alpha\ket{0}+\beta\ket{0}$ be an arbitrary 1-qubit state. Note that $VV^{\dagger}=V^{\dagger}V=I$, and that $VV=X$ as shown in (a). Consider how the circuit maps the following states:
\[\begin{align*}
\ket{00}\ket{\psi}&\overset{c_2V_3}\mapsto\ket{00}\ket{\psi}\overset{c_1X_2}\mapsto\ket{00}\ket{\psi}\overset{c_2V^{\dagger}_2}\mapsto\ket{00}\ket{\psi}\overset{c_1X_2}\mapsto\ket{00}\ket{\psi}\overset{c_2V_3}\mapsto\ket{00}\ket{\psi}=\ket{00}\ket{\psi} \\
\ket{01}\ket{\psi}&\overset{c_2V_3}\mapsto\ket{01}V\ket{\psi}\overset{c_1X_2}\mapsto\ket{01}V\ket{\psi}\overset{c_2V^{\dagger}_2}\mapsto\ket{01}V^{\dagger}V\ket{\psi}\overset{c_1X_2}\mapsto\ket{01}V^{\dagger}V\ket{\psi}\overset{c_2V_3}\mapsto\ket{01}V^{\dagger}V\ket{\psi}=\ket{01}\ket{\psi}\\
\ket{10}\ket{\psi}&\overset{c_2V_3}\mapsto\ket{10}\ket{\psi}\overset{c_1X_2}\mapsto\ket{11}\ket{\psi}\overset{c_2V^{\dagger}_2}\mapsto\ket{11}V^{\dagger}\ket{\psi}\overset{c_1X_2}\mapsto\ket{10}V^{\dagger}\ket{\psi}\overset{c_2V_3}\mapsto\ket{10}VV^{\dagger}\ket{\psi}=\ket{10}\ket{\psi} \\
\ket{11}\ket{\psi}&\overset{c_2V_3}\mapsto\ket{11}V\ket{\psi}\overset{c_1X_2}\mapsto\ket{10}V\ket{\psi}\overset{c_2V^{\dagger}_2}\mapsto\ket{10}V\ket{\psi}\overset{c_1X_2}\mapsto\ket{11}\ket{\psi}\overset{c_2V_3}\mapsto\ket{11}VV\ket{\psi}=\ket{11}X\ket{\psi}
\end{align*}
\]

For each of the four mappings calculated in part (b), observe how $\ket{ab}\ket{\psi}$ is mapped in the two cases where $\ket{\psi}$ is either of the basis states $\ket{0}$ or $\ket{1}$. Since the action is trivially $\ket{ab}\ket{\psi}\mapsto\ket{ab}\ket{\psi}$ in all cases where both $ab$ is $11$, it follows that $\ket{ab}\ket{c}\mapsto\ket{ab}\ket{c}$ for all $ab\in\{00,01,10\}$ and $c\in\{0,1\}$. However, in the case where $ab=11$, and $c\in\{0,1\}$ it is seen that
\[\begin{align*}
\ket{11}\ket{0}\mapsto&\ket{11}X\ket{0}=\ket{11}\ket{1},\\
\ket{11}\ket{1}\mapsto&\ket{11}X\ket{1}=\ket{11}\ket{0}.
\end{align*}\]
Therefore, the circuit  leaves the states unchanged unless the first two qubits in the register are in the state $\ket{11}$, in which case the third qubit in the register is flipped to the opposite bit value. By thinking of each of these eight resulting states as column vectors, the matrix representation of the circuit, $T$ can be constructed by making each column of the matrix correspond to the vector that represents the resulting state under the circuit mapping as follows:
\[
T=\begin{pmatrix}
1&0&0&0&0&0&0&0 \\
0&1&0&0&0&0&0&0 \\
0&0&1&0&0&0&0&0 \\
0&0&0&1&0&0&0&0 \\
0&0&0&0&1&0&0&0 \\
0&0&0&0&0&1&0&0 \\
0&0&0&0&0&0&0&1 \\
0&0&0&0&0&0&1&0 \\
\end{pmatrix}.
\]

Determining a hidden "dot product vector"

 Consider the problem where one is given black-box access to a function $f : \{0,1\}^n \to \{0,1\}$ such that $f(x)=\mathbf{a}\cdot \mathbf{x}$, where $\mathbf{a}\in \{0,1\}^n$ is unknown. Here $\mathbf{a}\cdot \mathbf{x} = a_1x_1+a_2x_2+\dots +a_n x_n (mod 2)$ is the dot product of $\mathbf{a}$ and $\mathbf{x}$ in modulo-$2$ arithmetic. The goal is to determine the $n$-bit string $a$.

The following classical algorithm solves this problem with $n$ queries. Let $\mathbf{x_k}\in\{0,1\}^n$ be the bit string $\mathbf{x_k}:=0\dots010\dots0$ which has a bit value of $1$ in the $k$th position and $0$ everywhere else.

1. Set $k=1$.
2. Query $f$ at $\mathbf{x_k}$ to get $f(\mathbf{x_k})=\mathbf{a}\cdot \mathbf{x_k}=a_k$.
3. Set $k'=k+1$, if $k\leq n$ and proceed to step (4). If $k>n$, proceed to step (5).
4. Repeat step (2)-(3) with $k'=k$.
5. Construct the string $a_1a_2\dots a_n=\mathbf{a}$ using the bits obtained in step (2).

This algorithm terminates and succeeds in determining the string $a$ after $n$ queries have been made to $f$.

For some fixed bitstring $\mathbf{a}\neq\mathbf{0}$, querying $f$ with some bitstring $\mathbf{x}$ gives $\mathbf{a}\cdot \mathbf{x} = a_1x_1+a_2x_2+\dots +a_n x_n (mod 2)$, which can be thought of as an equation in the $n$ unknowns given by the $a_i$. Then querying $f$ with another string $\mathbf{x'}$ will similarly yield another equation of the form $\mathbf{x'} = a_1x'_1+a_2x'_2+\dots +a_n x'_n (mod 2)$. Then after $k$ queries with $k<n$ there will be a system of $k$ equations in $n$ unknowns. It is a general fact of linear algebra that such a system cannot uniquely determine the values of all of the $a_i$ variables/bits that comprise the unknown string $\mathbf{a}$. Therefore, $\mathbf{a}$ cannot be uniquely determined. If $k$ queries have been made, and the resulting equations from each of these are independent, then at most $k$ bits of $\mathbf{a}$ can be determined. Thus, no classical algorithm can solve this problem with fewer than $n$ queries in order to uniquely determine $\mathbf{a}$ with certainty.

Presented here is a quantum algorithm for solving the problem. Begin with an $n+1$ qubits, where the first $n$ qubit registers are initialized in the state $\ket{0}$ and the last qubit in the state $\ket{1}$. Consider the following circuit:


Here the first and last gates apply the single qubit Hadamard gate to each of the $n+1$ registers. The second gate $U_f$ is defined as
\[
U_f: \ket{\mathbf{x}}\ket{y}\mapsto \ket{\mathbf{x}}\ket{y\oplus f(x)},
\]
where $\mathbf{x}\in\{0,1\}^n$ and $y\in\{0,1\}$. The last part of the circuit denotes a measurement on the first $n$ registers.

Consider the action of this circuit on the initial state $\ket{\mathbf{0}}\ket{1}$ up until the measurements are performed:
\[\begin{align*}
\ket{\mathbf{0}}\ket{1}\overset{H^{\otimes n+1}}\mapsto &
\frac{1}{\sqrt{2^{n+1}}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}\ket{\mathbf{j}}(\ket{0}-\ket{1})\\
\overset{U_f}\mapsto \ \  &\frac{1}{\sqrt{2^{n+1}}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}\ket{\mathbf{j}}(\ket{\mathbf{a}\cdot\mathbf{j}}-\ket{1\oplus\mathbf{a}\cdot\mathbf{j}})\\
&=\frac{1}{\sqrt{2^{n+1}}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{\mathbf{a}\cdot\mathbf{j}}\ket{\mathbf{j}}(\ket{0}-\ket{1}) \\
\overset{H^{\otimes n+1}}\mapsto &\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{k}\in\{0,1\}^n}\displaystyle\left(\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{\mathbf{k}\cdot\mathbf{j}}(-1)^{\mathbf{a}\cdot\mathbf{j}}\right))\ket{\mathbf{k}}\ket{1}.
\end{align*}\]

The third line of this calculation gives the state that results after the Hadamard gates and $U_f$ gate is applied.

As computed in part (c), the state that results after the second set of Hadamard gates is applied is given by
\[
\ket{\varphi}:=\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{k}\in\{0,1\}^n}\displaystyle\left(\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{\mathbf{k}\cdot\mathbf{j}}(-1)^{\mathbf{a}\cdot\mathbf{j}}\right))\ket{\mathbf{k}}\ket{1}.
\]
Let the amplitude of the $\ket{\mathbf{k}}$ in this superposition be given by $\alpha_k$. Then
\[
\alpha_k=\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{\mathbf{k}\cdot\mathbf{j}}(-1)^{\mathbf{a}\cdot\mathbf{j}}=\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{\mathbf{k}\cdot\mathbf{j}\oplus\mathbf{a}\cdot\mathbf{j}}.
\]
The amplitude of the state $\ket{\mathbf{a}}$ in $\ket{\varphi}$ is
\[
\alpha_a=\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{\mathbf{a}\cdot\mathbf{j}\oplus\mathbf{a}\cdot\mathbf{j}}
=\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{0}=\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}1=\frac{1}{2^{n}}2^n=1.
\]
Hence, the first $n$ registers in the state $\ket{\varphi}$ are in the state $\ket{\mathbf{a}}$ with probability $1$. Since $\ket{\varphi}$ must be a normalized state, this implies that the amplitudes $\alpha_k$ of the states $\ket{\mathbf{k}}$ for all $\mathbf{k}\neq\mathbf{a}$ in $\ket{\varphi}$ are $\alpha_k=0$. Therefore, when the first $n$ registers are measured in the computational basis the state $\ket{\mathbf{a}}$ will always be observed, which then determines the string $\mathbf{a}$.