%
\documentclass[11pt]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
%\usepackage{hyperref}
\usepackage{graphicx,color}
%preamble from Richard
\setlength{\oddsidemargin}{0.25in}
\setlength{\topmargin}{-2.0cm} % needs to be adjusted to your printer!
\setlength{\textwidth}{6.25in}
%\setlength{\textwidth}{5in}
\setlength{\textheight}{9.2in} \setlength{\parskip}{1mm}
\setlength{\parindent}{0mm}
\newcommand{\gt}{>}
\newcommand{\ket}[1]{\left | #1 \right \rangle}
\newcommand{\bra}[1]{\left \langle #1 \right |}
\newcommand{\ave}[1]{\langle #1 \rangle}
\def\proof{{\bf Proof.}}
\def\ra{\rangle}
\def\la{\langle}
\def\rl{\rangle \langle}
\def\openone{\leavevmode\hbox{\small1\kern-3.8pt\normalsize1}}
%\def\RR{{\rm I\kern-.2emR}}
\def\tr{{\rm tr}\; }
\def\ce{{\cal E}}
\def\cl{{\cal L}}
\def\cb{{\cal B}}
\def\ch{{\cal H}}
\def\cn{{\cal N}}
\def\co{{\cal O}}
\def\cf{{\cal F}}
\def\cg{{\cal G}}
\def\ca{{\cal A}}
\def\cv{{\cal V}}
\def\cc{{\cal C}}
\def\cp{{\cal P}}
\def\cm{{\cal M}}
\def\mod{\,\, {\rm mod}\,\,}
\def\ma{\mathbf{a}}
\def\mb{\mathbf{b}}
\def\mx{\mathbf{x}}
\def\mapr{\mathbf{a'}}
\def\RR{\mathbb{R}}
\def\ZZ{\mathbb{Z}}
\def\QQ{\mathbb{Q}}
\def\NN{\mathbb{N}}
\def\nbits{\mathbb{Z}_2^n}
\def\CC{\mathbb{C}}
\def\OO{\mathbb{O}}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{conjecture}{Conjecture}
\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
\newtheorem{property}{Property}
\newcommand{\half}{\mbox{$\textstyle \frac{1}{2}$} }
\newcommand{\proj}[1]{\ket{#1}\!\bra{#1}}
\newcommand{\outerp}[2]{\ket{#1}\!\bra{#2}}
\newcommand{\inner}[2]{ \langle #1 | #2 \rangle}
\newcommand{\melement}[2]{ \langle #1 | #2 | #1 \rangle}
\newcommand{\mmatrix}[4]{\left( \begin{array}{cc} #1 & #2 \\ #3 &
#4 \end{array} \right)}
\newcommand{\vvec}[2]{\left( \begin{array}{cc} #1 \\ #2 \end{array} \right)}
\newcommand{\sign}[1]{{\rm sign}(#1)}
\newcommand{\poly}{{\rm poly}}
\newcommand{\prob}{{\rm prob}}
\newcommand{\op}{\oplus}
\newcommand{\vecc}[1]{\underline{#1}}
\begin{document}
\begin{center}{\large\bf EXERCISES FOR PARATY LECTURES (Richard Jozsa)} \end{center}
{\bf Exercise for Lecture 1}
{\bf 1D cluster state as an MPS}
The 1D cluster state on a line on $n$ qubits (labelled $1,2,\ldots ,n$) is the state $\ket{Cl_n}$ obtained as follows: start with a row of $\ket{+} = (\ket{0}+\ket{1})/\sqrt{2}$ states $\ket{+}_1\ket{+}_2\ldots \ket{+}_n$ and apply $CZ$ to each nearest neighbour pair $(1,2), (2,3), \ldots , (n-1,n)$.
Let $\ket{i_1 \ldots i_n}$ (with each $i_k$ being 0 or 1) be any computational basis state.
(a) Show that $\ket{Cl_n}$ has amplitudes $\inner{i_1 \ldots i_n}{Cl_n}= \frac{1}{2^n}(-1)^\alpha$ where $\alpha$ is the number of sites $k$ with $i_k=i_{k+1}=1$.
To express $\ket{Cl_n}$ as an MPS
\[ \ket{Cl_n}= \sum_{i_1, i_2, \ldots ,i_n=0}^1 L^{(i_n)}C^{(i_{n-1})}\ldots A^{(i_2)}
R^{(i_1)} \ket{i_1 \ldots i_n}, \]
where $A^{(i_2)}, \ldots ,C^{(i_{n-1})}$ are matrices and $L^{(i_n)}$ and $R^{(i_1)}$ are row and column vectors respectively, we will use Dirac notation to write the amplitudes as $\bra{L^{(i_n)}}C^{(i_{n-1})}\ldots A^{(i_2)} \ket{R^{(i_1)}}$. Introduce
\[ T^{(0)}= \left(\begin{array}{cc} 1 & 0 \\ 1 & 0 \end{array}\right) = \ket{p}\bra{0}\hspace{5mm}
T^{(1)}= \left(\begin{array}{cc} 0 & 1 \\ 0 & -1 \end{array}\right) = \ket{m}\bra{1}
\]
where $\ket{p}=\ket{0}+\ket{1}$ and $\ket{m}=\ket{0}-\ket{1}$.
(b) Show that $T^{(i)}T^{(i')}= \pm \ket{\mbox{$p$ or $m$}}\bra{\mbox{0 or 1}}
$ with a minus sign iff $i=i'=1$.\\ What is the value of $\bra{0} T^{(i_1)}\ldots T^{(i_n)}\ket{p}$?
Hence write down an MPS expression of $\ket{Cl_n}$ in the form $\sum_{i_1, i_2, \ldots ,i_n} L^{(i_n)}C^{(i_{n-1})}\ldots A^{(i_2)}R^{(i_1)} \ket{i_1 \ldots i_n}$.
(c) Now consider any measurement-based quantum computational (MQC) process on the 1D cluster state. Such a process is defined by a sequence of 1-qubit measurements on specified qubits and each choice of measurement may depend on (classical poly-time) calculations with previous measurement outcomes. Can such a process be classically efficiently simulated? Give a justification of your answer by quoting suitable results from the lecture.
(d){\bf (optional extra)} It is known that the MQC process of (c) applied on a 2D cluster state is {\em universal} for quantum computing (this is standard Raussendorf-Briegel cluster state MQC) so we would not expect it to be efficiently classically simulatable! Why does the argument in (c) not apply for the 2D cluster state?\\
(Hints: Consider a square grid of $n\times n$ $\ket{+}$ states with $CZ$ applied to each horizontal and vertical nearest neighbour pair in the grid. Suppose $n$ is even for convenience. Let $A$ be the subset of qubits in rows 1 to $n/2$ and $B$ those in rows $n/2+1$ to $n$.\\ (i) Look at the qubits just in rows $n/2$ and $n/2+1$ ($n$ qubits in each row). Show that the $n$ vertical $CZ$ operations on just these qubits gives a state with Schmidt rank $2^n$.\\ (ii) Show that the Schmidt rank of any bipartite state of $AB$ is unchanged by any unitary operations acting wholly within $A$ or $B$.\\ (iii) Deduce that the Schmidt rank of the 2D cluster state is exponential in $n$ for at least some partitions of the qubits, and conclude that our results about efficient classical simulaton do not apply to 2D cluster state MQC.
\newpage
{\bf Exercise for Lecture 2}
{\bf Clifford circuits}
(a) Let $C$ be a Clifford operation for $n$ qudits. Then for any $T(\underline{a},\underline{b}) = X^{a_1}Z^{b_1}\otimes \ldots \otimes X^{a_n}Z^{b_n}$ we have $C\, T(\underline{a},\underline{b})\, C^\dagger=
k \, T(\underline{a'},\underline{b'})$ for some $\underline{a'}, \underline{b'}\in \mathbb{Z}^n_d$ and complex $k$. Show that $k$ is necessarily a $d^{\rm th}$ root of unity. (Hint: recall $XZ=\omega ZX$ and $X^d=Z^d=I$).
(b) Consider Clifford circuits on $n$ qubits with the following features: inputs are computational basis states; intermediate measurements are allowed within the circuit but with non-adaptive choice of later gates. We saw in the lecture that in this situation, single line outputs are classically strongly efficiently simulatable (e.g. by Thm 1 on slide 13, with its proof there too).\\ (i) Suppose the output now arises from measurements on $O(\log n)$ lines. By suitably generalising the given proof of Thm 1, show that this is still classically strongly efficiently simulatable. (Hint: recall $\proj{0}=(I+Z)/2$ and similarly for $\proj{1}$.) \\ (ii) Does this proof still hold if there are $O(n)$ output lines? Why (not)? (However this case is still classically strongly efficiently simulatable, but by a more complicated argument, see e.g. arXiv:1305.6190 theorem 4).
\newpage
{\bf Exercise for Lecture 3}
{\bf Jordan-Wigner matrices and matchgates}
Let $c_1, c_2, \ldots ,c_{2n}$ be the standard Jordan-Wigner (JW) matrices for $n$ qubit lines. Consider the quadratic hamiltonian $H=i\theta c_1c_2$ for real $\theta$.
(a) Compute the associated matchgate (Gaussian operation) $U=\exp iH$.
(b) Calculate its conjugation action on the JW matrices and show directly that the linear span is preserved. Hence also find the corresponding rotation matrix $R\in SO(2n, \mathbb{R})$ associated to this conjugation action.
(c) {\bf (optional extra)} (linear terms in the hamiltonian)\\ Now let $c_1, c_2, \ldots ,c_{2n}$ be $2n$ abstract generators of a Clifford algebra (i.e. they satisfy the Clifford algebra anti-commutation relations). Introduce a further symbol called $c_0$ which is required to have the same relations with all the $c_\mu$'s i.e.
\[ \{ c_0, c_\mu \} = 2\delta_{0\mu} I\hspace{5mm} \mbox{for $\mu = 0,1,\ldots ,2n$} \]
extending the set of $c$'s to $2n+1$ generators. Introduce
\[ \mbox{$d_0=c_0$ and \hspace{2mm}$d_\mu=ic_\mu c_0 $ for $\mu = 1,\ldots , 2n$.} \]
(The optional factor $i$ here is just to have all $d$'s hermitian if the $c$'s were.)\\
Show the following:\\ (i) $ \{ d_\mu,d_\nu \} = 2\delta_{\mu\nu} I\hspace{5mm} \mu , \nu = 0,1, \ldots , 2n.$\\
(ii) A general purely quadratic expression in the $d_\mu$'s for $\mu=0,1, \ldots ,2n$
\[ \tilde{A}= \sum_{\mu ,\nu =0}^{2n} \tilde{a}_{\mu \nu} d_\mu d_\nu \]
is the same as a general quadratic {\em plus linear} expression in the original $c_\mu$'s for $\mu=1,\ldots ,2n$
\[ A=\sum_{\mu ,\nu=1}^{2n} a_{\mu \nu}\, c_\mu c_\nu +\sum_{\sigma =1}^{2n} b_\sigma c_\sigma .
\]
In fact $a_{\mu \nu}=\tilde{a}_{\mu \nu}$ for $\mu, \nu = 1,\ldots ,2n$ and $b_\sigma = i(\tilde{a}_{\sigma 0}-\tilde{a}_{0\sigma})$.
Hence Gaussian operations constructed from purely quadratic hamiltonians in the $d_\mu$'s correspond to an extended class of ``generalised'' Gaussian operations in the $c_\mu$'s viz. those arising from exponentials of {\em linear} as well as quadratic terms in the hamiltonian. Thus using our classical simulation methods applied to the $d_\mu$'s, arbitrary circuits of these generalised gates in the $c_\mu$'s can also be strongly classically efficiently simulated. See R.J, A. Miyake, S. Strelchuk arXiv:1311.3046v2 for more details and further developments of this.
\end{document}
\begin{theorem}\label{thm2} Let $c_\mu$ for $\mu = 1,\ldots , m$ be as above and let $c_0$ be a further symbol satisfying
\[ \{ c_0, c_\mu \} = 2\delta_{0\mu} \hspace{5mm} \mbox{for $\mu = 0,1,\ldots ,m$} \]
extending the set of $c$'s to $m+1$ generators. Introduce
\[ \mbox{$d_0=c_0$ and \hspace{2mm}$d_\mu=ic_\mu c_0 $ for $\mu = 1,\ldots , m$.} \]
(The optional factor $i$ here is just to have all $d$'s hermitian if the $c$'s were.)
Then\\ (a) $ \{ d_\mu,d_\nu \} = 2\delta_{\mu\nu} I\hspace{5mm} \mu , \nu = 0,1, \ldots , m.$\\
(b) A general purely quadratic expression in the $d_\mu$'s for $\mu=0,1, \ldots ,m$
\begin{equation}\label{eq1} \tilde{A}= \sum_{\mu ,\nu =0}^m \tilde{a}_{\mu \nu} d_\mu d_\nu \in \cl_2(d{\rm 's}) \end{equation}
is the same as a general quadratic {\em plus linear} expression in the $c_\mu$'s for $\mu=1,\ldots ,m$
\begin{equation}\label{eq2} A=\sum_{\mu ,\nu=1}^m a_{\mu \nu}\, c_\mu c_\nu +\sum_{\sigma =1}^m b_\sigma c_\sigma\,\,\, \in \cl_{1\oplus 2}(c{\rm 's}).
\end{equation}
In fact $a_{\mu \nu}=\tilde{a}_{\mu \nu}$ for $\mu, \nu = 1,\ldots ,m$ and $b_\sigma = i(\tilde{a}_{\sigma 0}-\tilde{a}_{0\sigma})$.
\end{theorem}