## Abstract

Matchgates are an especially multiflorous class of two-qubit nearest-neighbour quantum gates, defined by a set of algebraic constraints. They occur for example in the theory of perfect matchings of graphs, non-interacting fermions and one-dimensional spin chains. We show that the computational power of circuits of matchgates is equivalent to that of space-bounded quantum computation with unitary gates, with space restricted to being logarithmic in the width of the matchgate circuit. In particular, for the conventional setting of polynomial-sized (logarithmic-space generated) families of matchgate circuits, known to be classically simulatable, we characterize their power as coinciding with polynomial-time and logarithmic-space-bounded universal unitary quantum computation.

## 1. Introduction

The study of relationships between various kinds of quantum computational resources is one of the most fundamental issues in the theory of quantum computation, and one may explore a variety of possible avenues. On the one hand, we may study the power of quantum computations that use a restricted class of gates or computational steps (that are generally not fully universal) e.g. computations with Clifford gates (Gottesman 1997; Nielsen & Chuang 2000) or with nearest-neighbour (n.n.) matchgates (Valiant 2002; Knill 2001; Terhal & DiVincenzo 2002; Jozsa & Miyake 2008.) (The term ‘n.n.’ here refers to the requirement that the matchgates act only on consecutive pairs of qubits in the one-dimensional qubit array of the circuit). Each of these gate classes is defined by suitable algebraic constraints and in these cases they lead to computations that turn out to be classically efficiently simulatable. Despite this classical ceiling on computing power, these quantum computational processes are still of considerable interest because, for example, both kinds can generate complex entangled states and hence illuminate the sometimes alleged blanket attribution of quantum computational power to the mere presence of entanglement.

A second approach is to allow unrestricted kinds of (suitably local, unitary) quantum gates, e.g. they may be freely chosen from some finite universal set, and then place restrictions on the nature and amount of free computational resources that are available for the computation. Examples of such resources include time (number of steps), space (number of qubits), circuit depth (parallel time), deterministic versus non-deterministic computation, etc. Perhaps the most familiar example of such a restriction is that of polynomially bounded time, but others that have been established as conceptually and practically significant in the literature of *classical* complexity theory may also be entertained.

For our present work the notion of (classical or quantum) *space-bounded* computation will be a fundamental ingredient. We digress here to give a brief intuitive account of it using the significant and illustrative case of logarithmic space-bounded computations, called *log-space computations* for short. Let *x*=*x*_{1}…*x*_{n} be the binary string input for a computation. We wish to develop a notion of the computation being carried out in a restricted space of size only . Although this space is too small to even contain the input, the notion can be made meaningful and natural as follows. The input is given in an area of memory called the input tape, that is *read only* and cannot be used for computational processing. (Use of the term ‘tape’ here is motivated by a more formal definition based on the Turing machine (TM) model, which is described in appendix A.) Computation is then carried out in a separate area of memory called the work tape, of size . As the computation proceeds, different parts of the input may be read and copied to the work tape but only a very small, logarithmic length part may be represented there at any one time. Note, however, that numbers from 1 to *n* can be represented with bits, so the algorithm can at least remember locations in the input and return to them later if desired. A familiar example of the spirit of these definitions is our everyday use of the Internet: we may access desired locations, downloading data for processing on our computer’s hard disk, and remember web addresses, but our hard disk is far too small to simultaneously contain the whole Internet.

The above considerations lead to well-defined notions of log-space computations for both classical and quantum computers, which we discuss in greater detail in appendix A. In the classical case (with deterministic computational steps) any log-space computation (if it halts) must run in polynomial time (Papadimitriou 1994; Arora & Barak 2009). In a similar vein in the quantum case, any log-space quantum computation may be simulated classically in polynomial time: qubits correspond to *O*(*poly*(*n*)) dimensions and the progress of the computation of *N* steps may then be classically directly calculated in time *O*(*N**poly*(*n*)). Thus, log-space quantum computation provides another natural class of classically efficiently simulatable quantum computations.

As mentioned above it is known (Valiant 2002; Knill 2001; Terhal & DiVincenzo 2002; Jozsa & Miyake 2008) that polynomial-sized circuits of n.n. matchgates can be classically efficiently simulated so that their computational power is at most that of classical poly-time computation. A main result of the present paper is the precise identification of their power—we show that it *coincides* with the computational power of quantum log-space computation (in which the computational steps are unitary operations rather than fully general trace preserving completely positive maps (Watrous 1999, 2003, 2009)). Thus we obtain an equivalence between a class of computations restricted by algebraic constraints (n.n. matchgates) on the one hand, and a class obtained by limitations on the amount of use of free computational resources (log-space computation with general unitary gates) on the other. Actually, we prove a more general result asserting an equivalence (in a precisely defined sense) between the computational power of general quantum circuits of size (number of gates) *M* and width (number of qubit lines) *m* on the one hand, and n.n. matchgate circuits of size *N*=*O*(2^{2m}*M*) and width *n*=2^{m+1} on the other hand (and then we can set and *M* = *poly*(*n*) to obtain the poly-bounded case mentioned above).

Our result is similar in spirit to a theorem of Aaronson & Gottesman (2004), who showed that the computational power of Clifford (or stabilizer) circuits coincides with that of the classical complexity class known as ⊕L (defined in terms of a certain kind of classical non-deterministic log-space computation). In contrast, in our case we have an equivalence between two kinds of *quantum* computations.

In the next section we will recall basic facts about the classical simulation of n.n. matchgate circuits, extending these results for our later purposes and establishing some notations. In §3 we give a precise statement of our results with reference to appendix A, which contains the definitions of space-bounded classical and quantum computation that we use. In §4 we give the proof of our main result, and in §5 some further concluding remarks are provided.

## 2. Quantum matchgate circuits and their classical simulation

We will follow the notational conventions used by Jozsa & Miyake (2008). Let *X*,*Y*,*Z* denote the standard qubit Pauli operators. A matchgate is defined to be a two-qubit gate *G*(*A*,*B*) of the form (in the computational basis)
2.1
where *A* and *B* are both in *S**U*(2) or both in *U*(2) with the *same determinant*. Thus the action of *G*(*A*,*B*) amounts to *A* acting in the even parity subspace (spanned by |00〉 and |11〉) and *B* acting in the odd parity subspace (spanned by |01〉 and |10〉).

For any quantum (matchgate or conventional) circuit *C*, its *size**N* is its total number of gates, and its *width**n* is the total number of qubit lines upon which its gates act. We will disregard circuits having qubit lines on which no gates act, so that *N*≥*n*/2 for all circuits to be considered.

A fundamental classical simulation result for matchgate circuits is the following (Jozsa & Miyake 2008) (cf. Valiant 2002; Knill 2001; Terhal & DiVincenzo 2002).

## Theorem 2.1.

*Consider any matchgate circuit of size N and width n, such that*:

*the matchgates G*(*A*,*B*)*act on n.n. qubit lines only*;*the input state is any computational basis state*|*x*_{1}…*x*_{n}〉;*the output is a final measurement in the computational basis on any single qubit line*.

*Then the output may be classically efficiently simulated. More precisely for any k we can classically compute, in poly*(

*N*)

*time, the expectation value*〈

*Z*

_{k}〉

_{out}=

*p*

_{0}−

*p*

_{1}(

*and hence also p*

_{0}

*and p*

_{1}),

*where p*

_{0},

*p*

_{1}

*are the outcome probabilities and Z*

_{k}

*is the Pauli Z operator on the k*

*th line*.

As in this theorem, two-qubit matchgates in this paper will always be taken to act only on *n.n.* qubit lines so henceforth the term ‘matchgate’ will mean ‘n.n. matchgate’.

For later purposes we will need some details of how this classical simulation is actually achieved. We begin by introducing the 2*n* hermitian operators on *n*-qubits (omitting tensor product symbols ⊗ throughout):
2.2
where *X* and *Y* are in the *k*th slot for *c*_{2k−1} and *c*_{2k}, and *k* ranges from 1 to *n*. Thus the operators *c*_{2k−1} and *c*_{2k} are associated to the *k*th qubit line. It is straightforward to check that these matrices satisfy the anti-commutation relations
2.3
These relations define a *Clifford algebra* on 2*n* generators and the operators in equation (2.2) constitute what is known as the Jordan–Wigner representation (Jordan & Wigner 1928) of the Clifford algebra.

Next, we note the following properties (all proved by Jozsa & Miyake 2008). If *U* is any matchgate acting on lines (*k*,*k*+1) then
2.4
where is a special orthogonal matrix and the *l*-summation extends over the four *c*_{l} operators associated to lines *k* and *k*+1. Furthermore, this association of rotations to matchgates is surjective, i.e. every arises from a matchgate *U* (unique up to an overall phase). To incorporate all lines *k* on an equal footing we can regard *R* as a rotation in 2*n* dimensions acting as the identity outside the four-dimensional span of dimensions 2*k*−1, 2*k*, 2*k*+1 and 2*k*+2.

Now let
represent the action of a circuit of *N* matchgates on input |*x*_{1}…*x*_{n}〉. Then for a final *Z* measurement on line *k* we have
2.5
From equation (2.2) it holds that
and so
2.6
Let *R*_{t} be the rotation associated to *U*_{t} via equation (2.4) (extended to 2*n* dimensions), and write *R*=*R*_{N}…*R*_{1}. Then from equations (2.5) and (2.6) we get
2.7
This finally gives our efficient classical simulation of matchgate circuits by noting the following features of the formula in equation (2.7):

*R*is a product of*N*matrices of size 2*n*×2*n*(with*n*≤2*N*) so*R*can be computed in time*poly*(*N*) by sequential matrix multiplication.The

*c*_{j}operators are all product operators and |*ψ*_{in}〉 is a product state of*n*qubits—so 〈*ψ*_{in}|*c*_{j}*c*_{l}|*ψ*_{in}〉 can be computed as a product of*n*factors in time*O*(*n*)=*O*(*N*), for each of the*O*(*n*^{2}) choices of (*j*,*l*).The summation in equation (2.7) has only

*O*(*n*^{2})=*O*(*N*^{2}) terms, so in view of (i) and (ii),*p*_{0}−*p*_{1}can be computed in time*poly*(*N*). In particular, polynomial-sized matchgate circuits (i.e.*N*=*poly*(*n*)) can be simulated classically in polynomial time.

To develop a relationship of such circuits to space-bounded quantum computation we begin by giving an alternative expression of equation (2.7). Consider first the case of *k*=1 (i.e. measurement on the first line) and |*ψ*_{in}〉=|0…0〉. A direct calculation with the Jordan–Wigner operators gives
2.8
Because the rows of the matrix *R* are orthonormal, the sum of terms in equation (2.7) with *j*=*l* vanishes, and we can write
2.9
where we have introduced the matrix of off-diagonal terms from equation (2.8):
2.10
i.e. is the block diagonal anti-symmetric matrix with *n* copies of
2.11
on the diagonal.

The matrices *R* and *S* have size 2*n*×2*n* and real entries, and using the Dirac notation |1〉,…,|2*n*〉 for an orthonormal basis in the associated real vector space we can write equation (2.9) as
2.12
(where we have used the fact that the transpose of a rotation matrix is its inverse). Note finally that *R* and *S* are actually (real) *unitary* matrices and hence can be viewed as *quantum operations* in 2*n* dimensions i.e. on rebits. Here and henceforth we will use the term ‘rebit’ to refer to a qubit whose state components (in the fixed basis being used) are restricted to be real numbers.

The general case of 〈*Z*_{k}〉 and a general input state |*ψ*_{in}〉 is similar: in equation (2.12) we replace 〈2| and |1〉 by 〈2*k*| and |2*k*−1〉, respectively, and *S*, depending on the input state, is replaced by the real antisymmetric matrix
2.13
A computational basis input state |*x*〉=|*x*_{1}…*x*_{n}〉 gives
which is a ‘pairwise swap’ operation with a conditional phase (−1)^{j+x⌈j/2⌉}, and then

The n.n. restriction on matchgate actions in theorem 2.1 is in fact a crucial ingredient for the classical simulability of the circuits (as indeed n.n. and next-n.n. actions are already universal for quantum computation; Jozsa & Miyake 2008). Note that n.n. matchgate actions may be extended to arbitrary line pairs using the qubit SWAP operation on n.n. lines. However, SWAP is *not* a matchgate (even though *S**W**A**P*=*G*(*I*,*X*) but *det*(*I*)≠*det**X*!) A closely related bonafide matchgate is the operation *W*=*G*(*Z*,*X*), being SWAP together with ‘introduction of a minus sign when both lines are 1’ i.e. a fermionic SWAP operation if we view qubit labels 0 and 1 as occupation numbers for fermionic modes. For n.n. lines *k* and *k*+1, the corresponding Jordan–Wigner operator pairs are interchanged under conjugation by *W**viz.**W*^{†}*c*_{2k+1}*W*=*c*_{2k−1} and *W*^{†}*c*_{2k+2}*W*=*c*_{2k} and therefore *W*^{†}*Z*_{k+1}*W*=*Z*_{k}.

A circuit *C* with input |*x*_{1}…*x*_{n}〉 and measurement on the *k*th line will be called *equivalent* to a circuit *D* with input |*y*_{1}…*y*_{m}〉 and measurement on the *l*th line, if they have the same probability distribution for their output measurements. (Strictly speaking we should here include a precision tolerance to allow for change of choice of finite basic gate sets, but this technical detail may be readily accommodated and we henceforth ignore it.)

Using the properties of *W* above we can standardize the form of matchgate circuits as follows, which will be convenient for later purposes.

## Lemma 2.2.

*Let C be any matchgate circuit of size N and width n≤2N, with input |x*_{1}*…x*_{n}*〉 and final measurement Z*_{k} *on the kth line. Then there is an equivalent matchgate circuit D of size N+O(n*^{2}*) and width n or n+1, with input |0…0〉 and final measurement Z*_{1} *on the first line.*

## Proof.

The description of *D* is obtained from *C* and its input string *x*_{1}…*x*_{n} as follows. Let *r* be the Hamming weight of the input string and let 0^{k} and 1^{k} denote length *k* strings of 0’s and 1’s, respectively. If *r* is even we take *n* lines for *D* initialized to |0^{n}〉. We then apply *r*/2 *G*(*X*,*X*) n.n. gates to the bottom *r*/2 lines pairs to obtain |0^{n−r}1^{r}〉. Next using *O*(*n*^{2}) n.n. *W*=*G*(*Z*,*X*) gates we successively swap the *r* lower 1’s into their positions in the input string to obtain ±|*x*_{1}…*x*_{n}〉. Next apply the circuit *C*. Finally if *C* has final measurement on line *k*, apply a ladder of *k*−1 n.n. *W* gates to swap the *k*th line into the first position, and the equivalent final measurement is now *Z*_{1}. This completes the description of *D* when *r* is even. If *r* is odd we take *n*+1 lines for *D*, applying ⌈*r*/2⌉ n.n. *G*(*X*,*X*) gates to get |0^{n−r}1^{r+1}〉. We then leave line *n*+1 untouched by any further gates and proceed as above for the first *n* lines to obtain *D*. ▪

## 3. Main results

For the remainder of this paper, *M**G*=*M**G*(*n*;*N*;*x*_{1}…*x*_{n};*k*) will denote a given matchgate circuit of width *n*, size *N*, input |*x*_{1}…*x*_{n}〉 and final measurement *Z*_{k} on the *k*th line. Similarly, *Q**C*=*Q**C*(*m*;*M*;*y*_{1}…*y*_{m}) will denote a quantum circuit of width *m*, size *M*, input |*y*_{1}…*y*_{m}〉 and final measurement (without loss of generality) *Z*_{1} on the first line.

To express our main results we will need the notion of a classical description or *encoding* of a quantum (matchgate or conventional) circuit. We will assume that all our circuits are composed of gates from fixed finite sets of one- and two-qubit gates, whose products densely generate the class of all gates of the kind being considered. In the proofs given in §4 below some particularly convenient sets will be chosen but using standard arguments based on the Solovay–Kitaev theorem (Nielsen & Chuang 2000) it may be shown that our results do not depend on such particular choices. The action of each gate in a quantum circuit of width *n* and size *N* can be specified by a triple (*g*,*i*,*j*), where *g* encodes which of the finite gate types it is and *i*,*j*∈{1,…,*n*} specify which of the qubit lines it acts upon. In any circuit we discard lines on which no gates act so *N* is at least *n*/2. The full circuit is then encoded as a concatenation of its sequential gate applications
3.1
All of these symbols may be represented as binary strings (of constant length for the gate types *g* and length for the line numbers *i* and *j*) giving an encoding of length for any circuit of width *n* and size *N*. This encoding may also include specification of an input *x*_{1}…*x*_{n} and line number *k* for the final measurement, if desired. In the case of matchgate circuits we could omit all the *j* values since for matchgates we always have *j*_{t}=*i*_{t}+1 for *t*=1,…,*N*.

## Theorem 3.1.

*The following equivalence between matchgate circuits and general quantum circuits holds.*

*Given any matchgate circuit M**G*(*n*;*N*;*x*_{1}…*x*_{n};*k*)*there exists an equivalent quantum circuit Q**C*(*m*;*M*;0…0)*with**and*.*Moreover, the encoding of the circuit*1*Q**C*can be computed from the encoding of the matchgate circuit*M**G*by means of a (classical ) space*computation*.*Conversely, given any quantum circuit Q**C*(*m*;*M*;*y*_{1}…*y*_{m})*there exists an equivalent matchgate circuit M**G*(*n*;*N*;0…0;1)*with n*=2^{m+1}*and N*=*O*(*M*2^{2m}).*Moreover, the encoding of the matchgate circuit M**G can be computed from the encoding of the circuit Q**C by means of a classical space O*(*m*)*computation*.

Before giving the proof in the next section, we discuss here some consequences. First, to illustrate the content of the theorem, consider a polynomial-sized matchgate circuit, i.e. one with *N*=*O*(*poly*(*n*)). Then theorem 3.1(i) states that it can be simulated by a circuit *Q**C* of *poly*(*n*) size and *exponentially compressed width*, and the translation of descriptions can be carried out with a comparatively modest (log-space) computational cost. The latter remark is important in that we would like the simulation of the matchgate circuit to be a feature of the *Q**C* circuit’s computational power rather than being subsumed in the computational power of the translation of *M**G* to *Q**C*. Conversely, Theorem 3.1(ii) with parameters and *M*=*O*(*poly*(*n*)) asserts that any *poly*(*n*) sized quantum circuit of logarithmic width may be simulated by a matchgate circuit of polynomial size (and hence also of polynomial width). In this sense we have a full equivalence between the computational power of polynomial-sized matchgate circuits and universal logarithmic-width polynomial-sized unitary quantum circuits (modulo classical log-space translations).

To elevate such observations to formal statements about quantum computational complexity classes we need to introduce suitably defined families of computational tasks (parameterized by increasing input size *n*) and associated computational complexity classes. When characterizing computational complexity in terms of the circuit model, we need to consider families of circuits subject to a suitable restriction for how these circuits are generated as a function of the input and its size *n*. In contrast, the TM model requires no such auxiliary condition, as a single TM can deal with inputs of all lengths. For example, for usual polynomial-time quantum computation we conventionally use families of circuits whose descriptions are generated from the input string by a polynomial-time classical computation. But the complexity classes that we are aiming to characterize (*viz*. poly-sized matchgate computations and a notion of log-space quantum computation) are themselves no stronger than classical polynomial-time computation, so we need to adopt a more strict condition. A natural choice is classical log-space generation, commonly used in classical complexity theory for classes that are contained within classical polynomial-time computation.

Let *Σ** denote the set of all finite length bit strings. A *promise problem* is a pair *A*=(*A*_{yes},*A*_{no}) of subsets with . Intuitively speaking, a promise problem expresses a computational decision problem, where the strings in the set *A*_{yes} are those input strings for which the correct answer is ‘yes’ (or the binary value 1) and the strings in *A*_{no} are those for which the correct answer is ‘no’ (or the binary value 0). Input strings contained in neither of the sets *A*_{yes} and *A*_{no} are ‘don’t care’ inputs for which no answer is required. Promise problems for which , i.e. that disallow ‘don’t care’ inputs, are called *languages* (and are generally represented simply by the set *A*_{yes}).

With this terminology in mind, consider the following definitions.

## Definition 3.2.

Log-space generated families of matchgate circuits and the complexity classes BMG, PMG, BQL_{U} and PQL_{U} are defined as follows:

A

*log-space generated*family of matchgate circuits is a classical log-space computable function*g*on*Σ** such that, for each*w*∈*Σ**, the string*g*(*w*) is an encoding of a matchgate circuit*M**G*(*n*;*N*;*x*_{1}…*x*_{n};*k*).A promise problem

*A*=(*A*_{yes},*A*_{no}) is computed with bounded error by a log-space generated family*g*of matchgate circuits if and only if, for all strings*w*∈*A*_{yes}the matchgate circuit encoded by*g*(*w*) outputs 1 with probability at least 2/3, and for all strings*w*∈*A*_{no}the matchgate circuit encoded by*g*(*w*) outputs 1 with probability at most 1/3.A promise problem

*A*=(*A*_{yes},*A*_{no}) is computed with unbounded error by a log-space generated family*g*of matchgate circuits if and only if, for all strings*w*∈*A*_{yes}the matchgate circuit encoded by*g*(*w*) outputs 1 with probability strictly greater than 1/2, and for all strings*w*∈*A*_{no}the matchgate circuit encoded by*g*(*w*) outputs 1 with probability at most 1/2.The class BMG consists of all promise problems computable with bounded error by a log-space generated family

*g*of matchgate circuits, and the class PMG consists of all promise problems computable with unbounded error log-space generated family*g*of matchgate circuits.The class BQL

_{U}consists of all promise problems computable with bounded error by a log-space unitary quantum computation, and the class PQL_{U}consists of all promise problems computable with unbounded error by a log-space unitary quantum computation. (These notions are described in appendix A.)

It was proved by Watrous (1999, 2003) that, when quantum operations are restricted to those expressible by matrices of algebraic numbers, it holds that PQL_{U}=PL, where PL is the class of promise problems computed with unbounded error by classical probabilistic TMs operating in logarithmic space.

In terms of the above-defined notions, theorem 3.1 has the following immediate corollaries.

## Corollary 3.3.

*Let* *be a family of probability distributions on Boolean values, parameterized by binary strings w. Then* *arises as the output distribution for a log-space generated family of matchgate circuits if and only if* *arises as the output distribution for a unitary log-space quantum computation.*

## Proof.

The two directions of implication follow easily from theorem 3.1, noting that then both directions of translation are computable in classical log-space, and using the interpretation (mentioned in appendix A, taking there) of log-space quantum computation in terms of log-space generated families of log-width quantum circuits. ▪

## Corollary 3.4.

*It holds that*

BMG=BQL

_{U},*and*PMG=PQL

_{U}.

We may alternatively use the notion of *completeness* of a language or promise problem for a complexity class to express the equivalence of the computational power of polynomial-sized matchgate circuits and log-space quantum computation. A promise problem *A*=(*A*_{yes},*A*_{no}) is *complete* for a complexity class if and any promise problem *B*=(*B*_{yes},*B*_{no}) in can be *reduced* to *A*. There are many differing notions for the reduction of one problem to another, but we will consider *log-space reductions*. The choice to consider log-space reductions is analogous to the log-space generation of circuit families, and provides a non-trivial notion of completeness for the classes under discussion.

## Definition 3.5.

A function is a *log-space reduction* from a promise problem A=(A_{yes},A_{no}) to another promise problem B=(B_{yes},B_{no}) if g is a (classical) log-space computable function and it holds that g(*w*)∈B_{yes} for all *w*∈A_{yes}, and g(*w*)∈B_{no} for all *w*∈A_{no}.

Thus, a promise problem *B* is *complete* for BQL_{U} if *B*∈BQL_{U} and, for every promise problem *A*∈BQL_{U}, there exists a log-space reduction *g* from *A* to *B*. The definition for PQL_{U} is similar.

Now consider the following promise problems that formalize the computational tasks of simulating matchgate circuits of the sort that we consider. (These problems are stated in a standard way that makes clear which strings belong to the yes- and no-sets.)

The bounded-error matchgate circuit problem (BMGC for short)

*Input:* An encoding of , a n.n. quantum matchgate

circuit, its input string and its output qubit.

*Yes:* The output of *MG* is 1 with probability .

*No:* The output of *MG* is 1 with probability .

The unbounded-error matchgate circuit problem (MGC for short)

*Input:* An encoding of , a n.n. quantum matchgate

circuit, its input string and its output qubit.

*Yes:* The output of *MG* is 1 with probability .

*No:* The output of *MG* is 1 with probability .

The equivalence between matchgate circuits and space-bounded quantum computations established by theorem 3.1 gives the following corollary.

## Corollary 3.6.

*With respect to classical log-space reductions, we have*

BMGC

*is*BQL_{U}-*complete, and*MGC

*is*PQL_{U}-*complete*.

Thus intuitively, any instance of any problem in BQL_{U} can be reduced to approximating the output of a matchgate circuit having bounded error, and conversely the latter can be computed in BQL_{U}. This corollary is formally similar to the result of Aaronson & Gottesman (2004) characterizing the computational power of stabilizer circuits, where it is shown that an analogously defined language for stabilizer circuits (rather than our matchgate circuits here) is complete for the complexity class ⊕L (again relative to log-space reductions).

## 4. Proof of theorem 3.1

### (a) Proof of theorem 3.1(*i*)

We will first describe a procedure for converting *M**G*(*n*;*N*;*x*_{1}…*x*_{n};*k*) into a circuit *Q**C* of the claimed size and width, and then discuss the implementation of this procedure in space . We will consider first the case where the given matchgate circuit takes the form *M**G*(*n*;*N*;0…0;1), and then apply lemma 2.2 to handle the general case. Without loss of generality, it will be assumed that *n* is a power of 2, and hereafter we will let .

For clarity of exposition (and without loss of generality) we will assume that all our matchgates are drawn from a particular finite set chosen as follows. Recall from equation (2.4) that matchgates correspond surjectively with rotations. Using the standard Euler decomposition (Hoffman *et al.* 1972) any such four-dimensional rotation can be expressed as a product of six rotations each of which acts non-trivially in one of the six two-dimensional co-ordinate subspaces of . Accordingly, we choose six basic matchgates that correspond to six such rotations, through an angle that is an irrational multiple of *π*. For example, we may simply take the rotations to be
4.1
with rotation angle . Then any matchgate (to suitable precision) may be represented as a circuit of these six basic matchgates. For convenience (cf. lemma 2.2) we can also include *G*(*X*,*X*) and *G*(*Z*,*X*) in our basic set.

Recall (cf. equation (2.12)) that the output probabilities of the matchgate circuit satisfy
Here *R*=*R*_{N}…*R*_{1} is the 2*n*-dimensional rotation corresponding to the product of the individual two-level rotations *R*_{t} of the matchgates (*g*_{t},*i*_{t},*i*_{t}+1) in the circuit *M**G*, and *S* is the 2*n*-dimensional matrix of equation (2.10). The circuit *Q**C* will be constructed to implement the computation illustrated in figure 1 for the unitary *U*=*S*^{−1}*R**S**R*^{−1}.

The real unitary operation *U*=*S*^{−1}*R**S**R*^{−1} acts in 2*n* dimensions, and for the computation described in figure 1 we need to provide a description of the controlled operation *Λ**U* as a circuit of two-qubit gates on *m* rebit lines. Each basic rotation *R*_{t} corresponding to a matchgate (*g*_{t},*i*_{t},*i*_{t}+1) acts non-trivially in the span of two basis states selected from |2*i*_{t}−1〉,|2*i*_{t}〉|2*i*_{t}+1〉 and |2*i*_{t}+2〉, and it acts as the identity in the (2*n*−2)-dimensional complementary subspace. Our strategy now is the following: we begin by expressing each of these basic rotations as a constant-sized circuit of multiply controlled single qubit rotations. Then we will use the fact (Barenco *et al.* 1995) that any *r*-fold controlled single-qubit gate can be implemented using *O*(*r*) one- and two-qubit operations, to build up our final circuit of elementary gates, of the claimed size.

Unfortunately, if we represent the dimensions |*i*〉 as rebit lines via the usual binary representation of the labels *i*=1,…,2*n*, then *R*_{t} will *not* be a two-qubit gate, and indeed it will generally act on all rebit lines. To circumvent this problem we instead use a Gray code to associate rebit lines to the 2*n* dimensions. A Gray code (Press *et al*. 2007) for the numbers 1,…,2*n* is a sequence of distinct binary strings, each of length , such that the strings corresponding to any consecutive numbers *i* and *i*+1 have Hamming distance 1. Such codes exist and the Gray code strings can be easily computed from the standard binary representation via a simple sequence of single bit additions (Press *et al*. 2007).

Now, as noted above, each basic matchgate rotation *R*_{t} acts within two of four consecutive dimensions and hence within the space of two Gray code strings of Hamming distance at most 3. If we conjugate *R*_{t} by suitable *X* and *Λ**X* gates that act on the rebit lines where the Gray code strings differ, and that are controlled by the Gray code line values where they agree, then the Hamming distance may always be reduced to 1, i.e. each *R*_{t} (with the conjugations in place) can be made to act within the two-dimensional subspace of a single rebit line conditioned on the bit values of all other lines that are specified by the (common) Gray code values on those lines.

As an illustrative example, suppose *R*_{t} acts within the two-dimensional span of the computational basis states |01*z*_{3}1*z*_{5}…*z*_{m−2}〉 and |10*z*_{3}0*z*_{5}…*z*_{m−2}〉 having Hamming distance 3, where *z*_{3}*z*_{5}…*z*_{m−2} is the fixed substring common to the two Gray code strings. If we apply the gate *X*_{2}, then *X*_{4}, then (*Λ**X*)_{12} and finally (*Λ**X*)_{14}, each conditioned on the values *z*_{3}*z*_{5}…*z*_{m−2} of lines 3 and 5 to *m*−2, then we obtain the basis states |00*z*_{3}0*z*_{5}…*z*_{m−2}〉 and |10*z*_{3}0*z*_{5}…*z*_{m−2}〉, respectively, i.e. the rotation action is mapped into the two-dimensional subspace of the first rebit controlled by the values 0*z*_{3}0*z*_{5}…*z*_{m−2} on the remaining lines.

Next, we use the algorithm from Section 7.5 of Barenco *et al*. (1995) for representing an *r*-fold controlled operation *Λ*^{r}*T* (for a single qubit gate *T*) in terms of a circuit of *O*(*r*) two-qubit gates, which requires the addition of one additional ancillary qubit. Applying this for *r*≤*m*−2, and where *T* is our two-dimensional rotation or one of the extra *X* operations in the conjugations above, we obtain the description of the controlled-*R* operation (and analogously also controlled-*R*^{−1}) needed for the computation in figure 1 as a circuit of two-qubit gates.

Similarly, for the operation *S*, we see from its block diagonal form equation (2.10) that *S* can be represented as a product of operations each of which acts non-trivially only in two consecutive dimensions. Hence by using the same techniques as above we can express *S* as a circuit of two-local gates on rebit lines corresponding to the Gray code. Alternatively, we can note that equations (2.10) and (2.11) show that in the usual binary representation of the basis state labels, *S* has the local form . Then using a simple -sized circuit (Press *et al*. 2007) that translates between the Gray code and usual binary representation, we can get a circuit of size for the required controlled-*S* operations.

Assembling these ingredients, we obtain a circuit on rebit lines described in figure 1 for the operation *U*=*S*^{−1}*R**S**R*^{−1}. If the original matchgate circuit had size *N* and width *n* then the final circuit has size and width *m*. The -factor increase in size arises from the algorithm of Barenco *et al*. (1995) to decompose an -controlled operation into elementary operations. Thus, we have achieved the transformation

For the general case where *M**G* takes the form *M**G*(*n*;*N*;*x*_{1}…*x*_{n};*k*), one may follow the same procedure above after first applying the translation process of lemma 2.2. This requires the concatenation of sequences of gates to the beginning and end of the encoding of the circuit *M**G*, but otherwise does not involve any computation on the gates of *M**G* itself. This results in a matchgate circuit of the standard form *M**G*(*n*;*N*+*O*(*n*^{2});0…0;1).

Finally, we point out that the succession of translations described above can be achieved by a classical computation bounded to take place in space by noting the following facts:

The gates of

*M**G*are processed one at a time to obtain the gates of*Q**C*. The computation requires one pass through the encoding of*M**G*to construct the gates of*Q**C*corresponding to the operator*R*, and a second pass in the opposite direction to obtain the gates of*Q**C*corresponding to*R*^{−1}.Each gate of

*M**G*is encoded as a string of length , and it is clear that the computation of the gates of*Q**C*corresponding to each such gate can be computed in space . In particular, space is sufficient to translate any number*i*∈{1,…,2*n*} expressed in binary into its Gray code representation, to compute the required conjugations by*X*and*Λ**X*gates, and to implement the procedure of Barenco*et al*. (1995) on the required gates (keeping in mind that the individual two-qubit gates resulting from this procedure are output sequentially and need not all be stored simultaneously).The additional gates that are added by the construction of lemma 2.2 are easily generated one-by-one in space , and can be incorporated into the procedure described above by the addition of space.

This completes the proof of theorem 3.1(i).

### (b) Proof of theorem 3.1(*i**i*)

Given a description of a quantum circuit *Q**C*(*m*;*M*;*y*_{1}…*y*_{m}) we will generate an equivalent matchgate circuit *M**G*(*n*=2^{m+1};*N*=*O*(2^{2m}*M*);*x*_{1}…*x*_{n}=0…0;*k*=1) and the translation of description will be computable in space *O*(*m*). Without loss of generality, we may take *y*_{1}…*y*_{m}=0…0 (as the description of the *Q**C* circuit may be easily prefixed by *X* gates corresponding to the given *y*_{1}…*y*_{m} values.)

Let *V* denote the total unitary operation of the *Q**C* circuit. Then its output distribution is the unique binary distribution with mean
4.2
On the other hand, for a hypothetical matchgate circuit *M**G* of width *n* we have
where arise from the circuit as described in §2. If we represent the 2*n* dimensions in binary as rebit lines then equation (2.11) shows that and
4.3
We will define *M**G* by exploiting the structural similarity between equations (4.2) and (4.3). Roughly speaking we will associate matchgates to the successive gates of *V* , choosing them so that their adjoint actions as per equation (2.4) will give an overall rotation that reproduces *V*^{†}. In this metamorphosis of equation (4.2) into equation (4.3) we will need to address three discrepancies between these formulae: (i) *V* is generally complex whereas *R* is real; (ii) 〈*Z*_{1}〉_{MG} is expressed as an off-diagonal matrix element whereas 〈*Z*_{1}〉_{QC} is a diagonal element; and (iii) 〈*Z*_{1}〉_{QC} has a central *Z*_{1} term whereas 〈*Z*_{1}〉_{MG} has in this position.

We begin by treating (ii) and (iii) together. Introduce the two-qubit controlled operation
where are *X*-basis states. Then
4.4
Next introduce the qubit swap operation *S**W**A**P*_{12} and *w*_{12}=*S**W**A**P*_{12} *v*. Then equation (4.4) gives
4.5
Now we extend the *Q**C* circuit by introducing an ancillary qubit *A* (hereafter located in the rightmost position in the binary description of the computational basis) and a post-processing by *w*_{1A} (where 1 denotes the first line of the given *Q**C* circuit) to obtain . Then equation (4.5) (with label 2 in that equation replaced by label A) gives
4.6
Note that if we label our Hilbert space dimensions by natural numbers counting from 1 to 2^{m+1} then |0…00_{A}〉 and |0…01_{A}〉 correspond to |1〉 and |2〉, respectively, and equation (4.6) gives
Comparing this expression with 〈*Z*_{1}〉_{MG} in equation (4.3) we see that the off-diagonal matrix elements as well as the central -terms (acting on the first line in both cases) are now in correspondence thus addressing issues (ii) and (iii) above. Furthermore, the translation of the *Q**C* circuit description for *V* into that for (i.e. adjoining a description of *w*_{1A}) is a simple process that can be carried out even in constant space.

To deal with issue (i) recall that real gates suffice for universal quantum computation (Bernstein & Vazirani 1997; McKague *et al.* 2009) and given any quantum circuit there is an equivalent circuit comprising real gates from the special orthogonal group that has one extra ancillary rebit line *B*. This construction is a direct consequence of the algebra isomorphism
between complex numbers and a class of real 2×2 matrices. Correspondingly to any *K*-qubit unitary gate *U*∈*U*(2^{K}) we associate the real gate
and to any *K*-qubit state |*ψ*〉 we associate the (*K*+1)-rebit state to map any quantum computation into an equivalent real one.

If the gates *U* of the *Q**C* circuit are from a universal set of one- and two-qubit gates then the corresponding ’s will be one-, two-, and three-rebit gates and we may assume that they are given already decomposed in terms of a finite real universal set of two-rebit gates. For this set we choose the six rotations through angle (cf. equation (4.1)) that act, respectively, in the six two-dimensional co-ordinate subspaces of . In this way we translate the original *Q**C* circuit into an equivalent circuit of width *m*+2 comprising these basic real gates and the translation can be achieved in *O*(*m*) space, for example by sequentially translating each successive gate of into its real version.

Each of the resulting basic gates is a rotation *T*_{k,k′} acting on some (not necessarily n.n.) pair (*k*,*k*′) of rebit lines. Let *τ* be the associated matrix, which by our choice of basic gates, acts non-trivially only in a two-dimensional subspace of . To associate a circuit of matchgates on *n*=2^{m+1} qubit lines we need to view the global gate *T*=*T*_{k,k′}⊗_{j≠k,k′}*I*_{j} as an operator on the full 2*n*=2^{m+2}-dimensional space with basis labelled *sequentially* as |1〉,…,|2*n*〉. By virtue of its tensor product structure the 2*n*×2*n* matrix of *T* amounts to the application of *n*/2 parallel instances of *τ*, acting in a set of *n*/2 disjoint four-dimensional co-ordinate subspaces. Furthermore, *τ* acts non-trivially in only two of its four dimensions so *T*=*T*_{1}*T*_{2}…*T*_{n/2} is then given as a product of *n*/2 rotations *T*_{i}, in 2*n* dimensions, each of which acts non-trivially only in the span of two basis states |*k*_{i}〉 and |*l*_{i}〉 (and acts as the identity in the (2*n*−2)-dimensional complement). Now if |*k*_{i}−*l*_{i}|≤3 then the rotation *T*_{i} is induced directly by a single matchgate *G*_{i} via equation (2.4). Here *G*_{i} is one of six basic matchgates that correspond to our choice of the six basic rotations. If |*k*_{i}−*l*_{i}|>3 recall that the matchgate *G*(*Z*,*X*) on qubit lines *k* and *k*+1 induces an associated rotation that swaps the pairs (2*k*−1,2*k*) and (2*k*+1,2*k*+2) with each other. Then the rotation *T*_{i} is induced by a basic matchgate *G*_{i} conjugated by a ladder of *O*(*n*) *G*(*Z*,*X*) matchgates (to bring (*k*_{i},*l*_{i}) into a position with |*k*_{i}−*l*_{i}|≤3). Thus each *T*_{i} corresponds to a circuit of *O*(*n*) matchgates so *T* (comprising *O*(*n*) *T*_{i}’s) corresponds to a matchgate circuit of size *O*(*n*^{2}). Then finally, our original *Q**C* circuit of width *m* and size *M* is translated into an equivalent matchgate circuit of width 2^{m+1} and size *O*(*M**n*^{2})=*O*(*M*2^{2m}) as claimed. Note that in the final translation, the renaming of the six basic rotations by their corresponding matchgates is a simple operation but the corresponding line labels for the matchgate actions range from 1 to *n*=2^{m+1} needing *O*(*m*)-bit specifications, which can be calculated in *O*(*m*) space using standard arithmetic operations. This completes the proof of theorem 3.1(ii).

## 5. Concluding remarks

We have demonstrated an equivalence (in the precise sense given in §3) between the computational power of matchgate circuits of width *n* and universal unitary quantum computation within an exponentially compressed space bound of qubits. This equivalence is particularly interesting in the case of classically efficiently simulatable quantum computations (cf. theorem 2.1) where the matchgate circuits (and then also the corresponding log-space-bounded circuits) have *p**o**l**y*(*n*) size. In the literature there are two seemingly different techniques for constructing classically simulatable quantum computations: (a) we have the normalizer formalism that underlies the simulability of stabilizer circuits, as expressed in the Gottesman–Knill theorem (Gottesman 1997). Generalizations of this technique have been considered in Clark *et al*. (2008) and it has been argued in Jozsa (2008) that the classical simulability of matchgate circuits in theorem 2.1 can be understood in terms of a suitably generalized normalizer construction too. Characteristically, this technique leads to circuits of gates that are subject to algebraic constraints (normalizer conditions) and despite their classical simulability, the associated computations can generate complex entangled states. (b) A second method for imposing classical simulability is to restrict the amount of entanglement in the states that may be generated in the course of the computation. Such states have correspondingly small classical descriptions which can then be exploited for classical simulation. Examples of this method include the near-separable computations of Jozsa & Linden (2003) and Vidal (2003) and use of the matrix product formalism (cf. Verstraete *et al*. (2008) for a comprehensive recent review) to impose bounds on the Schmidt rank across any partition of a multi-qubit state.

With the above in mind, our main results can be seen as providing a link between (a) and (b) showing that, at least for the case of matchgate computations, the associated normaliser formalism may be viewed as an example of a limitation on the amount of generic entanglement and *vice versa*.

Our results (especially corollary 3.4) provide alternative characterizations of some classically simulatable quantum complexity classes. Such classes, *ipso facto* contained within P (classical polynomial-time computation), have the following interesting feature: suppose we have any class C of classically simulatable quantum computations (that is not just classical computation itself i.e. we have a non-trivial quantum gate involved). Then we can argue that if the computational power of C is *full* classical polynomial-time (in a suitably strong sense, as below), it would follow that BPP equals BQP i.e. that the powers of polynomial-time classical and quantum (bounded error) computing coincide. Thus it is significant that our poly-sized circuits of matchgates should have a computational power that is strictly weaker than P (and similarly for stabiliser circuits). The intuitive argument is the following: we interpret the condition that C has full classical poly-time power in a strong sense, as meaning that any classical gate can be simulated (in a quantum-coherent fashion) by a circuit from C. Thus we can simulate a Toffoli gate. But it is known (Shi 2003) that the Toffoli gate plus any non-trivial (basis-changing) quantum gate is efficiently universal for quantum computation. Hence if C also has any such non-trivial quantum gate, then in addition to being classically simulatable, C must also be quantum universal. Note that the above argument does not apply to some possible classes of classically simulatable computations such as those in Van den Nest (2008), that can involve further global restrictions on the structure of allowed circuits e.g. although it may be possible to simulate a Toffoli gate, the definition of the class may yet exclude its appearance in a general position within a circuit.

Finally, we mention some possible avenues of significance of our results for further physical and implementational considerations.

Matchgate circuits are known to include the real-time dynamics of one-dimensional XY spin chain Hamiltonians with n.n. interactions (e.g. Knill 2001; Terhal & DiVincenzo 2002; Jozsa & Miyake 2008). Thus theorem 3.1(i) implies that a digital *quantum* simulation of the latter can be carried out employing a quantum computer which is exponentially smaller in its use of qubits than the original system. This may for example, allow for an experimental observation of a quantum phase transition induced by varying the parameters in the Hamiltonian (cf. Verstraete *et al*. 2009).

If there exist experimental situations in which matchgates are especially easy to realize, then the simulation of universal quantum computation using matchgates, that is implied by theorem 3.1(ii), may be of experimental interest to demonstrate quantum computational effects, albeit with an exponential overhead in circuit width. Recalling that matchgates correspond to unitary evolutions generated by quadratic Hamiltonians of fermionic creation and annihilation operators (Knill 2001; Terhal & DiVincenzo 2002; Jozsa & Miyake 2008), a prospective setting here might be a fermionic counterpart (Beenakker *et al*. 2004) of the Knill–Laflamme–Milburn scheme in linear optics, where the gates are supposed to be implemented by beam splitters using the point contacts of a two-dimensional electron gas.

Lastly, we recall that the symmetry of the special orthogonal group appeared abstractly in our developments, via the Clifford algebra formalism (cf. equation 2.4). However, it can also be emergent *physically* as exotic quantum statistics. For example, in the fractional quantum Hall effect with the filling fraction *ν*=5/2 or in recent topological insulator–superconductor structures, the quasi-particle excitations in the celebrated Moore–Read state behave as non-abelian (Ising) anyons (Moore & Read 1991), that can realize non-abelian quantum statistics of for 2*n* excitations (Nayak & Wilczek 1996), analogous to the transformations available in the matchgate formalism. The experimental observation of such anyonic behaviour is of current interest for condensed–matter physics, as well as for a potential implementation of topological quantum computation, where the anyon braiding operations would need to be supplemented by further non-topological operations to achieve universal quantum computation in the full Hilbert space (Kitaev 2003; Bravyi 2006). However, theorem 3.1(ii) implies that the action has an inherent universal computational capability, albeit within an exponentially compressed quantum space bound, that can then also be viewed in terms of matchgate computations.

## Acknowledgements

A.M., R.J., and B.K. acknowledge support from the EC network QICS which provided collaborative opportunities for this work. A.M. acknowledges helpful discussions with D. Gottesman, suggesting the technique used in equation (4.6), and with S. Wehner. A.M. and B.K. are grateful to H.J. Briegel for his support. R.J. is supported by UK’s EPSRC-funded QIP IRC and the EC network QAP. J.W. is supported by Canada’s NSERC, the Canadian Institute for Advanced Research (CIFAR) and the QuantumWorks Innovation Platform. B.K. acknowledges support of the FWF (Elise Richter Program). The research at the Perimeter Institute is supported by the Government of Canada through Industry Canada and by Ontario-MRI.

## Appendix A. Definitions of space-bounded computation

The notion of classical space-bounded computation that we use is the standard textbook one (cf. Papadimitriou 1994; Arora & Barak 2009), and for completeness we include a summary description here. The classical TMs that we consider have three tapes called the input, work and output tapes, respectively. Each tape is a sequence of cells which may contain one of three symbols: the blank symbol B, or one of the binary values 0 or 1. (Often one allows more symbols, but these ones are sufficient for the present discussion.) Conventionally, we take the tapes to be infinite to the right.

At any stage the TM has an *internal state**q*, chosen from a fixed finite set, and each tape has a *tape head* that scans one of its cells at each moment. The computational process of the TM is defined by a finite table of transition rules of the form
A1
where *q* is an internal state and *s*_{input},*s*_{work} are symbols on the input and work tape, respectively. Each *d* is either *L* (‘one step left’), *R* (‘one step right’) or *S* (‘stay in the same place’). The meaning of this instruction is the following: if the TM has the internal state *q*, and is scanning the symbols *s*_{input} and *s*_{work} on its input and work tapes, then

the internal state changes to

*r*,the input tape head moves in direction

*d*_{input},the symbol being scanned on the work tape is replaced by

*t*_{work}and the work tape head moves in direction*d*_{work}, andif

*t*_{output}is a non-blank symbol, then this symbol is written on the output tape and the output tape head moves right (while nothing happens to the output tape or tape head if*t*_{output}is a blank symbol).

These rules imply that the input tape is ‘read only’ and the output tape is ‘write only’. This is done so that the work tape effectively represents the memory of the TM, upon which various limitations can be defined. It is also common to impose the restriction that if *s*_{input} is the blank symbol then *d*_{input} cannot be *R*, which forces the input tape head to remain at most one square away from the actual input string on the input tape. (If this condition is not imposed, the position of the input tape head could be exploited to effectively store a large integer value that is not counted as part of the TM’s memory usage.) We assume the machine to be *deterministic*, which means that there can be only one transition rule whose left-hand side is given by any triple (*q*,*s*_{input},*s*_{work}).

To say that a TM is run on a particular binary input string *w* means that the TM is started in a distinguished starting state *q*_{start}, has *w* written left-justified on the input tape, one symbol per cell and with all other tape cells containing the blank symbol, and with all tape heads scanning the leftmost cells of their respective tapes. The transition rules then determine the steps of the computation. One of the TM’s internal states *q*_{halt} is designated as the *halting state*, and the computation is assumed to stop in the event that this state is reached. If this happens, the binary string written on the output tape is taken as the TM’s output. A function is computed by the TM if, for every input string *x*∈*Σ**, the TM eventually halts and produces the output *g*(*x*). The function *g* is said to be computable in space bounded by *f*(*n*) if, for all inputs *x*=*x*_{1}…*x*_{n}, the work tape head remains within the first *f*(*n*) cells of the work tape throughout the computation. For decision problems, where the answer for each *x*_{1}…*x*_{n} is 0 or 1, one often disregards the output tape entirely and takes the first cell of the work tape, say, to hold the answer whenever the computation halts.

Of particular interest to this paper are functions computable within space bounds of the form , which is significantly smaller than the space required to hold the entire input. Functions that are computable within such a bound are called *log-space computable* functions. Note that a function *g* computable in log-space need not have correspondingly short outputs *y*_{1}…*y*_{m}=*g*(*x*_{1}…*x*_{n}), because a log-space bounded machine may still run for *O*(*poly*(*n*)) steps (Papadimitriou 1994; Arora & Barak 2009) (albeit in cramped space conditions) before halting, and so we can potentially have *m*=*O*(*poly*(*n*)) as well.

A general notion and study of space-bounded *quantum* computation was given by Watrous (1999, 2003). Here we will adopt a simplified version of the model along the lines presented by Watrous (2009). Although one may seek to directly generalize the classical definition above, using a fully quantum notion of a quantum TM of the kind described by Bernstein & Vazirani (1997), it appears to be much easier to work instead with a classical-quantum hybrid TM model in which some aspects of the machine are required to always remain classical.

We start with a *classical* TM as above, and add an additional tape (called the *quantum work tape*) with the following features:

the cells of the quantum work tape are qubits, each of which is initialized to |0〉 at the start of the computation, and

there are

*two*heads, with classical positions, scanning the quantum work tape.

We will also eliminate the output tape as our focus will be on decision problems, although one could make further modifications to the model to allow for a classical output tape as well.

The operation of the machine is defined by a finite set of instructions similar to equation (A1), but suitably modified so that quantum gates may be applied to the qubits on the quantum tape during the course of the computation. In particular, we may assume that each internal state *q* has associated to it a two-qubit quantum gate *U*_{q}, chosen from a universal set (which should include the identity operation for the programmer’s convenience). Then a basic transition rule for the machine has the form
A2
The meanings of such a transition is similar to the ones described previously, except that *d*_{q1} and *d*_{q2} denote movement instructions for the two quantum work tape heads. The computation proceeds in a similar way as before—but with the addition that if the two quantum work tape heads are scanning different squares at the start of a given step, then the two-qubit operation *U*_{q} is applied to the two scanned qubits before the tape heads move. In the event that the machine enters the state *q*_{halt}, the leftmost quantum work tape qubit is measured in the computational basis to determine the output of the computation.

The quantum computation is said to occur within space bound *f*(*n*) if, for every input *x*_{1}…*x*_{n} given on the input tape, the work tape head and qubit tape heads remain within the first *f*(*n*) cells of their respective tapes throughout the computation. Because our output is a single bit, this provides a notion of a decision problem being computed by an *f*(*n*)-space-bounded quantum computation.

It is important to point out that a space *f*(*n*) bounded quantum computation may be alternatively thought of as just a circuit of quantum gates applied to *f*(*n*) qubit lines, all initialized to |0〉, where the circuit is determined by a classical space *f*(*n*) bounded computation on the input *x*_{1}…*x*_{n}, i.e. a ‘space-*f*(*n*) generated’ family of quantum circuits. Indeed, in our hybrid classical–quantum TM, the quantum work tape may be replaced by a classical output tape just as in the fully classical model, and instead of applying quantum operations, the corresponding gate names and line numbers are sequentially written on the output tape.

Note that apart from the final measurement, all our quantum operations are required to be *unitary* gates. One may entertain a more general scenario in which general non-unitary quantum operations (completely positive trace preserving maps) on two qubits are allowed, as well as a mechanism for measurements of qubits to occur during the computation that can influence the classical parts of the machine. In the ubiquitous scenario of polynomial *time* and polynomial width quantum computations, say in terms of polynomial-sized quantum circuits, this provides no further generality because arbitrary quantum operations may always be represented via unitary operations with the inclusion of extra ancillary qubit lines. However, for space-bounded computation this generalization can be non-trivial. For example, a log-space computation with general non-unitary gates could involve polynomially many steps, and to simulate such a computation by a unitary process in the most straightforward way would hence require a polynomial number of ancillary qubit lines, which are not available in log space. The general notion of space-bounded quantum computation with general non-unitary gates has been considered by Watrous (1999, 2003), but for the purpose of the present paper we restrict ourselves to the model with unitary gates, which we accordingly call space-bounded *unitary* quantum computation.

## Footnotes

- © 2009 The Royal Society