A particular instance of Grover's search

Here, we will analyze how Grover's search algorithm can be used in the particular cases when the density of marked items is $1/4$ and $1/2$.

Consider a function $f:\{0,1\}^n \to \{0,1\}$, define the sets
\[\begin{align*}
A&=\{x\in\{0,1\}^n : f(x)=1\} \\
B&=\{x\in\{0,1\}^n : f(x)=0\},
\end{align*} \]
and let $a=|A|$ and $b=|B|$.

The equally weighted superposition of all basis states in a $2^n=N$ dimensional Hilbert space can be expressed as
\[
\ket{\psi_0}=\frac{1}{\sqrt{N}}\SUM{x\in\{0,1\}^n}{}\ket{x}=\sqrt{\frac{a}{N}}\SUM{f(x)=1}{}\ket{x}+\sqrt{\frac{b}{N}}\SUM{f(x)=0}{}\ket{x}.
\]
Assuming that $a=|A|$ is known, choose $\theta$ such that $\sin(\theta)=\sqrt{\frac{a}{N}}$. Then the superposition $\ket{\psi_0}$ can be equivalently written as
\[
\ket{\psi_0}=\sin(\theta)\SUM{f(x)=1}{}\ket{x}+\cos(\theta)\SUM{f(x)=0}{}\ket{x}.
\]
In Grover's search algorithm, $\ket{\psi_0}$ is prepared as an initial state, and then a sequence of \emph{Grover} iterations are applied, which after $k$ iterations, results in the state
\[
\ket{\psi_k}=\sin((2k+1)\theta)\SUM{f(x)=1}{}\ket{x}+\cos((2k+1)\theta)\SUM{f(x)=0}{}\ket{x}.
\]
The objective is to choose the number of iterations $k$ so that $\sin((2k+1)\theta)\approx 1$ so that some state $\ket{x}$ such that $x\in{A}$ is measured with high probability. For this to be the case, it suffices that the following conditions hold:
\[\begin{align*}
\sin((2k+1)\theta)&\approx 1 \\
(2k+1)\theta&\approx \frac{\pi}{2} \\
k&\approx \frac{\pi}{4\theta}-\frac{1}{2} \\
\end{align*}\]

Consider the case when $a=\frac{1}{4}2^n=\frac{1}{4}N$ so that the initial angle $\theta$ is chosen to satisfy $\sin(\theta)=\sqrt{\frac{a}{N}}=\sqrt{\frac{N}{4N}}=\frac{1}{2}$ implying that $\theta=\frac{\pi}{6}$. In this case, the number of desired iterations that need to be performed is actually given by
\[
k= \frac{\pi}{4\theta}-\frac{1}{2}=\frac{\pi 6}{4\pi}-\frac{1}{2}=1,
\]
and thus Grover's algorithm is guaranteed to find an $x$ such that $x\in A$ in just a single iteration.

Now consider the case where $a=\frac{1}{2}2^n=\frac{1}{2}N$ so that the initial angle $\theta$ is chosen to satisfy $\sin(\theta)=\sqrt{\frac{a}{N}}=\sqrt{\frac{N}{2N}}=\frac{1}{\sqrt{2}}$ implying that $\theta=\frac{\pi}{4}$. In this case, the number of desired iterations that need to be performed is approximately
\[
k\approx \frac{\pi}{4\theta}-\frac{1}{2}=\frac{\pi 4}{4\pi}-\frac{1}{2}=\frac{1/2}.
\]
However, since $k$ is not an integer and is equally close to the integers $0$ and $1$ it is seen that a state $\ket{x}$ such that $x\in A$ is not guaranteed to be found with certainty if the state $\ket{\psi_k}$ were to be measured. In this instance, Grover's search algorithm provides no benefit, in the sense that the likelihood of observing a state $\ket{x}$ such that $x\in A$ is equally probably if $1$ iteration is performed or if $0$ iterations are performed to the initial state.

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

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

Classical and quantum algorithms for the OR problem

Consider the problem, where given a black box for a function $f:\{0,1\}\to\{0,1\}$, the goal is to determine the logical OR $f(0) \vee f(1)$ (or equivalently $f(0)\oplus f(1)$, where $\oplus$ denotes addition modulo $2$) with a \emph{single} query to  $f$.

A classical probabilistic algorithm that makes only a single query to $f$ and predicts $f(0)\vee f(1)$ with probability $2/3$ proceeds as follows.

1. With uniform probability (1/2) randomly select a bit $b\in\{0,1\}$.
2. Query $f$ at $b$ to get the value $f(b)$.
3.  Set $f(b)=f(0)\vee f(1)$.

If $f(b)=1$ (which can only possibly happen in the cases where either $f=f_{10},f=f_{10}, \ \text{or} \ f=f_{11}$), then certainly $f(0)\vee f(1)=f(b)=1$ and the algorithm succeeds. However, if $f(b)=0$, then $f(0)\vee f(1)=f(b)=0$ will be correctly evaluated if and only if $f(b\oplus1)=0$ (in this case $f=f_{00}$). Otherwise, it could be the case that $f(b\oplus1)=1$ (where $f\neq f_{00}$) which implies $1=f(0)\vee f(1)\neq f(b)=0$, and the proposed algorithm would fail to get the correct value of $f(0)\vee f(1)$.


Let $U$ be the one-qubit unitary gate whose matrix representation is given by
\[
U=\begin{pmatrix}
1&\sqrt{2} \\
\sqrt{2}&-1
\end{pmatrix}.
\]
Denote the following states as $\ket{+}:=\frac{1}{\sqrt{2}}(\ket{0}+{1})$ and $\ket{-}:=\frac{1}{\sqrt{2}}(\ket{0}-{1})$. Now consider the circuit shown below:


 For notational purposes write $c_{r}G_{t}$ to represent the controlled-$G$ gate, where register $r$ serves as the control register and register $t$ serves as the target register. In this way, gate $G$ is applied to the state in register $t$ if the state in register $r$ is $\ket{1}$ and the gate $G$ is not applied if the state in the register $r$ is $\ket{0}$ (the action of the controlled gate extends linearly when the control register is in some superposition). Also, write $c_{r,s}G_s$ to mean that register $r$ and $s$ are to both serve as the control, where $G$ is applied to register $s$ if and only if both control registers $r$ and $s$ are in the state $\ket{1}$.

Notice that $\ket{x}+\ket{1\oplus x}=\ket{+}$ and that $\ket{x}-\ket{1\oplus x}=(-1)^x\ket{-}$ for $x=0,1$. The action of the circuit shown above on input $\ket{000}$ is now calculated:
\[ \begin{align*}
 \ket{000}\overset{I\otimes U\otimes X}\mapsto &\frac{1}{\sqrt{3}}\ket{0}(\ket{0}+\sqrt{2}\ket{1})\ket{1} \\
\overset{c_2H_1\otimes H}\mapsto &\frac{1}{\sqrt{3}}(\ket{0}\ket{0}+\ket{0}\ket{1}+\ket{1}\ket{1})\ket{-} \\
\overset{c_{1,2}Z_3}\mapsto & \frac{1}{\sqrt{3}}(\ket{0}\ket{0}\ket{-}+\ket{0}\ket{1}\ket{-}+\ket{1}\ket{1}\ket{+}) \\
\overset{I\otimes U_f}\mapsto & \frac{1}{\sqrt{3}\sqrt{2}}(\ket{0}\ket{0}(\ket{f(0)}-\ket{1\oplus f(0)})+\ket{0}\ket{1}(\ket{f(1)}-\ket{1\oplus f(1)})+\ket{1}\ket{1}(\ket{f(1)}+\ket{1\oplus f(1)})) \\
&=\frac{1}{\sqrt{3}}(\ket{0}\ket{0}(-1)^{f(0)}\ket{-}+\ket{0}\ket{1}(-1)^{f(1)}\ket{-}+\ket{1}\ket{1}\ket{+}) \\
\overset{c_{1,2}Z_3}\mapsto &\frac{1}{\sqrt{3}}(\ket{0}\ket{0}(-1)^{f(0)}\ket{-}+\ket{0}\ket{1}(-1)^{f(1)}\ket{-}+\ket{1}\ket{1}\ket{-}) \\
&= \frac{1}{\sqrt{3}}((-1)^{f(0)}\ket{0}\ket{0}+(-1)^{f(1)}\ket{0}\ket{1}+\ket{1}\ket{1})\ket{-}.
 \end{align*}\]
 Observe that register $3$ in this final state has been factored out and separated from registers $1$ and $2$. Therefore, by ignoring register $3$ the state of registers $1$ and $2$ is given as:
\[
 \ket{\psi}=\frac{1}{\sqrt{3}}((-1)^{f(0)}\ket{00}+(-1)^{f(1)}\ket{01}+\ket{11}).
\]


Consider the four possible states $\ket{\psi_{00}}, \ket{\psi_{01}}, \ket{\psi_{10}}, \ \text{or} \ \ket{\psi_{11}}$ of $\ket{\psi}$ that result in the cases where $f$ is one of the four functions $f_{00}, f_{01}, f_{10}, \ \text{or} \ f_{11}$, respectively:
\[\begin{align*}
\ket{\psi_{00}}=&\frac{1}{\sqrt{3}}(\ket{00}+\ket{01}+\ket{11}), \\
 \ket{\psi_{01}}=&\frac{1}{\sqrt{3}}(\ket{00}-\ket{01}+\ket{11}), \\
  \ket{\psi_{10}}=&\frac{1}{\sqrt{3}}(-\ket{00}+\ket{01}+\ket{11}), \\
  \ket{\psi_{11}}=&\frac{1}{\sqrt{3}}(-\ket{00}-\ket{01}+\ket{11}).
\end{align*}\]
Then the inner products between each pair of states is
\[
\begin{align*}
\ip{\psi_{00}}{\psi_{01}}=&\frac{1}{3}(\bra{00}+\bra{01}+\bra{11})(\ket{00}-\ket{01}+\ket{11})=\frac{1}{3}-\frac{1}{3}+\frac{1}{3}=\frac{1}{3}, \\
\ip{\psi_{00}}{\psi_{10}}=&\frac{1}{3}(\bra{00}+\bra{01}+\bra{11})(-\ket{00}+\ket{01}+\ket{11})=-\frac{1}{3}+\frac{1}{3}+\frac{1}{3}=\frac{1}{3}, \\
\ip{\psi_{00}}{\psi_{11}}=&\frac{1}{3}(\bra{00}+\bra{01}+\bra{11})(-\ket{00}-\ket{01}+\ket{11})=-\frac{1}{3}-\frac{1}{3}+\frac{1}{3}=-\frac{1}{3}, \\
\ip{\psi_{01}}{\psi_{10}}=&\frac{1}{3}(\bra{00}-\bra{01}+\bra{11})(-\ket{00}+\ket{01}+\ket{11})=-\frac{1}{3}-\frac{1}{3}+\frac{1}{3}=-\frac{1}{3}, \\
\ip{\psi_{01}}{\psi_{11}}=&\frac{1}{3}(\bra{00}-\bra{01}+\bra{11})(-\ket{00}-\ket{01}+\ket{11})=-\frac{1}{3}+\frac{1}{3}+\frac{1}{3}=\frac{1}{3}, \\
\ip{\psi_{10}}{\psi_{11}}=&\frac{1}{3}(-\bra{00}+\bra{01}+\bra{11})(-\ket{00}-\ket{01}+\ket{11})=\frac{1}{3}-\frac{1}{3}+\frac{1}{3}=\frac{1}{3},
\end{align*}
\]
Hence, the absolute value of the inner products between all of these states is $\frac{1}{3}$.


Based off the results just described above, a quantum algorithm will now be presented for the OR problem. Consider the supplemented circuit shown below, which is just the circuit shown previously with an additional controlled Hadamard and $U$ gate appended to the end as shown followed by measurements of the first two registers.:


Let $\ket{\psi'}$ denote the state that results when the state $\ket{\psi}$ from $2$(b) is passed through the rest of the circuit shown above. Then the state before the measurement will be given by
\[
\ket{\psi'}=\frac{1}{3}\displaystyle\left((-1)^{f(0)}\ket{0}(\ket{0}+\sqrt{2}\ket{1})+(-1)^{f(1)}\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})(\sqrt{2}\ket{0}-\ket{1})+\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})(\ket{0}-\ket{1})\right)
\]

Now consider the four states $\ket{\psi'_{ij}}$ that result when the function $f_{ij}$ is the one that happens to be queried:
\[\begin{align*}
\ket{\psi'_{00}}=&\ket{00} \\
\ket{\psi'_{01}}=&\frac{1}{3}(\ket{00}+\sqrt{2}\ket{01}+2\ket{10}+\sqrt{2}\ket{11}) \\
\ket{\psi'_{10}}=&\frac{1}{3}(\ket{00}-\frac{4}{\sqrt{2}}\ket{01}) \\
\ket{\psi'_{11}}=&\frac{1}{3}(-\ket{00}-\sqrt{2}\ket{01}-2\ket{10}+\sqrt{2}\ket{11}).
\end{align*}\]

The state $\ket{\psi'_{00}}$ corresponding to the function $f_{00}$, is not in a superposition and will always yield the state $\ket{00}$ when measured with probability $1$. Also, notice that for the states $\ket{\psi'_{ij}}$ where $ij\neq 00$, the probability of observing the $\ket{00}$ state is always $1/9$, and the probability for observing any other state is therefore $8/9$.

With this mind the quantum algorithm will work as follows. Run the circuit as described above, which would yield one of the four states $\ket{\psi'_{ij}}$ depending on which function happened to be queried. Then perform a measurement in the computational basis on the first two registers. If the state $\ket{00}$ is observed, output the value $0$ for $f(0)\vee f(1)$. Otherwise, if any of the states $\ket{01}, \ket{10}, \ \text{or} \ \ket{11}$ are observed, then output the value $1$ for $f(0)\vee f(1)$.

It is only in the case when the function that was queried happened to be $f_{00}$ that the value of $f(0)\vee f(1)$ is $0$. Therefore, if this did happen to be the case, the state $\ket{\psi'_{00}}=\ket{00}$ will always be observed with certainty, and this algorithm will succeed with probability $1$. On the other hand, if one of the three other functions $f_{ij}$ for $ij\neq00$ happened to be queried, then the resulting states would be one of the corresponding $\ket{\psi'_{ij}}$ for $ij\neq00$. Moreover, in these three cases the value of $f(0)\vee f(1)$ will always be $1$. When one of these three states are measured, the state $\ket{00}$ may be observed with probability $1/9$. In this instance, the algorithm will fail. Otherwise, some basis state $\ket{ij}\neq\ket{00}$ will be observed with probability $8/9$, and in this case the algorithm will have given the correct value of $f(0)\vee f(1)$.


The quantum algorithm just presented will now be modified with classical post-processing to yield an algorithm that succeeds in all cases with probability $9/10$. This classical algorithm will take as input, the output of the quantum algorithm which was just the value $0$ or $1$ represented the value of $f(0)\vee f(1)$.

The output of the classical algorithm also be a value assigned to $f(0)\vee f(1)$. However, now classical algorithm will utilize some randomization to give a final value.

On input $0$, the classical algorithm will output $0$ with probability $9/10$, and with probability $1/9$ will output $1$ instead.

On input $1$, the classical algorithm will output $1$ with probability $1$.

To calculate the probability of success of the classical algorithm introduce the following notation: write $Pr(QA=b)$ to represent the probability that the quantum algorithm outputs the value $b$, and write $Pr(CA=a\mid QA=b)$ to represent the probability that the classical algorithm outputs the value $a$ given that the quantum algorithm outputs $b$.

Now consider the case, where the function being queried happened to be $f_{00}$. Then the probability of success in this case will be given by:
\[\begin{align*}
Pr(success\mid f_{00})=&Pr(CA=0\mid QA=0)Pr(QA=0)+Pr(CA=0\mid QA=1)Pr(QA=1) \\
=&\frac{9}{10}\cdot1+0\cdot0=\frac{9}{10}
\end{align*}\]
The last two probabilities in this expression are $0$, because the quantum algorithm will never output $1$ when the function $f_{00}$ happens to be the one being queried.

In the cases, where the function that is being queried is one of the three $f_{ij}$ for $ij\neq00$, then
\[\begin{align*}
Pr(success\mid f_{ij})=&Pr(CA=1\mid QA=1)Pr(QA=1)+Pr(CA=1\mid QA=0)Pr(QA=0) \\
=&1\cdot\frac{8}{9}+\frac{1}{10}\cdot\frac{1}{9}=\frac{9}{10}
\end{align*}\]

Hence, in all cases this algorithm succeeds with probability $8/9$.