\chapter{Quantum circuits}
Now that we've discussed qubits, we can talk about how to use them in circuits.
The key change --- and the reason that quantum circuits can do things that
classical circuits cannot --- is the fact that we are allowing
linear combinations of $0$ and $1$.

\section{Classical logic gates}
In classical logic, we build circuits which take in some bits for input,
and output some more bits for input.
These circuits are built out of individual logic gates.
For example, the \vocab{AND gate} can be pictured as follows.
\[
	\Qcircuit @C=0.8em @R=.7em {
		\lstick{0} &\qw & \multigate{1}{\textsc{and}} & \rstick{0} \qw \\
		\lstick{0} &\qw & \ghost{\textsc{and}} &
	}
	\hspace{4.5em}
	\Qcircuit @C=0.8em @R=.7em {
		\lstick{0} &\qw & \multigate{1}{\textsc{and}} & \rstick{0} \qw \\
		\lstick{1} &\qw & \ghost{\textsc{and}} &
	}
	\hspace{4.5em}
	\Qcircuit @C=0.8em @R=.7em {
		\lstick{1} &\qw & \multigate{1}{\textsc{and}} & \rstick{0} \qw \\
		\lstick{0} &\qw & \ghost{\textsc{and}} &
	}
	\hspace{4.5em}
	\Qcircuit @C=0.8em @R=.7em {
		\lstick{1} &\qw & \multigate{1}{\textsc{and}} & \rstick{1} \qw \\
		\lstick{1} &\qw & \ghost{\textsc{and}} &
	}
\]
One can also represent the AND gate using the ``truth table'':
\[
	\begin{array}{|cc|c|}
		\hline
		A & B & A \text{ and } B \\ \hline
		0 & 0 & 0 \\
		0 & 1 & 0 \\
		1 & 0 & 0 \\
		1 & 1 & 1 \\
		\hline
	\end{array}
\]
Similarly, we have the \vocab{OR gate} and the \vocab{NOT gate}:
\[
	\begin{array}{|cc|c|}
		\hline
		A & B & A \text{ or } B \\ \hline
		0 & 0 & 0 \\
		0 & 1 & 1 \\
		1 & 0 & 1 \\
		1 & 1 & 1 \\
		\hline
	\end{array}
	\qquad
	\begin{array}{|c|c|}
		\hline
		A & \text{not } A \\ \hline
		0 & 1 \\
		1 & 0 \\
		\hline
	\end{array}
\]
We also have a so-called \vocab{COPY gate}, which duplicates a bit.
\[
	\Qcircuit @C=0.8em @R=.7em {
		\lstick{0} & \qw & \multigate{1}{\textsc{copy}} & \rstick{0} \qw & \\
		&& & \rstick{0} \qw &
	}
	\qquad\qquad
	\Qcircuit @C=0.8em @R=.7em {
		\lstick{1} & \qw & \multigate{1}{\textsc{copy}} & \rstick{1} \qw & \\
		&& & \rstick{1} \qw &
	}
\]
Of course, the first theorem you learn about these gates is that:
\begin{theorem}
	[AND, OR, NOT, COPY are universal]
	The set of four gates AND, OR, NOT, COPY is universal in the sense that
	any boolean function $f : \{0,1\}^n \to \{0,1\}$
	can be implemented as a circuit using only these gates.
\end{theorem}
\begin{proof}
	Somewhat silly: we essentially write down a circuit that OR's across
	all input strings in $f\pre(1)$.
	For example, suppose we have $n=3$ and want to simulate the function
	$f(abc)$ with $f(011) = f(110) = 1$ and $0$ otherwise.
	Then the corresponding Boolean expression for $f$ is simply
	\[
		f(abc) =
		\left[ \text{(not $a$) and $b$ and $c$} \right]
		\text{ or }
		\left[ \text{$a$ and $b$ and (not $c$)} \right].
	\]
	Clearly, one can do the same for any other $f$,
	and implement this logic into a circuit.
\end{proof}
\begin{remark}
	Since
	$x \text{ and } y = \text{not } ( (\text{not $x$}) \text{ or } (\text{not $y$}))$,
	it follows that in fact, we can dispense with the AND gate.
\end{remark}

\section{Reversible classical logic}
\prototype{CNOT gate, Toffoli gate.}

For the purposes of quantum mechanics, this is not enough.
To carry through the analogy we in fact need gates that are \vocab{reversible},
meaning the gates are bijections from the input space to the output space.
In particular, such gates must take the same number of input and output gates.
\begin{example}[Reversible gates]
	\listhack
	\begin{enumerate}[(a)]
		\ii None of the gates AND, OR, COPY are reversible for dimension reasons.
		\ii The NOT gate, however, is reversible:
		it is a bijection $\{0,1\} \to \{0,1\}$.
	\end{enumerate}
\end{example}
\begin{example}
	[The CNOT gate]
	The controlled-NOT gate, or the \vocab{CNOT} gate,
	is a reversible $2$-bit gate with the following truth table.
	\[
		\begin{array}{|rr|rr|}
			 \hline
			 \multicolumn{2}{|c|}{\text{In}} & \multicolumn{2}{|c|}{\text{Out}} \\
			 \hline
			 0 & 0 & 0 & 0 \\
			 1 & 0 & 1 & 1 \\
			 0 & 1 & 0 & 1 \\
			 1 & 1 & 1 & 0 \\ \hline
		\end{array}
	\]
	In other words, this gate XOR's the first bit to the second bit,
	while leaving the first bit unchanged.
	It is depicted as follows.
	\[
		\Qcircuit @C=1em @R=.7em {
			\lstick{x} & \ctrl{1} & \rstick{x} \qw \\
			\lstick{y} & \targ & \rstick{x+y \mod 2} \qw
		}
	\]
	The first dot is called the ``control'',
	while the $\oplus$ is the ``negation'' operation:
	the first bit controls whether the second bit gets flipped or not.
	Thus, a typical application might be as follows.
	\[
		\Qcircuit @C=1em @R=.7em {
			\lstick{1} & \ctrl{1} & \rstick{1} \qw \\
			\lstick{0} & \targ & \rstick{1} \qw
		}
	\]
\end{example}
So, NOT and CNOT are the only nontrivial reversible gates on two bits.

We now need a different definition of universal for our reversible gates.
\begin{definition}
	A set of reversible gates can \vocab{simulate} a Boolean function $f(x_1 \dots x_n)$,
	if one can implement a circuit which takes
	\begin{itemize}
		\ii As input, $x_1 \dots x_n$ plus some fixed bits set to $0$ or $1$,
		called \vocab{ancilla bits}\footnote{%
			The English word ``ancilla'' means ``maid''.}.
		\ii As output, the input bits $x_1, \dots, x_n$,
		the output bit $f(x_1, \dots, x_n)$,
		and possibly some extra bits (called \vocab{garbage bits}).
	\end{itemize}
	The gate(s) are \vocab{universal} if they can simulate any Boolean function.
\end{definition}
For example, the CNOT gate can simulate the NOT gate,
using a single ancilla bit $1$,
according to the following circuit.
\[
	\Qcircuit @C=1em @R=.7em {
		\lstick{x} & \ctrl{1} & \rstick{x} \qw \\
		\lstick{1} & \targ & \rstick{\text{not } x} \qw
	}
\]
Unfortunately, it is not universal.
\begin{proposition}
	[CNOT $\not\Rightarrow$ AND]
	The CNOT gate cannot simulate the boolean function ``$x \text{ and } y$''.
\end{proposition}
\begin{proof}[Sketch of Proof]
	One can see that any function simulated using only CNOT gates
	must be of the form
	\[ a_1 x_1 + a_2 x_2 + \dots + a_n x_n \pmod 2 \]
	because CNOT is the map $(x,y) \mapsto (x, x+y)$.
	Thus, even with ancilla bits, we can only create functions
	of the form $ax+by+c \pmod 2$ for fixed $a$, $b$, $c$.
	The AND gate is not of this form.
\end{proof}

So, we need at least a three-qubit gate.
The most commonly used one is:
\begin{definition}
	The three-bit \vocab{Toffoli gate}, also called the CCNOT gate, is given by
	\[
		\Qcircuit @C=1em @R=.7em {
			\lstick{x} & \ctrl{1} & \rstick{x} \qw \\
			\lstick{y} & \ctrl{1} & \rstick{y} \qw \\
			\lstick{z} & \targ & \rstick{z + xy \pmod 2} \qw
		}
	\]
	So the Toffoli has two controls, and toggles the last bit if and only if
	both of the control bits are $1$.
\end{definition}
This replacement is sufficient.
\begin{theorem}
	[Toffoli gate is universal]
	The Toffoli gate is universal.
\end{theorem}
\begin{proof}
	We will show it can \emph{reversibly} simulate
	AND, NOT, hence OR,
	which we know is enough to show universality.
	(We don't need COPY because of reversibility.)

	For the AND gate, we draw the circuit
	\[
		\Qcircuit @C=1em @R=.7em {
			\lstick{x} & \ctrl{1} & \rstick{x} \qw \\
			\lstick{y} & \ctrl{1} & \rstick{y} \qw \\
			\lstick{0} & \targ & \rstick{x \text{ and } y} \qw
		}
	\]
	with one ancilla bit, and no garbage bits.

	For the NOT gate, we use two ancilla $1$ bits and one garbage bit:
	\[
		\Qcircuit @C=1em @R=.7em {
			\lstick{1} & \ctrl{1} & \rstick{1} \qw \\
			\lstick{z} & \ctrl{1} & \rstick{z} \qw \\
			\lstick{1} & \targ & \rstick{\text{not } z} \qw
		}
	\]
	This completes the proof.
\end{proof}

Hence, in theory we can create any classical circuit we desire
using the Toffoli gate alone.
Of course, this could require exponentially many gates for even the
simplest of functions.
Fortunately, this is NO BIG DEAL because I'm a math major,
and having $2^n$ gates is a problem best left for the CS majors.

\section{Quantum logic gates}
In quantum mechanics, since we can have \emph{linear combinations} of basis
elements, our logic gates will instead consist of \emph{linear maps}.
Moreover, in quantum computation, gates are always reversible,
which was why we took the time in the previous section to show
that we can still simulate any function when restricted to reversible gates
(e.g.\ using the Toffoli gate).

First, some linear algebra:
\begin{definition}
	Let $V$ be a finite dimensional inner product space.
	Then for a map $U : V \to V$, the following are equivalent:
	\begin{itemize}
		\ii $\left< U(x), U(y) \right> = \left< x,y \right>$ for $x,y \in V$.
		\ii $U^\dagger$ is the inverse of $U$.
		\ii $\norm{x} = \norm{U(x)}$ for $x \in V$.
	\end{itemize}
	The map $U$ is called \vocab{unitary}
	if it satisfies these equivalent conditions.
\end{definition}

Then
\begin{moral}
	Quantum logic gates are unitary matrices.
\end{moral}
In particular, unlike the classical situation,
quantum gates are always reversible
(and hence they always take the same number of input and output bits).

For example, consider the CNOT gate.
Its quantum analog should be a unitary map $\UCNOT : H \to H$,
where $H = \CC^{\oplus 2} \otimes \CC^{\oplus 2}$,
given on basis elements by
\[
	\UCNOT(\ket{00}) = \ket{00}, \quad
	\UCNOT(\ket{01}) = \ket{01}
\]
\[
	\UCNOT(\ket{10}) = \ket{11}, \quad
	\UCNOT(\ket{11}) = \ket{10}.
\]
So pictorially, the quantum CNOT gate is given by
\[
	\Qcircuit @C=0.8em @R=.7em {
		\lstick{\ket0} & \ctrl{1} & \rstick{\ket0} \qw \\
		\lstick{\ket0} & \targ & \rstick{\ket0} \qw \\
	}
	\hspace{6em}
	\Qcircuit @C=0.8em @R=.7em {
		\lstick{\ket0} & \ctrl{1} & \rstick{\ket0} \qw \\
		\lstick{\ket1} & \targ & \rstick{\ket1} \qw \\
	}
	\hspace{6em}
	\Qcircuit @C=0.8em @R=.7em {
		\lstick{\ket1} & \ctrl{1} & \rstick{\ket1} \qw \\
		\lstick{\ket0} & \targ & \rstick{\ket1} \qw \\
	}
	\hspace{6em}
	\Qcircuit @C=0.8em @R=.7em {
		\lstick{\ket1} & \ctrl{1} & \rstick{\ket1} \qw \\
		\lstick{\ket1} & \targ & \rstick{\ket0} \qw \\
	}
\]
OK, so what?
The whole point of quantum mechanics is that we allow linear
qubits to be in linear combinations of $\ket0$ and $\ket1$,
too, and this will produce interesting results.
For example, let's take $\xdown = \frac{1}{\sqrt2} (\ket0-\ket1)$
and plug it into the top, with $\ket 1$ on the bottom, and see what happens:
\[
	\UCNOT \left( \xdown \otimes \ket1 \right)
	= \UCNOT \left( \frac{1}{\sqrt2} (\ket{01}-\ket{11}) \right)
	= \frac{1}{\sqrt2} \left( \ket{01}-\ket{10} \right)
	= \ket{\Psi_-}
\]
which is the fully entangled \emph{singlet state}! Picture:
\[
	\Qcircuit @C=0.8em @R=.7em {
		\lstick{\xdown} & \ctrl{1} & \rstick{\ket{\Psi_-}} \qw \\
		\lstick{\ket1} & \targ & \rstick{} \qw \\
	}
\]

Thus, when we input mixed states into our quantum gates,
the outputs are often entangled states,
even when the original inputs are not entangled.

\begin{example}
	[More examples of quantum gates]
	\listhack
	\begin{enumerate}[(a)]
		\ii Every reversible classical gate that we encountered before
		has a quantum analog obtained in the same way as CNOT:
		by specifying the values on basis elements.
		For example, there is a quantum Tofolli gate which
		for example sends
		\[
			\Qcircuit @C=0.8em @R=.7em {
				\lstick{\ket1} & \ctrl{1} & \rstick{\ket1} \qw \\
				\lstick{\ket1} & \ctrl{1} & \rstick{\ket1} \qw \\
				\lstick{\ket0} & \targ & \rstick{\ket1} \qw.
			}
		\]
		\ii The \vocab{Hadamard gate} on one qubit is a rotation given by
		\[
			\begin{bmatrix}
				\frac{1}{\sqrt2} & \frac{1}{\sqrt2} \\
				\frac{1}{\sqrt2} & -\frac{1}{\sqrt2}
			\end{bmatrix}.
		\]
		Thus, it sends $\ket0$ to $\xup$ and $\ket1$ to $\xdown$.
		Note that the Hadamard gate is its own inverse.
		It is depicted by an ``$H$'' box.
		\[
			\Qcircuit @C=0.8em @R=.7em {
				\lstick{\ket0} & \gate{H} & \rstick{\xup} \qw
			}
		\]
		\ii More generally, if $U$ is a $2 \times 2$ unitary matrix
		(i.e.\ a map $\CC^{\oplus 2} \to \CC^{\oplus 2}$) then
		there is \vocab{$U$-rotation gate} similar to the previous one,
		which applies $U$ to the input.
		\[
			\Qcircuit @C=0.8em @R=.7em {
				\lstick{\ket\psi} & \gate{U} & \rstick{U\ket\psi} \qw
			}
		\]
		For example, the classical NOT gate is represented by $U = \sigma_x$.
		\ii A \vocab{controlled $U$-rotation gate} generalizes the CNOT gate.
		Let $U : \CC^{\oplus 2} \to \CC^{\oplus 2}$ be a rotation gate,
		and let $H = \CC^{\oplus 2} \otimes \CC^{\oplus 2}$ be a $2$-qubit space.
		Then the controlled $U$ gate has the following circuit diagrams.
		\[
			\Qcircuit @C=0.8em @R=.7em {
				\lstick{\ket0} & \ctrl{1} & \rstick{\ket0} \qw \\
				\lstick{\ket\psi} & \gate{U} & \rstick{\ket\psi} \qw
			}
			\hspace{8em}
			\Qcircuit @C=0.8em @R=.7em {
				\lstick{\ket1} & \ctrl{1} & \rstick{\ket1} \qw \\
				\lstick{\ket\psi} & \gate{U} & \rstick{U\ket\psi} \qw
			}
		\]
		Thus, $U$ is applied when the controlling bit is $1$,
		and CNOT is the special case $U = \sigma_x$.  As before,
		we get interesting behavior if the control is mixed.
	\end{enumerate}
\end{example}

And now, some more counterintuitive quantum behavior.
Suppose we try to use CNOT as a copy, with truth table.
\[
	\begin{array}{|rr|rr|}
		 \hline
		 \multicolumn{2}{|c|}{\text{In}} & \multicolumn{2}{|c|}{\text{Out}} \\
		 \hline
		 0 & 0 & 0 & 0 \\
		 1 & 0 & 1 & 1 \\
		 0 & 1 & 0 & 1 \\
		 1 & 1 & 1 & 0 \\ \hline
	\end{array}
\]
The point of this gate is to be used with a garbage $0$ at the bottom
to try and simulate a ``copy'' operation.
So indeed, one can check that
\[
	\Qcircuit @C=0.8em @R=.7em {
		\lstick{\ket0} & \multigate{1}{U} & \rstick{\ket0} \qw \\
		\lstick{\ket0} & \ghost{U} & \rstick{\ket0} \qw
	}
	\hspace{8em}
	\Qcircuit @C=0.8em @R=.7em {
		\lstick{\ket1} & \multigate{1}{U} & \rstick{\ket1} \qw \\
		\lstick{\ket0} & \ghost{U} & \rstick{\ket1} \qw
	}
\]
Thus we can copy $\ket0$ and $\ket1$.
But as we've already seen if we input $\xdown \otimes \ket0$ into $U$,
we end up with the entangled state $\ket{\Psi_-}$
which is decisively \emph{not} the $\xdown \otimes \xdown$ we wanted.
And in fact, the so-called \vocab{no-cloning theorem} implies
that it's impossible to duplicate an arbitrary $\ket\psi$;
the best we can do is copy specific orthogonal states as in the classical case.
See also \Cref{prob:baby_no_clone}.

\section{Deutsch-Jozsa algorithm}
The Deutsch-Jozsa algorithm is the first example of a nontrivial
quantum algorithm which cannot be performed classically:
it is a ``proof of concept'' that would later inspire Grover's search algorithm
and Shor's factoring algorithm.

The problem is as follows: we're given a function $f : \{0,1\}^n \to \{0,1\}$,
and promised that the function $f$ is either
\begin{itemize}
	\ii A constant function, or
	\ii A balanced function, meaning that exactly half the inputs map to
	$0$ and half the inputs map to $1$.
\end{itemize}
The function $f$ is given in the form of a reversible black box $U_f$ which
is the control of a NOT gate, so it can be represented as the circuit diagram
\[
	\Qcircuit @C=1em @R=0.7em {
		\lstick{\ket{x_1x_2 \dots x_n}} & /^n \qw & \multigate{1}{U_f} &
			\rstick{\ket{x_1x_2\dots x_n}} \qw \\
		\lstick{\ket{y}} & \qw & \ghost{U_f} & \rstick{\ket{y+f(x) \mod 2}}\qw \\
	}
\]
i.e.\ if $f(x_1, \dots, x_n) = 0$ then the gate does nothing,
otherwise the gate flips the $y$ bit at the bottom.
The slash with the $n$ indicates that the top of the input really consists
of $n$ qubits, not just the one qubit drawn,
and so the black box $U_f$ is a map on $n+1$ qubits.

The problem is to determine,
with as few calls to the black box $U_f$ as possible,
whether $f$ is balanced or constant.

\begin{ques}
	Classically, show that in the worst case we may need
	up to $2^{n-1}+1$ calls to the function $f$ to answer the question.
\end{ques}

So with only classical tools, it would take $O(2^n)$ queries to determine
whether $f$ is balanced or constant.
However,
\begin{theorem}
	[Deutsch-Jozsa]
	The Deutsch-Jozsa problem can be determined in a quantum circuit
	with only a single call to the black box.
\end{theorem}
\begin{proof}
	For concreteness, we do the case $n=1$ explicitly;
	the general case is contained in \Cref{prob:deutsch_jozsa}.
	We claim that the necessary circuit is
	\[
		\Qcircuit @C=1em @R=0.7em {
			\lstick{\ket0} & \gate{H} & \multigate{1}{U_f} & \gate{H} & \meter \qw \\
			\lstick{\ket1} & \gate{H} & \ghost{U_f} & \qw & \\
		}
	\]
	Here the $H$'s are Hadamard gates,
	and the meter at the end of the rightmost wire
	indicates that we make a measurement along the usual $\ket0$, $\ket1$ basis.
	This is not a typo! Even though classically the top wire is just
	a repeat of the input information,
	we are about to see that it's the top we want to measure.

	Note that after the two Hadamard operations, the state we get is
	\begin{align*}
		\ket{01} &\xmapsto{H^{\otimes 2}}
		\left( \frac{1}{\sqrt2}(\ket0+\ket1) \right)
		\otimes
		\left( \frac{1}{\sqrt2}(\ket0-\ket1) \right) \\
		&=
		\half \Big( \ket0\otimes\big(\ket0-\ket1\big)
		\; + \; \ket1\otimes\big(\ket0-\ket1\big) \Big).
	\end{align*}
	So after applying $U_f$, we obtain
	\[
		\half\Big(
		\ket0\otimes\big(\ket{0+f(0)}-\ket{1+f(0)}\big)
		\; + \; \ket1\otimes\big(\ket{0+f(1)}-\ket{1+f(1)}\big)
		\Big)
	\]
	where the modulo $2$ has been left implicit.
	Now, observe that the effect of going from
	$\ket0-\ket1$ to $\ket{0+f(x)}-\ket{1+f(x)}$ is merely
	to either keep the state the same (if $f(x)=0$)
	or to negate it (if $f(x)=1$).
	So we can simplify and factor to get
	\[
		\half
		\left( (-1)^{f(0)}\ket0 + (-1)^{f(1)}\ket1 \right)
		\otimes
		\left( \ket0-\ket1 \right).
	\]
	Thus, the picture so far is:
	\[
		\Qcircuit @C=1em @R=0.7em {
			\lstick{\ket0} & \gate{H} & \multigate{1}{U_f} &
				\rstick{\frac{1}{\sqrt2}%
				\Big((-1)^{f(0)}\ket0+(-1)^{f(1)}\ket1\Big)} \qw \\
			\lstick{\ket1} & \gate{H} & \ghost{U_f} &
				\rstick{\frac{1}{\sqrt2}(\ket0-\ket1)} \qw
		}
	\]
	In particular, the resulting state is not entangled,
	and we can simply discard the last qubit (!).
	Now observe:
	\begin{itemize}
		\ii If $f$ is constant, then the upper-most state is $\pm\xup$.
		\ii If $f$ is balanced, then the upper-most state is $\pm\xdown$.
	\end{itemize}
	So simply doing a measurement along $\sigma_x$ will give us the answer.
	Equivalently, perform another $H$ gate
	(so that $H\xup = \ket0$, $H\xdown = \ket1$)
	and measuring along $\sigma_z$ in the usual $\ket0$, $\ket1$ basis.
	Thus for $n=1$ we only need a single call to the oracle.
\end{proof}


\section\problemhead
\begin{problem}[Fredkin gate]
	The \vocab{Fredkin gate} (also called the controlled swap, or CSWAP gate)
	is the three-bit gate with the following truth table:
	\[
	\begin{array}{|rrr|rrr|}
		 \hline
		 \multicolumn{3}{|c|}{\text{In}} & \multicolumn{3}{|c|}{\text{Out}} \\
		 \hline
		 0 & 0 & 0 & 0 & 0 & 0 \\
		 0 & 0 & 1 & 0 & 0 & 1 \\
		 0 & 1 & 0 & 0 & 1 & 0 \\
		 0 & 1 & 1 & 0 & 1 & 1 \\
		 1 & 0 & 0 & 1 & 0 & 0 \\
		 1 & 0 & 1 & 1 & 1 & 0 \\
		 1 & 1 & 0 & 1 & 0 & 1 \\
		 1 & 1 & 1 & 1 & 1 & 1 \\\hline
	 \end{array}
	\]
	Thus the gate swaps the last two input bits whenever the first bit is $1$.
	Show that this gate is also reversible and universal.
	\begin{hint}
		One way is to create CCNOT using a few Fredkin gates.
	\end{hint}
	\begin{sol}
		To show the Fredkin gate is universal
		it suffices to reversibly create a CCNOT gate with it.
		We write the system
		\begin{align*}
			(z,\neg z,-) &= \opname{Fred}(z,1,0) \\
			(x,a,-) &= \opname{Fred}(x,1,0) \\
			(y,b,-) &= \opname{Fred}(y,a,0) \\
			(-,c,-) &= \opname{Fred}(b,0,1) \\
			(-,d,-) &= \opname{Fred}(c, z, \neg z).
		\end{align*}
		Direct computation shows that $d = z+xy\pmod 2$.
	\end{sol}
\end{problem}

\begin{problem}
	[Baby no-cloning theorem]
	\label{prob:baby_no_clone}
	Show that there is no unitary map $U$ on two qubits
	which sends $U(\ket\psi \otimes \ket0) = \ket\psi \otimes \ket\psi$
	for any qubit $\ket\psi$, i.e.\
	the following circuit diagram is impossible.
	\[
	\Qcircuit @C=0.8em @R=.7em {
		\lstick{\ket\psi} & \multigate{1}{U} & \rstick{\ket\psi} \qw \\
		\lstick{\ket0} & \ghost{U} & \rstick{\ket\psi} \qw
	}
	\]
	\begin{hint}
		Plug in $\ket\psi=\ket0$, $\ket\psi=\ket1$, $\ket\psi = \xup$
		and derive a contradiction.
	\end{hint}
\end{problem}

\begin{problem}[Deutsch-Jozsa]
	\label{prob:deutsch_jozsa}
	Given the black box $U_f$ described in the Deutsch-Jozsa algorithm,
	consider the following circuit.
	\[
		\Qcircuit @C=1em @R=0.7em {
			\lstick{\ket{0\dots0}} & /^n \qw & \gate{H^{\otimes n}} & \multigate{1}{U_f}
				& \gate{H^{\otimes n}} & \meter \qw \\
			\lstick{\ket1} & \qw & \gate{H} & \ghost{U_f} & \qw & \\
		}
	\]
	That is, take $n$ copies of $\ket 0$, apply the Hadamard rotation to all of them,
	apply $U_f$, reverse the Hadamard to all $n$ input bits
	(again discarding the last bit), then measure all $n$ bits
	in the $\ket0$/$\ket1$ basis (as in \Cref{ex:simult_measurement}).

	Show that the probability of measuring $\ket{0\dots0}$
	is $1$ if $f$ is constant and $0$ if $f$ is balanced.
	\begin{hint}
		First show that the box sends
		$\ket{x_1} \otimes \dots \otimes \ket{x_m} \otimes \xdown$
		to $(-1)^{f(x_1, \dots, x_m)}
		(\ket{x_1} \otimes \dots \otimes \ket{x_m} \otimes \xdown)$.
	\end{hint}
	\begin{sol}
		Put $\xdown = \frac{1}{\sqrt2} (\ket0-\ket1)$.
		Then we have that $U_f$ sends
		\[
			\ket{x_1}  \dots  \ket{x_m}  \ket 0
			- \ket{x_1}  \dots  \ket{x_m}  \ket 1
			\xmapsto{U_f}
			\pm \ket{x_1}  \dots  \ket{x_m}  \ket 0
			\mp \ket{x_1}  \dots  \ket{x_m}  \ket 1
		\]
		the sign being $+$, $-$ exactly when $f(x_1, \dots, x_m) = 1$.

		Now, upon inputting $\ket0 \dots \ket0 \ket1$, we find that $H^{\otimes m+1}$ maps it to
		\[ 2^{-n/2} \sum_{x_1, \dots, x_n} \ket{x_1} \dots \ket{x_n} \xdown.  \]
		Then the image under $U_f$ is
		\[ 2^{-n/2} \sum_{x_1, \dots, x_n} (-1)^{f(x_1, \dots, x_n)} \ket{x_1} \dots \ket{x_n} \xdown.  \]
		We now discard the last qubit, leaving us with
		\[ 2^{-n/2} \sum_{x_1, \dots, x_n} (-1)^{f(x_1, \dots, x_n)} \ket{x_1} \dots \ket{x_n}.  \]
		Applying $H^{\otimes m}$ to this, we get
		\[ 2^{-n/2} \sum_{x_1, \dots, x_n} (-1)^{f(x_1, \dots, x_n)}
			\cdot
			\left(
			2^{-n/2}
			\sum_{y_1, \dots, y_n}
			(-1)^{x_1 y_1 + \dots + x_n y_n}
			\ket{y_1} \ket{y_2} \dots \ket{y_n}
			\right)
		\]
		since $H\ket0 = \frac{1}{\sqrt2}(\ket0+\ket1)$
		while $H\ket1 = \frac{1}{\sqrt2}(\ket0-\ket1)$,
		so minus signs arise exactly if $x_i = 0$ and $y_i = 0$ simultaneously,
		hence the term $(-1)^{x_1 y_1 + \dots + x_n y_n}$.
		Swapping the order of summation, we get
		\[
			2^{-n}
			\sum_{y_1, \dots, y_n}
			C(y_1, \dots, y_n)
			\ket{y_1} \ket{y_2} \dots \ket{y_n}
		\]
		where $C_{y_1, \dots, y_n}
		= \sum_{x_1, \dots, x_n} (-1)^{f(x_1, \dots, x_n)
			+x_1 y_1 + \dots + x_n y_n}$.
		Now, we finally consider two cases.
		\begin{itemize}
			\ii If $f$ is the constant function, then we find that
			\[
				C(y_1, \dots, y_n) =
				\begin{cases}
					\pm 1 &  y_1 = \dots = y_n = 0 \\
					0 & \text{otherwise}.
				\end{cases}
			\]
			To see this, note that the result is clear for $y_1 = \dots = y_n = 0$;
			otherwise, if WLOG $y_1 = 1$, then the terms for $x_1 = 0$ exactly cancel
			the terms for $x_1 = 0$, pair by pair.
			Thus in this state, the measurements all result in $\ket0 \dots \ket0$.

			\ii On the other hand if $f$ is balanced, we derive that
			\[ C(0, \dots, 0) = 0. \]
			Thus \emph{no} measurements result in $\ket 0 \dots \ket 0$.
		\end{itemize}
		In this way, we can tell whether $f$ is balanced or not.
	\end{sol}
\end{problem}

\begin{dproblem}[Barenco et al, 1995; arXiv:quant-ph/9503016v1]
	Let
	\[
		P = \begin{bmatrix} 1 & 0 \\ 0& i \end{bmatrix}
		\qquad
		Q = \frac{1}{\sqrt2}\begin{bmatrix} 1 & -i \\ -i & 1 \end{bmatrix}
	\]
	Verify that the quantum Toffoli gate can be implemented
	using just controlled rotations via the circuit
	\[
		\Qcircuit @R=1em @C=0.7em {
			\lstick{\ket{x_1}} & \qw & \ctrl{2} & \ctrl{1} & \ctrl{1} & \qw & \ctrl{1} & \qw \\
			\lstick{\ket{x_2}} & \ctrl{1} & \qw & \gate{P} & \targ & \ctrl{1} & \targ & \qw \\
			\lstick{\ket{x_3}} & \gate{Q} & \gate{Q} & \qw & \qw & \gate{Q^\dagger} & \qw & \qw
		}
	\]
	This was a big surprise to researchers when discovered,
	because classical reversible logic requires three-bit gates (e.g. Toffoli, Fredkind).
	\begin{hint}
		This is direct computation.
	\end{hint}
\end{dproblem}
