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

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

The impossibillity of evaluating a function at two inputs with a single query

Consider functions of the form $f : \{0,1\}\to\{0,1\}$, and a query oracle for such a function given as a unitary operator $U_f$ defined as $\ket{a,b}\mapsto\ket{a,b\oplus f(a)}$ for $a,b\in\{0,1\}$. In an attempt to obtain information about the values $f(0)$ and $f(1)$, assume the methods use only two qubits and can be expressed as a circuit of the form



where $V$ and $W$ are two-qubit unitaries and the last two gates labelled with $X$ are measurements in the computational basis.

Label the four possible functions under consideration as follows:

\[f_{00}(x) = \left\{
\begin{array}{rl}
0,& x=0 \\
0,&x=1
\end{array}\right.;\]
\[f_{01}(x) = \left\{
\begin{array}{rl}
0,& x=0 \\
1,&x=1
\end{array}\right.;\]

\[f_{10}(x) = \left\{
\begin{array}{rl}
1,& x=0 \\
0,&x=1
\end{array}\right.;\]
\[f_{11}(x) = \left\{
\begin{array}{rl}
1,& x=0 \\
1,&x=1
\end{array}\right..\]

Let $\ket{\psi}=\alpha_{00}\ket{00}+\alpha_{01}\ket{01}+\alpha_{10}\ket{10}+\alpha_{11}\ket{11}$, where
\[|\alpha_{00}|^2+|\alpha_{01}|^2+|\alpha_{10}|^2+|\alpha_{11}|^2=1,\]
be the general form of the state that results after the $V$ gate is applied in the circuit. For each of the four functions, the states that results after the query gate $U_{f_{ij}}$ is applied to $\ket{\psi}$ are given by:

\[
\begin{align*}
 \ket{\psi_{00}}:=U_{f_{00}}\ket{\psi}&=\alpha_{00}\ket{0,0\oplus f_{00}(0)}+\alpha_{01}\ket{0,1\oplus f_{00}(0)}+\alpha_{10}\ket{1,0\oplus f_{00}(1)}+\alpha_{11}\ket{1,1\oplus f_{00}(1)} \\
 &=\alpha_{00}\ket{00}+\alpha_{01}\ket{01}+\alpha_{10}\ket{10}+\alpha_{11}\ket{11}, \\
 \\
  \ket{\psi_{01}}:=U_{f_{01}}\ket{\psi}&=\alpha_{00}\ket{0,0\oplus f_{01}(0)}+\alpha_{01}\ket{0,1\oplus f_{01}(0)}+\alpha_{10}\ket{1,0\oplus f_{01}(1)}+\alpha_{11}\ket{1,1\oplus f_{01}(1)} \\
 &=\alpha_{00}\ket{00}+\alpha_{01}\ket{01}+\alpha_{11}\ket{10}+\alpha_{10}\ket{11}, \\
 \\
  \ket{\psi_{10}}:=U_{f_{10}}\ket{\psi}&=\alpha_{00}\ket{0,0\oplus f_{10}(0)}+\alpha_{01}\ket{0,1\oplus f_{10}(0)}+\alpha_{10}\ket{1,0\oplus f_{10}(1)}+\alpha_{11}\ket{1,1\oplus f_{10}(1)} \\
 &=\alpha_{01}\ket{00}+\alpha_{00}\ket{01}+\alpha_{10}\ket{10}+\alpha_{11}\ket{11}, \\
 \\
  \ket{\psi_{11}}:=U_{f_{11}}\ket{\psi}&=\alpha_{00}\ket{0,0\oplus f_{11}(0)}+\alpha_{01}\ket{0,1\oplus f_{11}(0)}+\alpha_{10}\ket{1,0\oplus f_{11}(1)}+\alpha_{11}\ket{1,1\oplus f_{11}(1)} \\
 &=\alpha_{01}\ket{00}+\alpha_{00}\ket{01}+\alpha_{11}\ket{10}+\alpha_{10}\ket{11}, \\
 \end{align*}
\]

For any measurement to be able to distinguish the four states $\ket{\psi_{ij}}$ it must be the case that the states $\ket{\psi_{ij}}$ are mutually orthogonal. The unitary gate $W$ would then serve the purpose of rotating these states into the four computational basis states, which would then be distinguished by the measurements made on the two qubits. Observe that the four functions satisfy the properties that $f_{00}(0)=f_{01}(0)=0$ and $f_{10}(0)=f_{11}(0)=1$. Therefore, in order for a measurement to be able to determine the value of $f_{ij}(0)$, the following orthogonality constraints must hold:
\[
\ip{\psi_{00}}{\psi_{10}}=0 \ \text{and} \ \ip{\psi_{00}}{\psi_{11}}=0
\]

Computing these inner products with these constraints imposed gives

\[\begin{align*}
\ip{\psi_{00}}{\psi_{10}}=\overline{\alpha_{00}}\alpha_{01}+\overline{\alpha_{01}}\alpha_{00}+\overline{\alpha_{10}}\alpha_{10}+\overline{\alpha_{11}}\alpha_{11}=0,
\\
\ip{\psi_{00}}{\psi_{11}}=\overline{\alpha_{00}}\alpha_{01}+\overline{\alpha_{01}}\alpha_{00}+\overline{\alpha_{10}}\alpha_{11}+\overline{\alpha_{11}}\alpha_{10}=0,
\end{align*}
\]

which implies that
\[
\begin{align*}
&\overline{\alpha_{10}}\alpha_{10}+\overline{\alpha_{11}}\alpha_{11}=\overline{\alpha_{10}}\alpha_{11}+\overline{\alpha_{11}}\alpha_{10}, \\
\implies &(\overline{\alpha_{10}}-\overline{\alpha_{11}})(\alpha_{10}-\alpha_{11})=0, \\
\implies&\alpha_{10}-\alpha_{11}=0,
\end{align*}
\]
so that $\alpha_{10}=\alpha_{11}$.

The orthogonality conditions mentioned in above were chosen so that that the value of $f(0)$ can be determined perfectly. The result of these constraints implied that $\alpha_{10}=\alpha_{11}$. By letting $\alpha=\alpha_{10}=\alpha_{11}$ it is seen that
\[
\begin{align*}
\ket{\psi_{00}}=\alpha_{00}\ket{00}+\alpha_{01}\ket{01}+\alpha\ket{10}+\alpha\ket{11}=\ket{\psi_{01}}, \\
  \ket{\psi_{10}}=\alpha_{01}\ket{00}+\alpha_{00}\ket{01}+\alpha\ket{10}+\alpha\ket{11}=  \ket{\psi_{11}}.
\end{align*}
\]
Thus $\ket{\psi_{00}}$ and $\ket{\psi_{01}}$ are really the same state, and $  \ket{\psi_{10}}$ and $ \ket{\psi_{11}}$ are the same state.

  In an attempt to also determine the value of $f(1)$ observe that $f_{00}(1)=f_{10}(1)=0$ and that $f_{01}(1)=f_{11}(1)=1$. Therefore, in order to be able to determine the value of $f_{ij}(1)$ it must also be the case that $\ip{\psi_{00}}{\psi_{01}}=0$ and $\ip{\psi_{10}}{\psi_{11}}=0$, but since the constraints for determining $f_{ij}(0)$ implied that $\ket{\psi_{00}}=\ket{\psi_{01}}$, it is actually the case that $\ip{\psi_{00}}{\psi_{01}}=1\neq0$. Hence, the orthogonality constraints that must hold in order for both the values of $f_{ij}(0)$ and $f_{ij}(1)$ to hold can not be satisfied simultaneously.
 
  In order to be determine the value of $f_{ij}(1)$ perfectly provided that that value of $f_{ij}(0)$ can be determined perfectly, the states $\ket{\psi_{00}}$, and $\ket{\psi_{01}}$ must be perfectly distinguishable, and also the states $\ket{\psi_{10}}$, and $\ket{\psi_{11}}$ must also be distinguishable. However, since$\ket{\psi_{00}}=\ket{\psi_{01}}$ and $\ket{\psi_{00}}=\ket{\psi_{01}}$ such a distinguishing procedure is impossible, and would only be able to succeed with probability at most $1/2$.

Constructing simple two qubit states

Here, we will describe how to construct some simple two-qubit states using some primitive gates.

In what follows, a two-qubit quantum circuit consisting of one $CNOT$ gate and two Hadamard $H$ gates that computes the following unitary transformation will be described:
\[U=\begin{pmatrix}
1&0&0&0 \\
0&1&0&0\\
0&0&1&0 \\
0&0&0&-1
\end{pmatrix}\]

Consider the for computational basis states and their corresponding representation as column vectors:
\[\ket{00}=\begin{pmatrix}
1\\0\\0\\0
\end{pmatrix},
\ket{01}=\begin{pmatrix}
0\\1\\0\\0
\end{pmatrix},
\ket{10}=\begin{pmatrix}
0\\0\\1\\0
\end{pmatrix},
\ket{11}=\begin{pmatrix}
0\\0\\0\\1
\end{pmatrix}.\]

Observe that $U$ leaves the first three basis states unchanged and only multiplies the last by a factor of $-1$:
\[U\ket{00}=\ket{00},
U\ket{01}=\ket{01},
U\ket{10}=\ket{10},
U\ket{11}=-\ket{11}.\]

Consider the following circuit consisting of a Hadamard gate acting on the second qubit, followed by a controlled-NOT gate, and then with a second Hadamard gate acting on the second qubit again.


 The action of this circuit on each of the four basis states is described below:
 \[\ket{00} \overset{I\otimes H}\mapsto\super{\ket{00}+\ket{01}}\overset{CNOT}\mapsto\super{\ket{00}+\ket{01}}\overset{I\otimes H}\mapsto\frac{1}{2}(\ket{00}+\ket{01}+\ket{00}-\ket{01})=\ket{00},\]

\[\ket{01} \overset{I\otimes H}\mapsto\super{\ket{00}-\ket{01}}\overset{CNOT}\mapsto\super{\ket{00}-\ket{01}}\overset{I\otimes H}\mapsto\frac{1}{2}(\ket{00}+\ket{01}-\ket{00}+\ket{01})=\ket{01},\]

\[\ket{10} \overset{I\otimes H}\mapsto\super{\ket{10}+\ket{11}}\overset{CNOT}\mapsto\super{\ket{11}+\ket{10}}\overset{I\otimes H}\mapsto\frac{1}{2}(\ket{10}-\ket{11}+\ket{10}+\ket{11})=\ket{10}, \]

\[\ket{11} \overset{I\otimes H}\mapsto\super{\ket{10}-\ket{11}}\overset{CNOT}\mapsto\super{\ket{11}-\ket{10}}\overset{I\otimes H}\mapsto\frac{1}{2}(\ket{10}-\ket{11}-\ket{10}-\ket{11})=-\ket{11}.\]

Thus, the action of the circuit is identical to the unitary transformation $U$ expressed as the matrix since the four basis  states are mapped similarly.


Now, define the one-qubit gates $H$ and $S$ as
\[H=\frac{1}{\sqrt{2}}\begin{pmatrix}
1&1\\
1&-1
\end{pmatrix}\]
and
\[S=\begin{pmatrix}
1&0\\
0&i
\end{pmatrix}\]

In each case, the $4\times4$ matrix corresponding to the two-qubit controlled gate is given.

Denote the following gate by $c_1H_2$:

Observe how the $c_1H_2$ gate acts on the four basis states:
\[\ket{00}=\begin{pmatrix} 1\\0\\0\\0\end{pmatrix}\overset{c_1H_2}\mapsto\ket{00}=\begin{pmatrix} 1\\0\\0\\0\end{pmatrix}, \ \ \ \ \ \ \
\ket{01}=\begin{pmatrix} 0\\1\\0\\0\end{pmatrix}\overset{c_1H_2}\mapsto\ket{01}=\begin{pmatrix} 0\\1\\0\\0\end{pmatrix},\]

\[\ket{10}=\begin{pmatrix} 0\\0\\1\\0\end{pmatrix}\overset{c_1H_2}\mapsto\super{\ket{10}+\ket{11}}=\frac{1}{\sqrt{2}}\begin{pmatrix} 0\\0\\1\\1\end{pmatrix},\]

\[\ket{11}=\begin{pmatrix} 0\\0\\0\\1\end{pmatrix}\overset{c_1H_2}\mapsto\super{\ket{10}-\ket{11}}=\frac{1}{\sqrt{2}}\begin{pmatrix} 0\\0\\1\\-1\end{pmatrix}.\]

The matrix representation of the gate $c_1H_2$ can be constructed by placing each of these output vectors as the columns of the matrix:
\[c_1H_2=\begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
0&0&\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\
0&0&\frac{1}{\sqrt{2}}&\frac{-1}{\sqrt{2}}
\end{pmatrix}.\]


Denote the following gate by $c_2H_1$:

Observe how the $c_2H_1$ gate acts on the four basis states:
\[\ket{00}=\begin{pmatrix} 1\\0\\0\\0\end{pmatrix}\overset{c_2H_1}\mapsto\ket{00}=\begin{pmatrix} 1\\0\\0\\0\end{pmatrix}, \ \ \ \
\ket{01}=\begin{pmatrix} 0\\1\\0\\0\end{pmatrix}\overset{c_2H_1}\mapsto\super{\ket{01}+\ket{11}}=\frac{1}{\sqrt{2}}\begin{pmatrix} 0\\1\\0\\1\end{pmatrix},\]

\[\ket{10}=\begin{pmatrix} 0\\0\\1\\0\end{pmatrix}\overset{c_2H_1}\mapsto\ket{10}=\begin{pmatrix} 0\\0\\1\\0\end{pmatrix}, \ \ \ \ \
\ket{11}=\begin{pmatrix} 0\\0\\0\\1\end{pmatrix}\overset{c_2H_1}\mapsto\super{\ket{01}-\ket{11}}=\frac{1}{\sqrt{2}}\begin{pmatrix} 0\\1\\0\\-1\end{pmatrix}.\]

Then, matrix representation of the gate $c_1H_2$ can be constructed by placing each of these output vectors as the columns of the matrix:
\[c_1H_2=\begin{pmatrix}
1&0&0&0\\
0&\frac{1}{\sqrt{2}}&0&\frac{1}{\sqrt{2}}\\
0&0&1&0\\
0&\frac{1}{\sqrt{2}}&0&\frac{-1}{\sqrt{2}}
\end{pmatrix}.\]


Denote the following gate by $c_1S_2$:

 First note that $S\ket{0}=\ket{0}$ and $S\ket{1}=i\ket{1}$. Now observe how the $c_1S_2$ gate acts on the four basis states:
\[\ket{00}=\begin{pmatrix} 1\\0\\0\\0\end{pmatrix}\overset{c_1S_2}\mapsto\ket{00}=\begin{pmatrix} 1\\0\\0\\0\end{pmatrix}, \ \ \ \ \ \ \
\ket{01}=\begin{pmatrix} 0\\1\\0\\0\end{pmatrix}\overset{c_1S_2}\mapsto\ket{01}=\begin{pmatrix} 0\\1\\0\\0\end{pmatrix},\]

\[\ket{10}=\begin{pmatrix} 0\\0\\1\\0\end{pmatrix}\overset{c_1S_2}\mapsto\ket{10}=\begin{pmatrix} 0\\0\\1\\0\end{pmatrix}, \ \ \ \ \ \ \
\ket{11}=\begin{pmatrix} 0\\0\\0\\1\end{pmatrix}\overset{c_1S_2}\mapsto\ket{11}=\begin{pmatrix} 0\\0\\0\\i\end{pmatrix}.\]

The matrix representation of the gate $c_1S_2$ can be constructed by placing each of these output vectors as the columns of the matrix:
\[c_1S_2=\begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
0&0&1&0\\
0&0&0&i
\end{pmatrix}.\]


Denote the following gate by $c_2S_1$:

Observe how the $c_2S_1$ gate acts on the four basis states:
\[\ket{00}=\begin{pmatrix} 1\\0\\0\\0\end{pmatrix}\overset{c_2S_1}\mapsto\ket{00}=\begin{pmatrix} 1\\0\\0\\0\end{pmatrix}, \ \ \ \ \ \ \
\ket{01}=\begin{pmatrix} 0\\1\\0\\0\end{pmatrix}\overset{c_2S_1}\mapsto\ket{01}=\begin{pmatrix} 0\\1\\0\\0\end{pmatrix},\]

\[\ket{10}=\begin{pmatrix} 0\\0\\1\\0\end{pmatrix}\overset{c_2S_1}\mapsto\ket{10}=\begin{pmatrix} 0\\0\\1\\0\end{pmatrix}, \ \ \ \ \ \ \
\ket{11}=\begin{pmatrix} 0\\0\\0\\1\end{pmatrix}\overset{c_2S_1}\mapsto\ket{11}=\begin{pmatrix} 0\\0\\0\\i\end{pmatrix}.\]

Note that the action of $c_2S_1$ is identical to that of $c_1S_2$ from case (iii), and so the matrix representation of $c_2S_1$ is also the same:
\[c_2S_1=\begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
0&0&1&0\\
0&0&0&i
\end{pmatrix}.\]

Here, the $4\times4$ matrix corresponding to the following quantum circuit will be given:

where $S$ is defined as it was above, and the last two-qubit gate denoted by $SWAP$ transposes the two qubits (more precisely, the $SWAP$ gate maps $\ket{00}\mapsto\ket{00}, \ket{01}\mapsto\ket{10}, \ket{10}\mapsto\ket{01},\ \text{and}\ \ket{11}\mapsto\ket{11}$).


Denote the overall action of this circuit by the unitary operator $U$. In order to express the action of $U$ as a matrix, first observe how $U$ acts on the four computational basis states:

\[\begin{array}{rcl}
\ket{00} &\overset{H\otimes I}\mapsto&\super{\ket{00}+\ket{10}} \\
&\overset{c_1S_2}\mapsto&\super{\ket{00}+\ket{10}} \\
&\overset{I\otimes H}\mapsto&\frac{1}{2}(\ket{00}+\ket{01}+\ket{10}+\ket{11}) \\
&\overset{SWAP}\mapsto&\frac{1}{2}(\ket{00}+\ket{10}+\ket{01}+\ket{11})
\end{array}
\implies U\begin{pmatrix}1\\0\\0\\0\end{pmatrix}=\frac{1}{2}\begin{pmatrix}1\\1\\1\\1\end{pmatrix},\]

\[\begin{array}{rcl}
\ket{01} &\overset{H\otimes I}\mapsto&\super{\ket{01}+\ket{11}} \\
&\overset{c_1S_2}\mapsto&\super{\ket{01}+i\ket{11}} \\
&\overset{I\otimes H}\mapsto&\frac{1}{2}(\ket{00}-\ket{01}+i\ket{10}-i\ket{11}) \\
&\overset{SWAP}\mapsto&\frac{1}{2}(\ket{00}-\ket{10}+i\ket{01}-i\ket{11})
\end{array}
\implies U\begin{pmatrix}0\\1\\0\\0\end{pmatrix}=\frac{1}{2}\begin{pmatrix}1\\i\\-1\\-i\end{pmatrix},\]

\[\begin{array}{rcl}
\ket{10} &\overset{H\otimes I}\mapsto&\super{\ket{00}-\ket{10}} \\
&\overset{c_1S_2}\mapsto&\super{\ket{00}-\ket{10}} \\
&\overset{I\otimes H}\mapsto&\frac{1}{2}(\ket{00}+\ket{01}-\ket{10}-\ket{11}) \\
&\overset{SWAP}\mapsto&\frac{1}{2}(\ket{00}+\ket{10}-\ket{01}-\ket{11})
\end{array}
\implies U\begin{pmatrix}0\\0\\1\\0\end{pmatrix}=\frac{1}{2}\begin{pmatrix}1\\-1\\1\\-1\end{pmatrix},\]

\[\begin{array}{rcl}
\ket{11} &\overset{H\otimes I}\mapsto&\super{\ket{01}-\ket{11}} \\
&\overset{c_1S_2}\mapsto&\super{\ket{01}-i\ket{11}} \\
&\overset{I\otimes H}\mapsto&\frac{1}{2}(\ket{00}-\ket{01}-i\ket{10}+i\ket{11}) \\
&\overset{SWAP}\mapsto&\frac{1}{2}(\ket{00}-\ket{10}-i\ket{01}+i\ket{11})
\end{array}
\implies U\begin{pmatrix}1\\0\\0\\0\end{pmatrix}=\frac{1}{2}\begin{pmatrix}1\\-i\\-1\\i\end{pmatrix}.\]

Then the matrix constructed that contains the four output vectors as its columns gives the matrix representation of the unitary operation $U$ given by the circuit:
\[U=\frac{1}{2}\begin{pmatrix}
1&1&1&1\\
1&i&-1&-i\\
1&-1&1&-1\\
1&-i&-1&i
\end{pmatrix}.\]

Entangled vs. Seperable states

If possible, each two-qubit state given below will be expressed as a product of two one-qubit states. Otherwise, it will be shown that such a factorization is impossible (in this case, the qubits are said to be entangled).


Case (i):
$\ket{\psi}=\frac{1}{2}\ket{00}+\frac{i}{2}\ket{01}-\frac{1}{2}\ket{10}-\frac{i}{2}\ket{11}$


Consider the one-qubit states $\ket{\phi_1}=\frac{1}{\sqrt2}\ket{0}-\frac{1}{\sqrt2}\ket{1}$ and $\ket{\phi_2}=\frac{1}{\sqrt2}\ket{0}+\frac{i}{\sqrt2}\ket{1}$. Then expanding the tensor product of the two states $\ket{\phi_1}\otimes\ket{\phi_2}=\ket{\phi_1}\ket{\phi_2}$ yields:
\[\begin{array}{rcl}\ket{\phi_1}\ket{\phi_2}&=&(\frac{1}{\sqrt2}\ket{0}-\frac{1}{\sqrt2}\ket{1})(\frac{1}{\sqrt2}\ket{0}+\frac{i}{\sqrt2}\ket{1}) \\
\\
&=&\frac{1}{\sqrt2}\frac{1}{\sqrt2}\ket{0}\ket{0}+\frac{1}{\sqrt2}\frac{i}{\sqrt2}\ket{0}\ket{1}-\frac{1}{\sqrt2}\frac{1}{\sqrt2}\ket{1}\ket{0}-\frac{1}{\sqrt2}\frac{i}{\sqrt2}\ket{1}\ket{1} \\
\\
&=&\frac{1}{2}\ket{00}+\frac{i}{2}\ket{01}-\frac{1}{2}\ket{10}-\frac{i}{2}\ket{11}.
\end{array}\]
Thus, $\ket{\psi}=\ket{\phi_1}\ket{\phi_2}$ can be expressed as the tensor product of two one-qubit states and is therefore a separable state.


Case (ii):

$\ket{\psi}=\frac{1}{2}\ket{00}+\frac{1}{2}\ket{01}+\frac{1}{2}\ket{10}-\frac{1}{2}\ket{11}$

It will be shown that $\ket{\psi}$ is an entangled state. For the sake of contradiction, suppose that $\ket{\psi}$ can be written as the tensor product of two one-qubit states expressed in their general form $\ket{\phi_1}=\alpha\ket{0}+\beta\ket{1}$ and $\ket{\phi_2}=\alpha'\ket{0}+\beta'\ket{1}$, where $\alpha,\beta,\alpha',\beta'\in\mathbb{C}$. Then,
\[\begin{array}{rcl}
\ket{\psi}&=&\ket{\phi_1}\ket{\phi_2} \\
\\
&=&(\alpha\ket{0}+\beta\ket{1})(\alpha'\ket{0}+\beta'\ket{1}) \\
\\
&=&\alpha\alpha'\ket{00}+\alpha\beta'\ket{01}+\beta\alpha'\ket{10}+\beta\beta'\ket{11}
\end{array}\]
Now compare these amplitudes to those actually provided in $\ket{\psi}$:
\[\alpha\alpha'=\frac{1}{2}, \alpha\beta'=\frac{1}{2}, \beta\beta'=\frac{1}{2}, \beta\beta'=\frac{-1}{2}.\]
Since these products are all nonzero numbers and $\alpha,\beta,\alpha',\beta'\in\mathbb{C}$, this implies that $\alpha,\beta,\alpha',\beta'\neq 0$. Consider the following relationships which must also hold:
\[\begin{array}{rl}
&\alpha\alpha'-\alpha\beta'=\frac{1}{2}-\frac{1}{2}=0\\
\implies&\alpha(\alpha'-\beta')=0 \\
\implies&\alpha'=\beta',
\end{array}\]
and likewise
\[\begin{array}{rl}
&\beta\alpha'+\beta\beta'=\frac{1}{2}+\frac{-1}{2}=0\\
\implies&\beta(\alpha'+\beta')=0 \\
\implies&\alpha'=-\beta',
\end{array}\]
but then $\beta'=-\beta'$ implies that $\beta'=0$ which contradicts the fact that $\beta'\neq0$. Therefore, the two-qubit state $\ket{\psi}$ cannot be expressed as the tensor product of two one-qubit states, and must be entangled.


Case (iii):
$\ket{\psi}=\frac{9}{25}\ket{00}+\frac{12}{25}\ket{01}+\frac{12}{25}\ket{10}-\frac{16}{25}\ket{11}$


Consider the two identical one-qubit states $\ket{\phi_1}=\ket{\phi_2}=\frac{3}{5}\ket{0}+\frac{4}{5}\ket{1}$. Then expanding the tensor product of the two states $\ket{\phi_1}\otimes\ket{\phi_2}=\ket{\phi_1}\ket{\phi_2}$ yields:
\[\begin{array}{rcl}\ket{\phi_1}\ket{\phi_2}&=&(\frac{3}{5}\ket{0}+\frac{4}{5}\ket{1})(\frac{3}{5}\ket{0}+\frac{4}{5}\ket{1}) \\
\\
&=&\frac{3}{5}\frac{3}{5}\ket{0}\ket{0}+\frac{3}{5}\frac{4}{5}\ket{0}\ket{1}+\frac{4}{5}\frac{3}{5}\ket{1}\ket{0}+\frac{4}{5}\frac{4}{5}\ket{1}\ket{1} \\
\\
&=&\frac{9}{25}\ket{00}+\frac{12}{25}\ket{01}+\frac{2}{25}\ket{10}+\frac{16}{25}\ket{11}.
\end{array}\]
Thus, $\ket{\psi}=\ket{\phi_1}\ket{\phi_2}$ can be expressed as the tensor product of two one-qubit states and is therefore a separable state.

Distinguishing between pairs of quantum states

 In each of the following cases,  we will suppose that one of two single qubit states $\ket{a}$ and $\ket{b}$ is selected randomly with probability $1/2$, but we are not told which. The goal is to guess which state was selected with as high a probability as we can achieve. What will be described is a distinguishing procedure in the form of a unitary operation followed by a measurement in the computational basis, and its success probability.

CASE: (i)
$\ket{a}=\ket{0}$ and $\ket{b}=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$

The inner product of the two states $\ket{a}$ and $\ket{b}$ is:
\[\ip{a}{b}=\bra{0}\super{\ket{0}+\ket{1}}=\frac{1}{\sqrt{2}}(\ip{0}{0}+\ip{0}{1})=\frac{1}{\sqrt{2}},\]
since $\ip{i}{j}=\delta_{ij}$ for all $i,j\in\{0,1\}$. Then using the geometrical relation $\ip{a}{b}=\cos{\phi}$, where $\phi\in[0,2\pi)$ denotes the angle between the two states $\ket{a}$ and $\ket{b}$, it is seen that in this case
\[\phi=\arccos{\frac{1}{\sqrt{2}}}=\frac{\pi}{4}.\]
In general, two pure states can only be perfectly distinguished if they are orthogonal. That is, if $\phi=\frac{\pi}{2},\frac{3\pi}{2}$. Therefore, in this case the two states $\ket{a}$ and $\ket{b}$ cannot be perfectly distinguished.

Consider the unitary operation $R$ that rotates states by $\theta=\frac{\pi}{8}$ given by:
\[
R=\begin{pmatrix}
\cos{\frac{\pi}{8}}&-\sin{\frac{\pi}{8}} \\
\sin{\frac{\pi}{8}}&\cos{\frac{\pi}{8}}
\end{pmatrix}
\]
Then applying $R$ to the two computational basis states $\ket{0}$ and $\ket{1}$ gives:
\[\begin{array}{rcl}
R\ket{0}&=&\cos{\frac{\pi}{8}}\ket{0}+\sin{\frac{\pi}{8}}\ket{1}\\
R\ket{1}&=&-\sin{\frac{\pi}{8}}\ket{0}+\cos{\frac{\pi}{8}}\ket{1}
\end{array}\]

Therefore, applying $R$ to the states $\ket{a}$ and $\ket{b}$ yields:
\[\begin{array}{rcl}
R\ket{a}=R\ket{0}&=&\cos{\frac{\pi}{8}}\ket{0}+\sin{\frac{\pi}{8}}\ket{1},\\
R\ket{b}=\frac{1}{\sqrt{2}}R(\ket{0}+\ket{1})
&=&\frac{1}{\sqrt{2}}(\cos{\frac{\pi}{8}}\ket{0}+\sin{\frac{\pi}{8}}\ket{1}-\sin{\frac{\pi}{8}}\ket{0}+\cos{\frac{\pi}{8}}\ket{1})\\
&=&\frac{1}{\sqrt{2}}((\cos{\frac{\pi}{8}}-\sin{\frac{\pi}{8}})\ket{0}+(\cos{\frac{\pi}{8}}+\sin{\frac{\pi}{8}})\ket{1})
\end{array}\]
Since $R$ is unitary the inner product of $R\ket{a}$ and $R\ket{b}$ is preserved, and also the angle $\phi=\frac{\pi}{4}$ between the states is preserved.

 When either $R\ket{a}$ or $R\ket{b}$ are measured in the computational basis what will result is one of the basis states $\ket{0}$ or $\ket{1}$, but with certain probability. If the state happened to be $R\ket{a}$, then the probability of observing $\ket{0}$ and $\ket{1}$ is $\cos^2{\frac{\pi}{8}}$ and $\sin^2{\frac{\pi}{8}}$, respectively. If instead the state $R\ket{b}$ was measured, the probability of observing $\ket{0}$ would be $\sin^2{\frac{\pi}{8}}$, and the probability of observing $\ket{1}$ would be $\cos^2{\frac{\pi}{8}}$.

 Thus when either $\ket{a}$ or $\ket{b}$ is given uniformly at random, first apply $R$ to the state and then measure. If $\ket{0}$ is observed guess the state $\ket{a}=\ket{0}$, and if the state $\ket{b}$ is observed guess the state $\ket{b}=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$.

 The probability of guessing the state correctly is given by $\frac{1}{2}(1+\sin{\phi})$, where $\phi=\arccos({\ip{a}{b}})$ is the angle between the states. In this case, with $\phi=\frac{\pi}{4}$, the probability of successfully guessing the correct state is $\frac{1}{2}(1+\sin{\frac{\pi}{4}})\approx .50$.



Case: (ii)

 $\ket{a}=\super{\ket{0}+i\ket{1}}$ and $\ket{b}=\super{i\ket{0}+\ket{1}}$

Consider the inner product between $\ket{a}$ and $\ket{b}$:
\[\ip{a}{b}=(\super{\bra{0}-i\bra{1}})(\super{i\ket{0}+\ket{1}})=\frac{1}{2}(i\ip{0}{0}+\ip{0}{1}+\ip{1}{0}-i\ip{1}{1})=\frac{i}{2}-\frac{i}{2}=0\]
Hence, the two states are orthogonal so the angle between them is $\phi=\frac{\pi}{2}$. There must exist a unitary transformation $U$ that maps these two states to the computational basis states $\ket{0}$ and $\ket{1}$. Consider the following unitary map:
\[
U=\frac{1}{\sqrt{2}}\begin{pmatrix}
1&-i \\
i&-1\end{pmatrix},\]
and observe that
\[
U\ket{a}=\frac{1}{\sqrt{2}}\begin{pmatrix}
1&-i \\
i&-1\end{pmatrix}
\begin{pmatrix}
\frac{1}{\sqrt{2}}\\
\frac{i}{\sqrt{2}}
\end{pmatrix}=
\begin{pmatrix}
1\\
0
\end{pmatrix},\]
\[U\ket{b}=\frac{1}{\sqrt{2}}\begin{pmatrix}
1&-i \\
i&-1\end{pmatrix}
\begin{pmatrix}
\frac{i}{\sqrt{2}}\\
\frac{1}{\sqrt{2}}
\end{pmatrix}=
\begin{pmatrix}
0\\
1
\end{pmatrix},
\]
Then by applying the unitary operation $U$ to either of the states $\ket{a}$ or $\ket{b}$ chosen uniformly at random, and then measuring in the computational basis, either the state $\ket{0}$ or $\ket{1}$ will be observed with certainty. If $\ket{0}$ is observed, then the original state was $\ket{a}=\super{\ket{0}+i\ket{1}}$. Otherwise, if the state $\ket{1}$ was observed, then the original state was $\ket{b}=\super{i\ket{0}+\ket{1}}$. Since these states are orthogonal, the probability of success with the procedure is $1$.



Case: (iii)
$\ket{a}=\cos\theta\ket{0}+\sin\theta\ket{1}$ and $\ket{b}=\cos\theta\ket{0}-\sin\theta\ket{1}$, where $\theta\in[0,2\pi)$ is known.


The inner product of the states $\ket{a}$ and $\ket{b}$ is given by:
\[\begin{array}{rcl}\ip{a}{b}&=&(\cos\theta\bra{0}+\sin\theta\bra{1})(\cos\theta\ket{0}-\sin\theta\ket{1})\\
&=&\cos^2{\theta}\ip{0}{0}+\cos{\theta}\sin{\theta}\ip{0}{1}-(\sin{\theta}\cos{\theta}\ip{1}{0}+\sin^2{\theta}\ip{1}{1} \\
&=&\cos^2{\theta}-\sin^2{\theta} \\
&=&\cos{2\theta}
\end{array}\]

Therefore the angle between the two states is $\phi=2\theta$. If $\theta=0$, then $\phi=2\theta=0$ and the states are actually the same. In this case, there is no improved way of distinguishing between the two states besides merely guessing with a $50/50$ chance. Otherwise, consider the unitary operator $R$ that performs a rotation by $\pi/4$:
\[R=\begin{pmatrix}\cos{\frac{\pi}{4}}&-\sin{\frac{\pi}{4}} \\
\sin{\frac{\pi}{4}}&\cos{\frac{\pi}{4}}
\end{pmatrix}\]

Geometrical considerations show that applying $R$ to the states $\ket{a}$ and $\ket{b}$ yields:
\[\begin{array}{rcl}R\ket{a}&=&\cos{(\theta-\pi/4)}\ket{0}+\sin{(\theta-\pi/4)}\ket{1},\\
R\ket{b}&=&\cos{(\theta+\pi/4)}\ket{0}+\sin{(\theta+\pi/4)}\ket{1}.
\end{array}\]
Then if $R\ket{a}$ is measured in the computation basis,$\ket{0} $will be observed with probability $\cos^2{(\theta-\pi/4)}$ and $\ket{1}$ will be observed with probability $\sin^2{(\theta-\pi/4)}$. On the other hand, if the state $R\ket{b}$ is measured, the states $\ket{0}$ and $\ket{1}$ will be observed with probability $\cos^2{(\theta+\pi/4)}$ and $\sin^2{(\theta+\pi/4)}$, respectively.

Therefore, for $0\leq\theta\leq\pi/2$ or $\pi\leq\theta\leq3\pi/2$, if the state $\ket{0}$ is observed, guess that the original state was $\ket{a}$. For $\pi/2\leq\theta\leq\pi/2$ or $3\pi/2\leq\theta\leq2\pi$, if $\ket{1}$ is observed, then guess that the original state was $\ket{b}$. This method has a probability of success given by $P=\frac{1}{2}(1+\sin{(2\theta)})$.