Matchgate quantum computing
S. Ramelow$^{1,2}$
In the circuit model, quantum computers rely on the availability of a universal quantum gate set. A particularly intriguing example of such a set is the ``matchgates'' along with \textsc{swap}, the simple exchange of two qubits. In this paper, we show a simple decomposition of arbitrary matchgates into better known elementary gates, and implement one matchgate in a linear optics experiment using single photons. We characterize the gate performance via quantum process tomography and represent the resulting quantum process in a novel way, as a fidelity map in the space of all possible nonlocal two-qubit unitaries. In addition, we propose a new non-local, diagnostic process measure.
paper.tex
\documentclass[aps,prl,floatfix,twocolumn,a4paper]{revtex4}

\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{epstopdf}

\newcommand{\bra}[1]{\mbox{$\langle #1|$}}
\newcommand{\ket}[1]{\mbox{$|#1\rangle$}}
\newcommand{\braket}[2]{\mbox{$\langle #1|#2\rangle$}}
\newcommand{\ketbra}[2]{\mbox{$|#1\rangle\langle #2|$}}
\newcommand{\op}[1]{\mbox{\boldmath $\hat{#1}$}}
\newcommand{\Ket}[2]{|#1\rangle^{(#2)}}
\newcommand{\comment}[1]{\fbox{{\parbox{.4\textwidth}{\tiny #1}}}}

\pagestyle{empty}

\begin{document}

\title{Matchgate quantum computing}

\author{S. Ramelow$^{1,2}$}
\thanks{These authors contributed equally to this work.}
\author{A. Fedrizzi$^{1}$}
\thanks{These authors contributed equally to this work.}
\author{A. M. Steinberg$^{1,3}$}
\author{A. G. White$^{1}$}

\affiliation{$^1$Department of Physics and Centre for Quantum Computer
Technology, University of Queensland, QLD 4072, Australia\\
$^2$Faculty of Physics, University of Vienna, Boltzmanngasse 5, 1090
Vienna, Austria\\
$^{3}$Center for Quantum Information and Quantum Control, Institute for Optical Sciences, Department of Physics, University of Toronto, 60 St. George Street, Toronto, ON, M5S 1A7, Canada}

\begin{abstract}
In the circuit model, quantum computers rely on the availability of a universal quantum gate set. A particularly intriguing example of such a set is the ``matchgates'' along with \textsc{swap}, the simple exchange of two qubits. In this paper, we show a simple decomposition of arbitrary matchgates into better known elementary gates, and implement one matchgate in a linear optics experiment using single photons. We characterize the gate performance via quantum process tomography and represent the resulting quantum process in a novel way, as a fidelity map in the space of all possible nonlocal two-qubit unitaries. In addition, we propose a new non-local, diagnostic process measure.
\end{abstract}

\date{\today}

\maketitle

%\section{Introduction}
In quantum computation, an essential requirement of the circuit model is a universal gate set, which enables the approximation of any given unitary process to arbitrary precision \cite{nielsen2000qca}. The advantages and disadvantages of various gate sets are still being actively explored; for example, one set may be more natural than others for interpreting a certain problem, or, in a given physical architecture one set may require far less resources than another.
The best known gate-set class is that of any entangling 2-qubit gate in combination with arbitrary single-qubit unitaries \cite{dodd2002uqc}: most famously the 2-qubit \textsc{cnot} gate in conjunction with the 1-qubit Hadamard, $\textsc{h}$, and phase, $\textsc{t}$, gates. Circuits constructed of solely the \textsc{cnot} and $\textsc{h}$ gates can be simulated efficiently with a classical computer \cite{nielsen2000qca}. However, the addition of the $\textsc{t}$ gate---itself also efficiently simulatable---enables universal quantum computing (which of course is generally believed \emph{not} to be efficiently simulatable). Another important gate-set class uses 3-qubit entanglers, such as the Toffoli gate---which has only recently been demonstrated in linear optics \cite{lanyon2008sql} and ion traps \cite{monz2008rqt}---along with $\textsc{h}$.

In this paper we demonstrate a new gate-set class based \emph{only} on 2-qubit gates, specifically the \emph{matchgate} \cite{valiant2002qcc}, which can be entangling, and the \textsc{swap} gate, which is strictly non-entangling \cite{terhal2002csn,jozsa2008mac}. Matchgates---originally introduced in graph theory \cite{valiant2002qcc}---are 2-qubit unitaries,
\begin{equation}
\textsc{g}_\textsc{ab}=\left(\begin{array}{cccc}
a_{11} & 0 & 0  & a_{12}  \\
0 & b_{11} & b_{12}  & 0  \\
0 & b_{21} & b_{22}  &  0 \\
a_{21} & 0 & 0 & a_{22} \\
\end{array}
\right), \label{eq:matchgate}
\end{equation}
where \textsc{a} and \textsc{b}, the 1-qubit unitaries formed by
\begin{equation}
\textsc{a}=\left(\begin{array}{cc}
a_{11} & a_{12}\\
a_{21} & a_{22}\\
\end{array}
\right)~~\text{and}~~\textsc{b}=\left(\begin{array}{cc}
b_{11} & b_{12}\\
b_{21} & b_{22}\\
\end{array}\right),
\end{equation}
are members of $U(2)$ with $det(\textsc{a}){=}det(\textsc{b})$, and act on the even and the odd 2-qubit parity subspaces %of an input state
respectively \footnote{Relaxing the condition $det(\textsc{a}){=}det(\textsc{b})$ would allow $\textsc{g}_\textsc{ix}{=}\textsc{swap}$, where \textsc{i} is the 1-qubit identity.}. Matchgates include a rich number of entangling gates---including maximal entangling gates---as well as many classes of local gates. If matchgates act only between nearest-neighbour qubits, then the resulting circuit can be efficiently simulated classically \cite{valiant2002qcc}. In this context matchgates relate to systems of non-interacting fermions \cite{terhal2002csn}. Moreover, they are connected to 1D quantum Ising models: explicit matchgate circuits for simulations of such strongly-correlated quantum systems have been constructed in \cite{verstraete2009qcs}. However, if matchgates are also allowed to operate between \emph{next}-nearest neighbours---a seemingly trivial change achieved via \textsc{swap} gates---then the circuit can perform universal quantum computation \cite{jozsa2008mac}. Clearly, the resulting universal gate set is entirely different from the two mentioned above.

Here we show how to realise arbitrary matchgates using circuit elements already demonstrated in a range of physical architectures; we go on to demonstrate and measure matchgate operation in a linear optics photonic system, quantifying their performance with a new method for experimental analysis of two-qubit gates.

Fig.~\ref{fig:decomp}a) shows the decompostion of an arbitrary matchgate, $\textsc{g}_\textsc{ab}$, into \textsc{cnot}, controlled-unitary and single-qubit gates. Recall that, depending on the parity of the input state into the matchgate, either $\textsc{a}$ or $\textsc{b}$ acts on the two qubits. The first step of our general decomposition is to encode the parity of the two-qubit state onto one of the qubits. The first \textsc{cnot} gate turns the bottom qubit into state $\ket{0}$ for even-parity inputs ($\ket{00} {\rightarrow} \ket{00}$ \& $\ket{11} {\rightarrow} \ket{10}$) and into $\ket{1}$ for odd-parity inputs ($\ket{01} {\rightarrow} \ket{01}$ \& $\ket{10}  {\rightarrow} \ket{11}$). This qubit then acts as the control for the controlled unitary, \textsc{cu} \footnote{$\textsc{cnot}=\ket{0}\bra{0}\otimes\textsc{i}+\ket{1}\bra{1}\otimes\textsc{x}$, $\textsc{cu}=\ket{0}\bra{0}\otimes\textsc{i}+\ket{1}\bra{1}\otimes\textsc{u}$}, where $\textsc{u} {=} \textsc{b} \textsc{a}^{-1}$. If the bottom qubit is in state $\ket{0}$ (parity${=}0$), \textsc{a} will act on the top qubit; if it is in state $\ket{1}$ (parity${=}1$), \textsc{cu} will undo \textsc{a} before it performs \textsc{b}. The final \textsc{cnot} gate returns the qubits from the parity encoding to the original basis.

\begin{figure}[!thbp]
\begin{center}
\includegraphics[width=0.47\textwidth]{fig1.eps}
\caption{a) Decomposition of general matchgates $\textsc{g}_\textsc{ab}$. b) Simplified decomposition of symmetric matchgates $\textsc{g}_\textsc{aa}$ as described in the text. c) The same gate after flipping the \textsc{cnot}s with $\textsc{h}$s and decomposing $\textsc{h} \textsc{a} \textsc{h}$ into $\textsc{x}$- and $\textsc{z}$-rotations. d) Further simplification shows that $\textsc{g}_\textsc{aa}$, up to a global phase, can be implemented using a single \textsc{cz}$_{\theta}$ and local unitaries $\textsc{v}_1{=}\textsc{hx}_{\alpha}$ and $\textsc{v}_2{=}\textsc{z}_{-\theta/2}\textsc{x}_{\beta}\textsc{h}$ where $\alpha$, $\beta$, and $\theta$ are related to $\textsc{a}$ via $\textsc{h} \textsc{a} \textsc{h}{=}\textsc{x}_{\alpha}\textsc{z}_{-\theta/2}\textsc{x}_{\beta}$. For $\textsc{g}_\textsc{hh}$, $\theta{=}\pi$, and $\textsc{cz}_{\theta}\rightarrow\textsc{cz}$.}
\label{fig:decomp}
\end{center}
\end{figure}
Note that, alternatively, any 2-qubit operation could be implemented with three \textsc{cnot} gates and 8 single-qubit unitaries \cite{vidal2004uqc}, or two ``$\mathcal{B}$''-gates (yet to be experimentally demonstrated) and 6 single-qubit unitaries \cite{zhang2004mct}. Our decomposition, which offers a starting point for further simplifications, in contrast requires fewer gates and allows one to recast matchgate circuits (e.g. those in \cite{verstraete2009qcs}) into circuits consisting of more familiar quantum gates ---the \textsc{cnot} \cite{obrien2003dao,gasparoni2004rpc}, the more general \textsc{cu} \cite{lanyon2008sql}, and single qubit rotations, all of which have been individually implemented in various architectures.

We now show how to build the matchgates required for a universal gate set. The universality proof in \cite{jozsa2008mac}, relies on showing how matchgates and \textsc{swap} can be applied to implement another universal set---\textsc{h}, \textsc{t} and \textsc{cz}. As outlined in the additional online material \footnote{See EPAPS supplementary material at [URL will be inserted by AIP] for details}, each logical qubit has to be encoded in two (or four) physical qubits. The required matchgate set is then $\textsc{g}_\textsc{xx}$, $\textsc{g}_\textsc{tt}$ and $\textsc{g}_\textsc{hh}$. These gates are all symmetric i.e. $\textsc{a}{=}\textsc{b}$, and the circuit of Fig.~\ref{fig:decomp}a) is greatly simplified, because $\textsc{a}^{-1}\textsc{a}{=}\textsc{i}$: the controlled unitary turns into a ``controlled identity''. The resulting circuit diagram, shown in Fig.~\ref{fig:decomp}b), still requires two 2-qubit gates. It does however resemble the general construction of a \textsc{cu} \cite{barenco1995egq} gate, i.e. it can be replaced by a single \textsc{cu} and 4 single-qubit unitaries in the following way: We flip the \textsc{cnot}s upside down by adding 4 Hadamards---$\overline{\textsc{cnot}}{\equiv}(\textsc{h}{\otimes}\textsc{h}){\times}\textsc{cnot}{\times}(\textsc{h}{\otimes}\textsc{h})$---and rewrite the resulting central unitary $\textsc{h} \textsc{a} \textsc{h}$, up to a global phase, as $\textsc{x}_{\alpha}\textsc{z}_{-\theta/2}\textsc{x}_{\beta}$ \cite{barenco1995egq}, Fig.~\ref{fig:decomp}c). The rotations $\textsc{x}_{\alpha}$ and $\textsc{x}_{\beta}$ commute with their respective \textsc{cnot}s, which allows us to express the two-qubit part of the operation as a single controlled $\textsc{cz}_{\theta}$, Fig.~\ref{fig:decomp}d). This simplified circuit for $\textsc{g}_\textsc{aa}$ can now be directly implemented in bosonic systems using the technique of shortcuts through higher-dimensional Hilbert spaces \cite{lanyon2008sql}.

Turning back to the universal matchgate set, we find that $\textsc{g}_\textsc{xx}{=}\textsc{x}{\otimes}\textsc{x}$ and $\textsc{g}_\textsc{tt}{=}\textsc{t}{\otimes}\textsc{i}$---both operations are local and can be done trivially in a photonic architecture with waveplates or interferometers. Similarly, \textsc{swap} is a straightforward procedure in optics, either in free-space or integrated circuits. The one non-trivial gate to be demonstrated is
\begin{equation}
\textsc{g}_\textsc{hh}{=}\frac{1}{\sqrt{2}}\left(\begin{array}{cccc}
1 & 0 & 0  & 1  \\
0 & 1 & 1  & 0  \\
0 & 1 & -1  &  0 \\
1 & 0 & 0 & -1 \\
\end{array}\right),\label{eq:ghh}
\end{equation}
which is a nonlocal, maximally entangling gate. For this gate the decomposition yields $\theta{=}\pi$ and therefore $\textsc{cz}_{\theta}$ in Fig.~\ref{fig:decomp}d) is the well known \textsc{cz} gate. Experimentally, we can therefore implement $\textsc{g}_\textsc{hh}$ using polarization-encoded single photons, partially polarizing beam splitters and coincidence detection \cite{langford2005dse,kiesel2005loc,okamoto2005doq}. The experimental setup is explained in Fig.~\ref{fig:scheme}.
\begin{figure}[!bhtp]
\begin{center}
\includegraphics[width=0.40\textwidth]{fig2.eps}
\caption{Experimental scheme. Orthogonally polarized photon pairs are created in a nonlinear ppKTP crystal which is pumped by a 410 nm laser diode,  using focussing parameters from \cite{fedrizzi2007wtf}. The photons are split at a polarizing beamsplitter (PBS), collected, and guided to the circuit with single-mode optical fibers. Their input polarizations are set with a PBS, one quarter- and one half-wave plate (QWP, HWP) (Prep.). They are then superposed on a partially polarizing beamsplitter (PPBS) which transmits $2/3$ of horizontal, $\ket{H}$ and perfectly reflects vertical, $\ket{V}$ light. Loss elements (PPBS$^{\prime}$) correct the respective amplitudes and the unknown phase shift at the central PPBS is compensated by a combination of a QWP, a HWP and another QWP in one output port of the PPBS. If compensated correctly, only the input term $\ket{HH}$ picks up a phase shift of $\pi$ due to non-classical interference, which realizes a bit-flipped \textsc{cz} when measured in coincidence. The photons are then jointly analyzed with a QWP, a HWP and a PBS (Tomo.) before they are detected by two single-photon detectors. The rotations for the 4 single-qubit unitaries required for $\textsc{g}_{\textsc{hh}}$ in Fig.~\ref{fig:decomp}d) are incorporated into the preparation and measurement waveplate settings.}
\label{fig:scheme}
\end{center}
\end{figure}

We characterized our gate using full quantum \emph{process} tomography \cite{obrien2004qpt}, preparing $16$ combinations of the states $\{\ket{H},\ket{V},\ket{D}{=}1/\sqrt{2}(\ket{H}{+}\ket{V}),\ket{R}{=}1/\sqrt{2}(\ket{H}{+}i\ket{V})\}$ at each input and projecting into an overcomplete set of 36 measurements at the outputs. The photons were then detected in coincidence. The resulting process matrix $\chi_{exp}$, reconstructed via maximum-likelihood estimation, is shown in Fig.~\ref{fig:chi}. The process fidelity with $\chi_{ideal}$ is $92.3\pm0.2\%$, where the error was calculated assuming Poissonian count statistics. We attribute the remaining errors to non-ideal waveplates, imperfections in the spatial and temporal mode-overlap, as well as in the splitting ratios of the PPBS's.
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.44\textwidth]{fig3.eps}
\caption{a) Real and b) imaginary parts of the $\textsc{g}_\textsc{hh}$ process matrix $\chi_{exp}$ reconstructed from quantum process tomography measurements. The wireframes represent the ideal process $\chi_{ideal}$. The process fidelity of $\chi_{exp}$ with $\chi_{ideal}$ was $92.3\pm0.2\%$. We did not apply any numeric local rotations to optimize this result in contrast to, e.g. \cite{lanyon2008sql}.}
\label{fig:chi}
\end{center}
\end{figure}

The question remains: how well we have actually implemented a matchgate? A single process fidelity, such as calculated above, reveals the overlap between the experimental process and the corresponding, ideal target process. However, it does not yield any information about the way in which the process is not ideal---is it just mixed due to random noise or are we in fact implementing a different unitary process than we actually thought? In particular, we are interested in the \emph{nonlocal} properties of the quantum process, as they define its entangling power and errors in them cannot be corrected with local operations.

Interestingly, as shown in \cite{kraus2001oce}, out of the $15$ real parameters which define a unitary 2-qubit operator $U{\in}SU(4)$, only three actually describe the nonlocal part of the unitary, the remaining $12$ relating to local transformations:
\begin{equation}
U{=}(u_{1}{\otimes}v_{1})e^{\frac{-i}{2}(c_{1}\sigma_{x}\otimes\sigma_{x}+c_{2}\sigma_{y}\otimes\sigma_{y}+c_{3}\sigma_{z}\otimes\sigma_{z})}(u_{2}{\otimes}v_{2}).\label{eq:canonical}
\end{equation}

 \begin{figure*}[!t]
 \begin{center}
 \includegraphics[width=0.94\textwidth]{fig4.eps}
 \caption{a) Tetrahedron depicting the space of all nonlocal two-qubit unitary gates. All local gates $u{\otimes}v$, like $\textsc{g}_{\textsc{xx}}$ and $\textsc{g}_{\textsc{tt}}$, are represented by $[0,0,0]$; \textsc{swap} is located at $[0,\pi/2,\pi/2]$. The shaded volume represents the space of all perfect entanglers \cite{zhang2003gtn}, i.e. gates that can turn separable states into Bell states. The (thick blue) line $[\gamma,0,0]$ contains all $\textsc{g}_{\textsc{aa}}$ gates, which are equivalent to \textsc{cu} \cite{lanyon2008sql}. $\textsc{g}_{\textsc{hh}}$ is located at its midpoint $[\pi/2,0,0]$, and is therefore the only symmetric matchgate which is maximally entangling. b-c) Point-by-point locally optimized process fidelity map, Eq.~\ref{eq:fidelity}, of all ideal nonlocal gates with b) the ideal target gate and c) the experimentally reconstructed $\textsc{g}_{\textsc{hh}}$ process matrix. The maximum fidelity is $94.7\pm0.3\%$ at ${\sim}[\pi/2,0,0]$.}
 \label{fig:weyl}
 \end{center}
 \end{figure*}
This decomposition allows a very intuitive geometrical representation of local equivalence classes. The three nonlocal parameters $c_{1}$, $c_{2}$ and $c_{3}$ can be used to construct a 3-dimensional space of nonlocal gates. Symmetries reduce this space to a tetrahedron, shown in Fig.~\ref{fig:weyl} (a), the so-called Weyl-chamber \cite{zhang2003gtn}. Each point in this chamber represents all locally-equivalent gates with unique nonlocal properties \footnote{With the exception of the $c_{3}$=0 plane, which is symmetric around the line $[\pi/2,0,0]\rightarrow[\pi/2,\pi/2,0]$.}; the \textsc{cnot} gate, \textsc{cz}, and therefore also $\textsc{g}_\textsc{hh}$ gate, are all locally equivalent and located at $[\pi/2, 0, 0]$. Using a method from \cite{zhang2003gtn}, one can directly check whether two gates are locally equivalent, which confirms the results obtained from our matchgate decomposition in Fig.~\ref{fig:decomp}. In order to illustrate our experimental process in the Weyl chamber and to find the nonlocal unitary gate closest to it, we numerically translated $6201$ evenly-spaced ideal 2-qubit operators defined by (\ref{eq:canonical}) into their process representation and then calculated their maximal \emph{nonlocal} process fidelity,
\begin{equation}
\mathcal{F}_{nl}(c_{1},c_{2},c_{3})=\underset{u_{1}...v_{2}}\max\mathcal{F}(\chi_{exp},\chi(c_{1}...c_{3},u_{1}...v_{2})).\label{eq:fidelity}
\end{equation}
to $\chi_{exp}$ by numerical optimization over the local transformations $u_{1}, v_{1}$, and $u_{2}, v_{2}$. The result is a three-dimensional process fidelity map, shown in Fig.~\ref{fig:weyl}b) and c) for the ideal and experimental processes respectively. After optimization over the local unitaries, we find a maximum process fidelity for our experimental gate of $94.7{\pm}0.3\%$ (increased from 92.3\%, Fig.~\ref{fig:chi}) at $[c_{1},c_{2},c_{3}]{\sim}[\pi/2,0,0]$. At first it may seem that the $\mathcal{F}_{nl}$ (\ref{eq:fidelity}) is not a very sharp measure but in fact the volume of nonlocal gates with $\geq$90\% fidelity to $\chi_{ideal}$ is just 11.6\% \footnote{The process fidelity has a range of $\mathcal{F}\in[0.25,1].$}. For $\chi_{exp}$, this volume shrinks to 4.85\%, due to decoherence.

We can now define a new process distance measure---the \emph{nonlocal distance}, $\Delta_{nl}{\equiv} \sqrt{\Delta c_{1}^{2}+\Delta c_{2}^{2}+\Delta c_{2}^{2}}$,  where $\Delta_{nl}{\in}[0,\pi]$ and $\Delta c_{i}$ is the difference of the coordinates of the target unitary gate and the coordinates for the maximum overall fidelity $\mathcal{F}_{nl}(c_{1},c_{2},c_{3})_{\max}$ obtained from the optimization, Eq.~(\ref{eq:fidelity}) \footnote{This distance, can of course be calculated between any two points in the chamber.}. According to \cite{gilchrist2005dmc}, $\Delta_{nl}$ meets all distance measure criteria for pure processes and can be seen as a \emph{diagnostic measure}. Our experimental gate is located at a distance $\Delta_{nl}{\sim}0$ from the ideal \textsc{cz}. The uncertainty in this value is dominated by the numerical optimization. Upon closer inspection, this does not come at a surprise; any uncorrelated noise process such as depolarization or dephasing would show up as mixture, i.e. an uniform decrease of $\mathcal{F}_{nl}$ over the whole non-local space. Imperfections in optical components such as the PPBS central to our gate similarly lead to mixing because the underlying 2-qubit operations for reflectivity values around $\eta_{ideal}{=}1/3$ are non-unitary \cite{ralph2002loc}. A similar argument holds for other imperfections, such as temporal or spatial mode mismatch \footnote{In fact, most imperfections can be modeled as incoherent sums of different unitary processes, which would lead to several local fidelity maxima in the Weyl chamber.}. In other words, in contrast to the $\textsc{cu}$ gates demonstrated in \cite{lanyon2008sql}, our optical setup does not have any non-local unitary degrees of freedom.

We conclude that the nonlocal properties of our gate could not be improved by any unitary corrections. We therefore attribute the remaining reduction in fidelity to mixing, which is supported by the measured, non-ideal process purity of $89.8\pm0.4\%$.

This method, the projection of a quantum process into the nonlocal, unitary 2-qubit operator sub-space is likely to have a number of interesting applications in quantum information processing, e.g. process tomography, a topic which is rapidly increasing in importance as quantum computer architectures evolve. Suggested lines for further research are, for example, how different noise processes influence nonlocal properties of a quantum gate and nonlocal process discrimination \cite{laing2009eqp}.

In conclusion, we have implemented a matchgate circuit which allows universal computation when combined with the simple two-qubit \textsc{swap}. We characterized our gate using quantum process tomography and illustrated the fidelity overlap of the experimental process with all possible nonlocal gates in the Weyl chamber.

\begin{acknowledgments}
We wish to thank B.~P.~Lanyon and N.~K.~Langford for valuable input. We acknowledge financial support from the Australian Research Council Discovery and Federation Fellow programs and an IARPA-funded U.S. Army Research Office contract. SR acknowledges financial support by the FWF project CoQuS No. W1210-N16. AMS acknowledges support by the Natural Sciences and Engineering Research Council of Canada, Quantum Works and the Canadian Institute for Advanced Research.
\end{acknowledgments}

\begin{thebibliography}{23}
\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi
\expandafter\ifx\csname bibnamefont\endcsname\relax
  \def\bibnamefont#1{#1}\fi
\expandafter\ifx\csname bibfnamefont\endcsname\relax
  \def\bibfnamefont#1{#1}\fi
\expandafter\ifx\csname citenamefont\endcsname\relax
  \def\citenamefont#1{#1}\fi
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{\texttt{#1}}\fi
\expandafter\ifx\csname urlprefix\endcsname\relax\def\urlprefix{URL }\fi
\providecommand{\bibinfo}[2]{#2}
\providecommand{\eprint}[2][]{\url{#2}}

\bibitem[{\citenamefont{Nielsen and Chuang}(2000)}]{nielsen2000qca}
\bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Nielsen}} \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{I.}~\bibnamefont{Chuang}},
  \emph{\bibinfo{title}{Quantum computation and quantum information}}
  (\bibinfo{publisher}{Cambridge University Press}, \bibinfo{year}{2000}).

\bibitem[{\citenamefont{Dodd et~al.}(2002)\citenamefont{Dodd, Nielsen, Bremner,
  and Thew}}]{dodd2002uqc}
  J.L.~Dodd \emph{et~al.},
% \bibinfo{author}{\bibfnamefont{J.~L.} \bibnamefont{Dodd}},
% \bibinfo{author}{\bibfnamefont{M.~A.} \bibnamefont{Nielsen}},
% \bibinfo{author}{\bibfnamefont{M.~J.} \bibnamefont{Bremner}},
% \bibnamefont{and} \bibinfo{author}{\bibfnamefont{R.~T.} \bibnamefont{Thew}},
  \bibinfo{journal}{Phys. Rev. A} \textbf{\bibinfo{volume}{65}},
  \bibinfo{pages}{040301(R)} (\bibinfo{year}{2002}).

\bibitem[{\citenamefont{Lanyon et~al.}(2008)\citenamefont{Lanyon, Barbieri,
  Almeida, Jennewein, Ralph, Resch, Pryde, O'Brien, Gilchrist, and White}}]{lanyon2008sql}
  B.~Lanyon \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{B.}~\bibnamefont{Lanyon}},
%  \bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Barbieri}},
%  \bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Almeida}},
%  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Jennewein}},
%  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Ralph}},
%  \bibinfo{author}{\bibfnamefont{K.}~\bibnamefont{Resch}},
%  \bibinfo{author}{\bibfnamefont{G.}~\bibnamefont{Pryde}},
%  \bibinfo{author}{\bibfnamefont{J.L.}~\bibnamefont{O'Brien}},
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Gilchrist}},
%  \bibnamefont{and} \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{White}},
  \bibinfo{journal}{Nature Physics} \textbf{\bibinfo{volume}{5}},
  \bibinfo{pages}{134} (\bibinfo{year}{2008}).

\bibitem[{\citenamefont{Monz et~al.}(2009)\citenamefont{Monz, Kim, H\"{a}nsel,
  Riebe, Villar, Schindler, Chwalla, Hennrich, and Blatt}}]{monz2008rqt}
  T.~Monz \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Monz}},
%  \bibinfo{author}{\bibfnamefont{K.}~\bibnamefont{Kim}},
%  \bibinfo{author}{\bibfnamefont{W.}~\bibnamefont{H\"{a}nsel}},
%  \bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Riebe}},
%  \bibinfo{author}{\bibfnamefont{A.~S.} \bibnamefont{Villar}},
%  \bibinfo{author}{\bibfnamefont{P.}~\bibnamefont{Schindler}},
%  \bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Chwalla}},
%  \bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Hennrich}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Blatt}},
  \bibinfo{journal}{Phys. Rev. Lett.} \textbf{\bibinfo{volume}{102}},
  \bibinfo{eid}{040501} (\bibinfo{year}{2009}).

\bibitem[{\citenamefont{Valiant}(2002)}]{valiant2002qcc}
\bibinfo{author}{\bibfnamefont{L.}~\bibnamefont{Valiant}},
  \bibinfo{journal}{SIAM Journal on Computing} \textbf{\bibinfo{volume}{31}},
  \bibinfo{pages}{1229} (\bibinfo{year}{2002}).

\bibitem[{\citenamefont{Terhal and DiVincenzo}(2002)}]{terhal2002csn}
\bibinfo{author}{\bibfnamefont{B.M.}~\bibnamefont{Terhal}} \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{D.P.}~\bibnamefont{DiVincenzo}},
  \bibinfo{journal}{Phys. Rev. A} \textbf{\bibinfo{volume}{65}},
  \bibinfo{pages}{032325} (\bibinfo{year}{2002}).

\bibitem[{\citenamefont{Jozsa and Miyake}(2008)}]{jozsa2008mac}
\bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Jozsa}} \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Miyake}},
  \bibinfo{journal}{Proceedings of the Royal Society A} \textbf{\bibinfo{volume}{464}},
  \bibinfo{pages}{3089} (\bibinfo{year}{2008}).

\bibitem[{\citenamefont{Verstraete et~al.}(2009)\citenamefont{Verstraete,
  Cirac, and Latorre}}]{verstraete2009qcs}
\bibinfo{author}{\bibfnamefont{F.}~\bibnamefont{Verstraete}},
  \bibinfo{author}{\bibfnamefont{J.I.} \bibnamefont{Cirac}}, \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{J.I.} \bibnamefont{Latorre}},
  \bibinfo{journal}{Phys. Rev. A} \textbf{\bibinfo{volume}{79}},
  \bibinfo{pages}{032316} (\bibinfo{year}{2009}).

\bibitem[{\citenamefont{Vidal and Dawson}(2004)}]{vidal2004uqc}
\bibinfo{author}{\bibfnamefont{G.}~\bibnamefont{Vidal}} \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{C.M.}~\bibnamefont{Dawson}},
  \bibinfo{journal}{Phys. Rev. A} \textbf{\bibinfo{volume}{69}},
  \bibinfo{pages}{010301(R)}
  (\bibinfo{year}{2004}).

\bibitem[{\citenamefont{Zhang et~al.}(2004)\citenamefont{Zhang, Vala, Sastry,
  and Whaley}}]{zhang2004mct}
  J.~Zhang \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{J.}~\bibnamefont{Zhang}},
%  \bibinfo{author}{\bibfnamefont{J.}~\bibnamefont{Vala}},
%  \bibinfo{author}{\bibfnamefont{S.}~\bibnamefont{Sastry}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{K.}~\bibnamefont{Whaley}},
  \bibinfo{journal}{Phys. Rev. Lett.} \textbf{\bibinfo{volume}{93}},
  \bibinfo{pages}{020502} (\bibinfo{year}{2004}).

\bibitem[{\citenamefont{O'Brien et~al.}(2003)\citenamefont{O'Brien, Pryde,
  White, Ralph, and Branning}}]{obrien2003dao}
  J.L.~O'Brien and G.~Pryde \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{J.L.}~\bibnamefont{O'Brien}},
%  \bibinfo{author}{\bibfnamefont{G.}~\bibnamefont{Pryde}},
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{White}},
%  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Ralph}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{Branning}},
  \bibinfo{journal}{Nature} \textbf{\bibinfo{volume}{426}},
  \bibinfo{pages}{264} (\bibinfo{year}{2003}).

\bibitem[{\citenamefont{Gasparoni et~al.}(2004)\citenamefont{Gasparoni, Pan,
  Walther, Rudolph, and Zeilinger}}]{gasparoni2004rpc}
  S.~Gasparoni \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{S.}~\bibnamefont{Gasparoni}},
%  \bibinfo{author}{\bibfnamefont{J.}~\bibnamefont{Pan}},
%  \bibinfo{author}{\bibfnamefont{P.}~\bibnamefont{Walther}},
%  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Rudolph}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Zeilinger}},
  \bibinfo{journal}{Phys. Rev. Lett.} \textbf{\bibinfo{volume}{93}},
  \bibinfo{pages}{020504} (\bibinfo{year}{2004}).

\bibitem[{\citenamefont{Barenco et~al.}(1995)\citenamefont{Barenco, Bennett,
  Cleve, DiVincenzo, Margolus, Shor, Sleator, Smolin, and
  Weinfurter}}]{barenco1995egq}
  A.~Barenco \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Barenco}},
%  \bibinfo{author}{\bibfnamefont{C.}~\bibnamefont{Bennett}},
%  \bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Cleve}},
%  \bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{DiVincenzo}},
%  \bibinfo{author}{\bibfnamefont{N.}~\bibnamefont{Margolus}},
%  \bibinfo{author}{\bibfnamefont{P.}~\bibnamefont{Shor}},
%  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Sleator}},
%  \bibinfo{author}{\bibfnamefont{J.}~\bibnamefont{Smolin}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{H.}~\bibnamefont{Weinfurter}},
  \bibinfo{journal}{Phys. Rev. A} \textbf{\bibinfo{volume}{52}},
  \bibinfo{pages}{3457} (\bibinfo{year}{1995}).

\bibitem[{\citenamefont{Langford et~al.}(2005)\citenamefont{Langford, Weinhold,
  Prevedel, Resch, Gilchrist, O'Brien, Pryde, and White}}]{langford2005dse}
  N.K.~Langford \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{N.~K.}~\bibnamefont{Langford}},
%  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Weinhold}},
%  \bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Prevedel}},
%  \bibinfo{author}{\bibfnamefont{K.}~\bibnamefont{Resch}},
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Gilchrist}},
%  \bibinfo{author}{\bibfnamefont{J.L.}~\bibnamefont{O'Brien}},
%  \bibinfo{author}{\bibfnamefont{G.}~\bibnamefont{Pryde}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{White}},
  \bibinfo{journal}{Phys. Rev. Lett.} \textbf{\bibinfo{volume}{95}},
  \bibinfo{pages}{210504} (\bibinfo{year}{2005}).

\bibitem[{\citenamefont{Kiesel et~al.}(2005)\citenamefont{Kiesel, Schmid,
  Weber, Ursin, and Weinfurter}}]{kiesel2005loc}
  N.~Kiesel \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{N.}~\bibnamefont{Kiesel}},
%  \bibinfo{author}{\bibfnamefont{C.}~\bibnamefont{Schmid}},
%  \bibinfo{author}{\bibfnamefont{U.}~\bibnamefont{Weber}},
%  \bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Ursin}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{H.}~\bibnamefont{Weinfurter}},
  \bibinfo{journal}{Phys. Rev. Lett.} \textbf{\bibinfo{volume}{95}},
  \bibinfo{pages}{210505} (\bibinfo{year}{2005}).

\bibitem[{\citenamefont{Okamoto et~al.}(2005)\citenamefont{Okamoto, Hofmann,
  Takeuchi, and Sasaki}}]{okamoto2005doq}
  R.~Okamoto \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Okamoto}},
%  \bibinfo{author}{\bibfnamefont{H.~F.} \bibnamefont{Hofmann}},
%  \bibinfo{author}{\bibfnamefont{S.}~\bibnamefont{Takeuchi}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{K.}~\bibnamefont{Sasaki}},
  \bibinfo{journal}{Phys. Rev. Lett.} \textbf{\bibinfo{volume}{95}},
  \bibinfo{pages}{210506} (\bibinfo{year}{2005}).

\bibitem[{\citenamefont{Fedrizzi et~al.}(2007)\citenamefont{Fedrizzi, Herbst,
  Poppe, Jennewein, and Zeilinger}}]{fedrizzi2007wtf}
  A. Fedrizzi \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Fedrizzi}},
%  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Herbst}},
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Poppe}},
%  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Jennewein}},
%  \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Zeilinger}},
  \bibinfo{journal}{Opt. Express} \textbf{\bibinfo{volume}{15}},
  \bibinfo{pages}{15377} (\bibinfo{year}{2007}).

\bibitem[{\citenamefont{O'Brien et~al.}(2004)\citenamefont{O'Brien, Pryde,
  Gilchrist, James, Langford, Ralph, and White}}]{obrien2004qpt}
  J.L.~O'Brien \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{J.L.}~\bibnamefont{O'Brien}},
%  \bibinfo{author}{\bibfnamefont{G.}~\bibnamefont{Pryde}},
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Gilchrist}},
%  \bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{James}},
%  \bibinfo{author}{\bibfnamefont{N.~K.}~\bibnamefont{Langford}},
%  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Ralph}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{White}},
  \bibinfo{journal}{Phys. Rev. Lett.} \textbf{\bibinfo{volume}{93}},
  \bibinfo{pages}{080502} (\bibinfo{year}{2004}).

\bibitem[{\citenamefont{Kraus and Cirac}(2001)}]{kraus2001oce}
\bibinfo{author}{\bibfnamefont{B.}~\bibnamefont{Kraus}} \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{J.I.}~\bibnamefont{Cirac}},
  \bibinfo{journal}{Phys. Rev. A} \textbf{\bibinfo{volume}{63}},
  \bibinfo{pages}{062309}
  (\bibinfo{year}{2001}).

\bibitem[{\citenamefont{Zhang et~al.}(2003)\citenamefont{Zhang, Vala, Sastry,
  and Whaley}}]{zhang2003gtn}
  J.~Zhang \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{J.}~\bibnamefont{Zhang}},
%  \bibinfo{author}{\bibfnamefont{J.}~\bibnamefont{Vala}},
%  \bibinfo{author}{\bibfnamefont{S.}~\bibnamefont{Sastry}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{K.}~\bibnamefont{Whaley}},
  \bibinfo{journal}{Phys. Rev. A} \textbf{\bibinfo{volume}{67}},
  \bibinfo{pages}{042313} (\bibinfo{year}{2003}).

\bibitem[{\citenamefont{Gilchrist et~al.}(2005)\citenamefont{Gilchrist,
  Langford, and Nielsen}}]{gilchrist2005dmc}
\bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Gilchrist}},
  \bibinfo{author}{\bibfnamefont{N.K.} \bibnamefont{Langford}},
  \bibnamefont{and} \bibinfo{author}{\bibfnamefont{M.~A.}
  \bibnamefont{Nielsen}}, \bibinfo{journal}{Phys. Rev. A}
  \textbf{\bibinfo{volume}{71}}, \bibinfo{pages}{062310}
  (\bibinfo{year}{2005}).

\bibitem[{\citenamefont{Ralph et~al.}(2002)\citenamefont{Ralph, Langford, Bell,
  and White}}]{ralph2002loc}
  T.C.~Ralph \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{T.C.} \bibnamefont{Ralph}},
%  \bibinfo{author}{\bibfnamefont{N.K.} \bibnamefont{Langford}},
%  \bibinfo{author}{\bibfnamefont{T.B.} \bibnamefont{Bell}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{A.G.} \bibnamefont{White}},
  \bibinfo{journal}{Phys. Rev. A} \textbf{\bibinfo{volume}{65}},
  \bibinfo{pages}{062324} (\bibinfo{year}{2002}).

\bibitem[{\citenamefont{Laing et~al.}(2009)\citenamefont{Laing, Rudolph, and
  O'Brien}}]{laing2009eqp}
\bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Laing}},
  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Rudolph}}, \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{J.L.}~\bibnamefont{O'Brien}},
  \bibinfo{journal}{Phys. Rev. Lett.} \textbf{\bibinfo{volume}{102}},
  \bibinfo{pages}{160502} (\bibinfo{year}{2009}).

\end{thebibliography}


\section{Additional online material}

We briefly review the universality proof given by R. Jozsa and A. Miyake in \cite{jozsa2008mac}, which involves showing how one can construct an already known universal set from $\textsc{g}_\textsc{ab} {+} \textsc{swap}$. Because $\textsc{g}_\textsc{ab}$ is intrinsically a two-qubit gate and does not allow a change of parity of the input state, it is not straightforward to construct arbitrary single-qubit unitaries. This is solved in \cite{jozsa2008mac} by encoding the logical qubits $\ket{0}_{L}$, $\ket{1}_{L}$, into two physical qubits which have the same parity $\ket{0}_{L}{=}\ket{00}, \ket{1}_{L}{=}\ket{11}$. A symmetric $\textsc{g}_\textsc{aa}$ acting on the two physical qubits  then performs the single-qubit unitary $\textsc{a}$ on the logical qubit, Fig.~\ref{fig:encoding}a). This 2-qubit encoding is universal with next-next-nearest neighbor interactions, whereas a more complicated 4-qubit encoding, which requires the non-trivial $\textsc{g}_\textsc{zx}$, allows universal quantum computing with only next-nearest neigbour interactions \cite{jozsa2008mac}. 

Next, we need an entangling gate which can act between two encoded logical qubits. This can be achieved by adding \textsc{swap}, because, as illustrated in Fig.~\ref{fig:encoding}b), $\textsc{cz}{=} \textsc{g}_\textsc{hh} {\times}\textsc{swap} {\times} \textsc{g}_\textsc{xx} {\times} \textsc{g}_\textsc{hh}$, where $\textsc{x}$ denotes the $\sigma_x$ Pauli operator. In summary, the minimal set of matchgates needed for universal quantum computing is $\textsc{g}_\textsc{hh}$ and $\textsc{g}_\textsc{tt}$, which implement the single-qubit gates $\textsc{h}$ and $\textsc{t}$ on the encoded dual-qubit space, and $\textsc{g}_\textsc{xx}$, $\textsc{g}_\textsc{hh}$ and \textsc{swap}, which together form a \textsc{cz}.

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.47\textwidth]{figA1.eps}
\caption{Matchgate universality proof \cite{jozsa2008mac}. a) Symmetric matchgates $\textsc{g}_{\textsc{aa}}$ act on two physical qubits which represent one logical qubit. b) \textsc{cz} can be constructed using symmetric matchgates and \textsc{swap}. Dotted ellipses represent logical qubits.}
\label{fig:encoding}
\end{center}
\end{figure}

\end{document}

0909.3016.extracted_bib
\begin{thebibliography}{23}
\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi
\expandafter\ifx\csname bibnamefont\endcsname\relax
  \def\bibnamefont#1{#1}\fi
\expandafter\ifx\csname bibfnamefont\endcsname\relax
  \def\bibfnamefont#1{#1}\fi
\expandafter\ifx\csname citenamefont\endcsname\relax
  \def\citenamefont#1{#1}\fi
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{\texttt{#1}}\fi
\expandafter\ifx\csname urlprefix\endcsname\relax\def\urlprefix{URL }\fi
\providecommand{\bibinfo}[2]{#2}
\providecommand{\eprint}[2][]{\url{#2}}

\bibitem[{\citenamefont{Nielsen and Chuang}(2000)}]{nielsen2000qca}
\bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Nielsen}} \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{I.}~\bibnamefont{Chuang}},
  \emph{\bibinfo{title}{Quantum computation and quantum information}}
  (\bibinfo{publisher}{Cambridge University Press}, \bibinfo{year}{2000}).

\bibitem[{\citenamefont{Dodd et~al.}(2002)\citenamefont{Dodd, Nielsen, Bremner,
  and Thew}}]{dodd2002uqc}
  J.L.~Dodd \emph{et~al.},
% \bibinfo{author}{\bibfnamefont{J.~L.} \bibnamefont{Dodd}},
% \bibinfo{author}{\bibfnamefont{M.~A.} \bibnamefont{Nielsen}},
% \bibinfo{author}{\bibfnamefont{M.~J.} \bibnamefont{Bremner}},
% \bibnamefont{and} \bibinfo{author}{\bibfnamefont{R.~T.} \bibnamefont{Thew}},
  \bibinfo{journal}{Phys. Rev. A} \textbf{\bibinfo{volume}{65}},
  \bibinfo{pages}{040301(R)} (\bibinfo{year}{2002}).

\bibitem[{\citenamefont{Lanyon et~al.}(2008)\citenamefont{Lanyon, Barbieri,
  Almeida, Jennewein, Ralph, Resch, Pryde, O'Brien, Gilchrist, and White}}]{lanyon2008sql}
  B.~Lanyon \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{B.}~\bibnamefont{Lanyon}},
%  \bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Barbieri}},
%  \bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Almeida}},
%  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Jennewein}},
%  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Ralph}},
%  \bibinfo{author}{\bibfnamefont{K.}~\bibnamefont{Resch}},
%  \bibinfo{author}{\bibfnamefont{G.}~\bibnamefont{Pryde}},
%  \bibinfo{author}{\bibfnamefont{J.L.}~\bibnamefont{O'Brien}},
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Gilchrist}},
%  \bibnamefont{and} \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{White}},
  \bibinfo{journal}{Nature Physics} \textbf{\bibinfo{volume}{5}},
  \bibinfo{pages}{134} (\bibinfo{year}{2008}).

\bibitem[{\citenamefont{Monz et~al.}(2009)\citenamefont{Monz, Kim, H\"{a}nsel,
  Riebe, Villar, Schindler, Chwalla, Hennrich, and Blatt}}]{monz2008rqt}
  T.~Monz \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Monz}},
%  \bibinfo{author}{\bibfnamefont{K.}~\bibnamefont{Kim}},
%  \bibinfo{author}{\bibfnamefont{W.}~\bibnamefont{H\"{a}nsel}},
%  \bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Riebe}},
%  \bibinfo{author}{\bibfnamefont{A.~S.} \bibnamefont{Villar}},
%  \bibinfo{author}{\bibfnamefont{P.}~\bibnamefont{Schindler}},
%  \bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Chwalla}},
%  \bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Hennrich}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Blatt}},
  \bibinfo{journal}{Phys. Rev. Lett.} \textbf{\bibinfo{volume}{102}},
  \bibinfo{eid}{040501} (\bibinfo{year}{2009}).

\bibitem[{\citenamefont{Valiant}(2002)}]{valiant2002qcc}
\bibinfo{author}{\bibfnamefont{L.}~\bibnamefont{Valiant}},
  \bibinfo{journal}{SIAM Journal on Computing} \textbf{\bibinfo{volume}{31}},
  \bibinfo{pages}{1229} (\bibinfo{year}{2002}).

\bibitem[{\citenamefont{Terhal and DiVincenzo}(2002)}]{terhal2002csn}
\bibinfo{author}{\bibfnamefont{B.M.}~\bibnamefont{Terhal}} \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{D.P.}~\bibnamefont{DiVincenzo}},
  \bibinfo{journal}{Phys. Rev. A} \textbf{\bibinfo{volume}{65}},
  \bibinfo{pages}{032325} (\bibinfo{year}{2002}).

\bibitem[{\citenamefont{Jozsa and Miyake}(2008)}]{jozsa2008mac}
\bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Jozsa}} \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Miyake}},
  \bibinfo{journal}{Proceedings of the Royal Society A} \textbf{\bibinfo{volume}{464}},
  \bibinfo{pages}{3089} (\bibinfo{year}{2008}).

\bibitem[{\citenamefont{Verstraete et~al.}(2009)\citenamefont{Verstraete,
  Cirac, and Latorre}}]{verstraete2009qcs}
\bibinfo{author}{\bibfnamefont{F.}~\bibnamefont{Verstraete}},
  \bibinfo{author}{\bibfnamefont{J.I.} \bibnamefont{Cirac}}, \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{J.I.} \bibnamefont{Latorre}},
  \bibinfo{journal}{Phys. Rev. A} \textbf{\bibinfo{volume}{79}},
  \bibinfo{pages}{032316} (\bibinfo{year}{2009}).

\bibitem[{\citenamefont{Vidal and Dawson}(2004)}]{vidal2004uqc}
\bibinfo{author}{\bibfnamefont{G.}~\bibnamefont{Vidal}} \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{C.M.}~\bibnamefont{Dawson}},
  \bibinfo{journal}{Phys. Rev. A} \textbf{\bibinfo{volume}{69}},
  \bibinfo{pages}{010301(R)}
  (\bibinfo{year}{2004}).

\bibitem[{\citenamefont{Zhang et~al.}(2004)\citenamefont{Zhang, Vala, Sastry,
  and Whaley}}]{zhang2004mct}
  J.~Zhang \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{J.}~\bibnamefont{Zhang}},
%  \bibinfo{author}{\bibfnamefont{J.}~\bibnamefont{Vala}},
%  \bibinfo{author}{\bibfnamefont{S.}~\bibnamefont{Sastry}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{K.}~\bibnamefont{Whaley}},
  \bibinfo{journal}{Phys. Rev. Lett.} \textbf{\bibinfo{volume}{93}},
  \bibinfo{pages}{020502} (\bibinfo{year}{2004}).

\bibitem[{\citenamefont{O'Brien et~al.}(2003)\citenamefont{O'Brien, Pryde,
  White, Ralph, and Branning}}]{obrien2003dao}
  J.L.~O'Brien and G.~Pryde \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{J.L.}~\bibnamefont{O'Brien}},
%  \bibinfo{author}{\bibfnamefont{G.}~\bibnamefont{Pryde}},
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{White}},
%  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Ralph}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{Branning}},
  \bibinfo{journal}{Nature} \textbf{\bibinfo{volume}{426}},
  \bibinfo{pages}{264} (\bibinfo{year}{2003}).

\bibitem[{\citenamefont{Gasparoni et~al.}(2004)\citenamefont{Gasparoni, Pan,
  Walther, Rudolph, and Zeilinger}}]{gasparoni2004rpc}
  S.~Gasparoni \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{S.}~\bibnamefont{Gasparoni}},
%  \bibinfo{author}{\bibfnamefont{J.}~\bibnamefont{Pan}},
%  \bibinfo{author}{\bibfnamefont{P.}~\bibnamefont{Walther}},
%  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Rudolph}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Zeilinger}},
  \bibinfo{journal}{Phys. Rev. Lett.} \textbf{\bibinfo{volume}{93}},
  \bibinfo{pages}{020504} (\bibinfo{year}{2004}).

\bibitem[{\citenamefont{Barenco et~al.}(1995)\citenamefont{Barenco, Bennett,
  Cleve, DiVincenzo, Margolus, Shor, Sleator, Smolin, and
  Weinfurter}}]{barenco1995egq}
  A.~Barenco \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Barenco}},
%  \bibinfo{author}{\bibfnamefont{C.}~\bibnamefont{Bennett}},
%  \bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Cleve}},
%  \bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{DiVincenzo}},
%  \bibinfo{author}{\bibfnamefont{N.}~\bibnamefont{Margolus}},
%  \bibinfo{author}{\bibfnamefont{P.}~\bibnamefont{Shor}},
%  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Sleator}},
%  \bibinfo{author}{\bibfnamefont{J.}~\bibnamefont{Smolin}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{H.}~\bibnamefont{Weinfurter}},
  \bibinfo{journal}{Phys. Rev. A} \textbf{\bibinfo{volume}{52}},
  \bibinfo{pages}{3457} (\bibinfo{year}{1995}).

\bibitem[{\citenamefont{Langford et~al.}(2005)\citenamefont{Langford, Weinhold,
  Prevedel, Resch, Gilchrist, O'Brien, Pryde, and White}}]{langford2005dse}
  N.K.~Langford \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{N.~K.}~\bibnamefont{Langford}},
%  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Weinhold}},
%  \bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Prevedel}},
%  \bibinfo{author}{\bibfnamefont{K.}~\bibnamefont{Resch}},
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Gilchrist}},
%  \bibinfo{author}{\bibfnamefont{J.L.}~\bibnamefont{O'Brien}},
%  \bibinfo{author}{\bibfnamefont{G.}~\bibnamefont{Pryde}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{White}},
  \bibinfo{journal}{Phys. Rev. Lett.} \textbf{\bibinfo{volume}{95}},
  \bibinfo{pages}{210504} (\bibinfo{year}{2005}).

\bibitem[{\citenamefont{Kiesel et~al.}(2005)\citenamefont{Kiesel, Schmid,
  Weber, Ursin, and Weinfurter}}]{kiesel2005loc}
  N.~Kiesel \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{N.}~\bibnamefont{Kiesel}},
%  \bibinfo{author}{\bibfnamefont{C.}~\bibnamefont{Schmid}},
%  \bibinfo{author}{\bibfnamefont{U.}~\bibnamefont{Weber}},
%  \bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Ursin}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{H.}~\bibnamefont{Weinfurter}},
  \bibinfo{journal}{Phys. Rev. Lett.} \textbf{\bibinfo{volume}{95}},
  \bibinfo{pages}{210505} (\bibinfo{year}{2005}).

\bibitem[{\citenamefont{Okamoto et~al.}(2005)\citenamefont{Okamoto, Hofmann,
  Takeuchi, and Sasaki}}]{okamoto2005doq}
  R.~Okamoto \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Okamoto}},
%  \bibinfo{author}{\bibfnamefont{H.~F.} \bibnamefont{Hofmann}},
%  \bibinfo{author}{\bibfnamefont{S.}~\bibnamefont{Takeuchi}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{K.}~\bibnamefont{Sasaki}},
  \bibinfo{journal}{Phys. Rev. Lett.} \textbf{\bibinfo{volume}{95}},
  \bibinfo{pages}{210506} (\bibinfo{year}{2005}).

\bibitem[{\citenamefont{Fedrizzi et~al.}(2007)\citenamefont{Fedrizzi, Herbst,
  Poppe, Jennewein, and Zeilinger}}]{fedrizzi2007wtf}
  A. Fedrizzi \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Fedrizzi}},
%  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Herbst}},
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Poppe}},
%  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Jennewein}},
%  \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Zeilinger}},
  \bibinfo{journal}{Opt. Express} \textbf{\bibinfo{volume}{15}},
  \bibinfo{pages}{15377} (\bibinfo{year}{2007}).

\bibitem[{\citenamefont{O'Brien et~al.}(2004)\citenamefont{O'Brien, Pryde,
  Gilchrist, James, Langford, Ralph, and White}}]{obrien2004qpt}
  J.L.~O'Brien \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{J.L.}~\bibnamefont{O'Brien}},
%  \bibinfo{author}{\bibfnamefont{G.}~\bibnamefont{Pryde}},
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Gilchrist}},
%  \bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{James}},
%  \bibinfo{author}{\bibfnamefont{N.~K.}~\bibnamefont{Langford}},
%  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Ralph}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{White}},
  \bibinfo{journal}{Phys. Rev. Lett.} \textbf{\bibinfo{volume}{93}},
  \bibinfo{pages}{080502} (\bibinfo{year}{2004}).

\bibitem[{\citenamefont{Kraus and Cirac}(2001)}]{kraus2001oce}
\bibinfo{author}{\bibfnamefont{B.}~\bibnamefont{Kraus}} \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{J.I.}~\bibnamefont{Cirac}},
  \bibinfo{journal}{Phys. Rev. A} \textbf{\bibinfo{volume}{63}},
  \bibinfo{pages}{062309}
  (\bibinfo{year}{2001}).

\bibitem[{\citenamefont{Zhang et~al.}(2003)\citenamefont{Zhang, Vala, Sastry,
  and Whaley}}]{zhang2003gtn}
  J.~Zhang \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{J.}~\bibnamefont{Zhang}},
%  \bibinfo{author}{\bibfnamefont{J.}~\bibnamefont{Vala}},
%  \bibinfo{author}{\bibfnamefont{S.}~\bibnamefont{Sastry}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{K.}~\bibnamefont{Whaley}},
  \bibinfo{journal}{Phys. Rev. A} \textbf{\bibinfo{volume}{67}},
  \bibinfo{pages}{042313} (\bibinfo{year}{2003}).

\bibitem[{\citenamefont{Gilchrist et~al.}(2005)\citenamefont{Gilchrist,
  Langford, and Nielsen}}]{gilchrist2005dmc}
\bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Gilchrist}},
  \bibinfo{author}{\bibfnamefont{N.K.} \bibnamefont{Langford}},
  \bibnamefont{and} \bibinfo{author}{\bibfnamefont{M.~A.}
  \bibnamefont{Nielsen}}, \bibinfo{journal}{Phys. Rev. A}
  \textbf{\bibinfo{volume}{71}}, \bibinfo{pages}{062310}
  (\bibinfo{year}{2005}).

\bibitem[{\citenamefont{Ralph et~al.}(2002)\citenamefont{Ralph, Langford, Bell,
  and White}}]{ralph2002loc}
  T.C.~Ralph \emph{et al.},
%  \bibinfo{author}{\bibfnamefont{T.C.} \bibnamefont{Ralph}},
%  \bibinfo{author}{\bibfnamefont{N.K.} \bibnamefont{Langford}},
%  \bibinfo{author}{\bibfnamefont{T.B.} \bibnamefont{Bell}}, \bibnamefont{and}
%  \bibinfo{author}{\bibfnamefont{A.G.} \bibnamefont{White}},
  \bibinfo{journal}{Phys. Rev. A} \textbf{\bibinfo{volume}{65}},
  \bibinfo{pages}{062324} (\bibinfo{year}{2002}).

\bibitem[{\citenamefont{Laing et~al.}(2009)\citenamefont{Laing, Rudolph, and
  O'Brien}}]{laing2009eqp}
\bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Laing}},
  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Rudolph}}, \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{J.L.}~\bibnamefont{O'Brien}},
  \bibinfo{journal}{Phys. Rev. Lett.} \textbf{\bibinfo{volume}{102}},
  \bibinfo{pages}{160502} (\bibinfo{year}{2009}).

\end{thebibliography}