## Wednesday, 30 October 2013

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