## Abstract

The theory of matchgates is of interest in various areas in physics and computer science. Matchgates occur, for example, in the study of fermions and spin chains, in the theory of holographic algorithms and in several recent works in quantum computation. In this paper, we completely characterize the class of Boolean functions computable by unitary two-qubit matchgate circuits with some probability of success. We show that this class precisely coincides with that of the *linear threshold gates*. The latter is a fundamental family that appears in several fields, such as the study of neural networks. Using the above characterization, we further show that the power of matchgate circuits is surprisingly trivial in those cases where the computation is to succeed with high probability. In particular, the only functions that are matchgate-computable with success probability greater than 3/4 are functions depending on only a *single* bit of the input.

## 1. Introduction

One of the great virtues of the field of quantum computation is that it interconnects fundamental questions in physics and computer science. The concept of the quantum computer (Deutsch 1989) precisely captures the intrinsic computational power locked within quantum mechanics (Bernstein & Vazirani 1997), and makes it possible to address deep problems, such as the relationship between quantum and classical computational capabilities (Gottesman 1998; Valiant 2002; Jozsa & Linden 2003). At the same time, within the theory of quantum computation it is possible to characterize, in a precise sense, how ‘hard’ it is to simulate physical systems of interest, such as certain ground state problems (Kitaev *et al.* 2002) and time evolutions (Lloyd 1996).

Of particular interest, also in recent work, is the class of quantum processes generated by *matchgates* (Kasteleyn 1961; Temperley & Fisher 1961; DiVincenzo & Terhal 2002; Valiant 2002; Jerrum 2003; Cai & Choudhary 2006*a*,*b*; Jozsa & Miyake 2008; Bravyi 2009; Jozsa *et al.* 2010). The latter is a class of unitary two-qubit operations that are defined by certain algebraic constraints. The theory of matchgates is an instance of a research area that displays strong connections to both physics and computer science (Kasteleyn 1961; Temperley & Fisher 1961; DiVincenzo & Terhal 2002; Valiant 2002; Jerrum 2003; Cai & Choudhary 2006*a*,*b*; Jozsa & Miyake 2008; Bravyi 2009; Jozsa *et al.* 2010). In the study of strongly correlated systems, for example, the dynamics of an important class of one-dimensional quantum systems such as the XY model are modelled by matchgate circuits, i.e. for such Hamiltonians *H* one can construct a poly-size matchgate circuit , such that , for any time *t* (e.g. Jozsa & Miyake 2008). Employing mappings between spin-1/2 systems and fermions, matchgate circuits further describe the dynamics of all non-interacting fermionic systems (DiVincenzo & Terhal 2002). In the theory of quantum computation, matchgates are of particular interest as they provide a key example of the class of non-trivial quantum circuits that *cannot* offer any speed-up over classical computers (for example, in spite of the complex entangled states such circuits may generate; Valiant 2002; Jozsa & Miyake 2008). In addition, matchgate computations were recently found to be equivalent to space-bounded universal quantum computation (Jozsa *et al.* 2010). In classical computer science, finally, matchgates occur in various studies related to, for example the theory of holographic algorithms (Valiant 2002; Cai & Choudhary 2006*a*,*b*).

The aim of the present paper is to characterize the computational power of matchgate circuits. We will in particular study which Boolean functions^{1} can be computed with such circuits. Given an arbitrary matchgate circuit *U*, the question is asked which Boolean function *f*(*x*) can be computed (probabilistically) by initializing the system in the computational basis state |*x*,0〉 (where *x* represents an input string and 0 is a string of ancillary zeros), by subsequently running the circuit *U* and finally measuring, say, the first qubit. This setting captures in perhaps the most elementary way the computational power of matchgate circuits, associating with each circuit a yes/no question as commonly done.

We remark that, beyond its natural computer scientific interest, such an investigation is relevant from an intrinsic physical perspective as well. In particular, given the aforementioned equivalences between matchgate circuits, fermionic systems and one-dimensional spin systems, the present work aims at gaining insight into the link between the physics of these systems and their computational capabilities. In this context, one may pose a variety of interesting questions such as: ‘Does the presence of a quantum phase transition in the XY model leave any signature in the associated class of functions, which can be computed by time-evolving such systems’? The present work is also situated within such a programme.

In the following, we will characterize the family of matchgate-computable functions in full generality. We will find that this class precisely coincides with the class of *linear threshold gates* (LTGs; Dertouzos 1965; Muroga 1971; Siu *et al.* 1995). The latter is a fundamental family of functions that has been a topic of study since the 1960s and that plays an important role in numerous areas. LTGs occur in the study of neural networks where these functions serve as elementary models of neurons (Rosenblatt 1958; Block 1962; Minsky & Papert 1988) and in circuit complexity theory (Goldmann *et al.* 1992; Hajnal *et al.* 1993; Goldmann & Karpinski 1998); cf. Feldman *et al.* (2006), Sherstov (2008), Kalai *et al.* (2008), Khot & Saket (2008), O’Donnell & Servedio (2008), and references within for a number of recent investigations on LTGs. The existence of a connection between matchgates and LTGs may be considered surprising, since *a priori* there is no obvious relation between these two theories.

Below we state the contributions of this work in more precise terms. Here, we highlight some particularly noteworthy aspects of our results.

An interesting phenomenon occurs when considering those functions that are matchgate-computable with *high* success probability. Since a generic matchgate circuit may be a rather complex object, one would expect that this class of functions has some non-trivial character as well. We will show that this intuition is incorrect: any function that is matchgate-computable with success probability greater than 3/4 is proved to be *trivial* in that any such function can only depend on a *single* bit of the input. The origin of this apparent paradox is the strong set of constraints that are placed on any circuit (matchgate or conventional) that is to compute the correct function value with high probability on *all* inputs. Indeed, a generic circuit does typically *not* fulfil these requirements, and hence does not meaningfully compute any function. The present example thus highlights the significance of bounded-error constraints in a rather striking way: in spite of the potentially complex structure of general matchgate circuits, the only instances which turn out to satisfy the bounded-error constraints are circuits computing mere single-bit—i.e. utterly trivial—functions!

Note that the above feature is of interest from a physics perspective as well: it shows that the non-trivial *physical* properties (such as e.g. the presence of a quantum phase transition) of a family of quantum systems are *not* guaranteed to translate into any non-trivial-associated *computational* model. Indeed, in spite of the interesting physical processes modelled by matchgates, these processes turn out to have trivial power when used as a computer, which is to solve problems with high success probability.

Overall, the results in this paper indicate that matchgate circuits have a rather weak computational power. This is in part reflected in the above phenomenon, but also in an additional result obtained in this work. We will characterize the power of matchgate circuits in terms of a strikingly elementary *classical* computer, which is capable of computing every matchgate-computable function with the same success probability as the optimal matchgate circuit.

### (a) Related work

We mention two related investigations. First, in Jozsa *et al.* (2010), the power of matchgate circuits was characterized from a different perspective. It was shown that every *n*-qubit nearest-neighbour matchgate circuit *U* can be mapped to an equivalent circuit *U′* of roughly the same size, where *U′* is composed of *general* unitary gates but acts on a logarithmic number of qubits . The reduction from *U* to *U′* requires a logarithmic space classical computation. A converse statement, relating arbitrary quantum circuits acting on *m* qubit lines to matchgate circuits acting on *O*(2^{m}) qubits, was also proved. Thus Jozsa *et al.* (2010) characterize the power of matchgate circuits, under log-space classical reductions, as equivalent to space-bounded universal quantum computation. It will be interesting to contrast the study of Jozsa *et al.* (2010) with the present paper in the context of bounded-error matchgate computations; we refer to §6*a*.

Second, an investigation (Buhrman *et al.* 2009) similar to the present one was carried out for another important class of classically simulatable quantum circuits *viz.* the Clifford circuits. It was shown that an *n*-bit Boolean function *f* is Clifford-computable, if and only if it is an affine function, i.e. *f*(*x*) = *a*^{T}*x* + *b* for some *n*-bit string *a* and some bit *b*. Moreover, all affine functions are proved to be Clifford-computable with unit success probability.

### (b) Notation

In the following, [*n*] denotes the set of positive integers from 1 to *n*, for any *n*. If *x* = (*x*_{1},…,*x*_{n}) is a string of bits *x*_{k}∈{0,1}, then denotes the ±1 vector that is obtained by replacing all 0-components of the *n*-bit string *x* by 1 and all 1-components by −1. The symbol ⊕ denotes addition modulo 2. The 1-norm of a complex vector *w* = (*w*_{1},…,*w*_{n}) is denoted by .

## 2. Main results

Here, we summarize the contributions of this paper. To do so, we state some preliminary definitions.

A matchgate^{2} *G* is any two-qubit operation with matrix representation2.1in the standard basis, where *A* and *B* are in *U*(2) and must have the *same* determinant. Note that the equal determinant requirement, while seemingly innocent, is an important feature of matchgates. In particular, the theory of classical simulations of matchgate circuits crucially depends on this property; see Jozsa & Miyake (2008) for a discussion. We will consider circuits composed of matchgates acting on nearest-neighbour qubits (assuming a one-dimensional ordering of the qubits), i.e. the standard scenario in which matchgates are considered.

Let *f*: {0,1}^{n} → {0,1} be a Boolean function on *n* bits and let *U* be an *m*-qubit unitary operation with *m* ≥ *n*. We say that *U* computes *f* with probability at least *p* if for every *n*-bit string *x*, the preparation of the *m*-qubit state *U*|*x*,0〉 (where 0 denotes a string of *m*−*n* zeroes) followed by a computational basis measurement of the first qubit^{3} yields the outcome *f*(*x*) with a probability of at least *p*. An *n*-bit Boolean function *f* is said to be matchgate-computable with probability at least *p*, if there exists a matchgate circuit on *m* qubits, for some *m* ≥ *n*, which computes *f* with a probability of at least *p*. Note that in the latter definition neither any restriction is placed on the size of *m* when compared with *n*, nor on the number of gates in the matchgate circuit compared with *n*. However, below we will find that every matchgate-computable function can be computed by a matchgate circuit acting on at most *n* + 1 qubits (without decreasing the success probability). Moreover, it is known that any matchgate circuit acting on *m* qubits can be re-expressed as a matchgate circuit of size *O*(*m*^{3}) (see Jozsa & Miyake 2008).

### (a) Main theorem

We will show that the class of matchgate-computable functions coincides with the family of LTGs. A Boolean function *f* on *n* bits is called an LTG if there exists an *n*-dimensional real vector *w* and a real constant *θ*, such that *f*(*x*) equals 0 if and only if is strictly positive. The vector (*w*,*θ*) is called a representation of *f*. Examples of LTGs are the NOT gate, the *n*-bit AND and OR, and the majority gate. We will consider LTGs that are supplemented with a parameter which is called the margin of the LTG. Given an LTG *f* on *n* bits with representation (*w*,*θ*), the margin of this representation is defined to be the minimal value of over all *n*-bit strings *x*. The margin *ϵ* of *f* itself is the maximal achievable margin of any representation (*w*,*θ*) of *f*, which is normalized in the sense that ∥*w*∥_{1} + |*θ*| = 1.

The main result of this paper achieves a complete characterization of all matchgate-computable functions:

### Theorem 2.1

*Let f be a Boolean function on n bits and let p* ∈ (0.5,1]. *Then the following statements are equivalent:*

(a)

*f is matchgate-computable with probability at least p.*(b)

*f is an LTG with margin ϵ*≥ 2*p*−1.

*Moreover, (a) holds if and only if there exists a matchgate circuit acting on at most n* + 1 *qubits, which computes f with probability at least p.*

Note that theorem 2.1 connects the margin *ϵ* of an LTG with an optimal success probability *p* of computing this function using matchgate circuits. In particular, *ϵ* is small iff *p* is small. This implies that the class of LTGs computable with matchgate circuits grows larger as the required probability of success is decreased. When *p* is allowed to be arbitrarily close to 0.5, the full class of LTGs is matchgate-computable owing to theorem 2.1.

As an immediate corollary of the above result, it follows that matchgate circuits do not have universal classical computational power, even when an unbounded error is allowed, i.e. a success probability strictly greater than 0.5 but (with increasing *n*) potentially exponentially close to 0.5. This property follows immediately from the elementary fact that there exist functions that are not LTGs, such as the two-bit parity gate.

### (b) Bounded-error computations

Surprisingly, it follows from theorem 2.1 that matchgate circuits can only compute trivial functions if the computation is to succeed with high probability:

### Theorem 2.2

*A Boolean function f is matchgate-computable with probability p* > 3/4 *if and only if this function is either constant or depends on a single bit of its input.*

Owing to theorem 2.1, any function that is matchgate-computable with probability *p* > 3/4 is an LTG with margin *ϵ* > 1/2. We will show that the only LTGs having such large margin are constant or depend on one input bit, leading to the proof of theorem 2.2. Note that functions which depend on a single input bit have the very simple form *f*(*x*) = *x*_{k} or *f*(*x*) = 1−*x*_{k} for some *k*, i.e. *f* returns the *k*th bit of its input or its negation. As discussed in §1, theorem 2.2 is a somewhat unexpected result, given that generic matchgate circuits are rather non-trivial objects, which e.g. describe physical systems that may exhibit an interesting behaviour, such as e.g. quantum phase transitions. In spite of this rich structure, theorem 2.2 shows that the computational power of matchgate circuits is near-vanishing in those cases where the correct answer is to be produced with high probability.

Of particular interest are computations that yield the correct output with a probability that is bounded away from 0.5 by an inverse polynomial in the input size. Let be a family of Boolean functions, where *f*_{n} acts on *n* bits and let {*p*_{n}} be a family of probabilities, where *p*_{n} > 0.5 and, for *n* large, *p*_{n} is bounded away from 0.5 by an inverse polynomial in *n*. We say that is matchgate-computable with poly-bounded error if there exists such a poly-bounded family of probabilities as well as a family of matchgate circuits {*U*_{n}}, such that *U*_{n} computes *f*_{n} with probability at least *p*_{n}. It is standard that any computation with poly-bounded error can be promoted to an almost deterministic computation^{4} by repeating the computation poly(*n*) times and taking the majority vote of all the obtained results. Owing to theorem 2.1, the families of Boolean functions that are matchgate-computable with poly-bounded error precisely coincides with those LTGs having poly-bounded margin, i.e. the margin *ϵ*_{n} of *f*_{n} scales as an inverse polynomial in *n*. Furthermore, we will show that a family of LTGs has poly-bounded margin if and only if *f*_{n} has a representation (*w*_{n},*θ*_{n}), where the coefficients of *w*_{n} and *θ*_{n} are *integers* that are at most polynomially large; such families of threshold gates are said to have polynomial integer weight. This leads to the following concise characterization.

### Theorem 2.3

*A family of Boolean functions is matchgate-computable with poly-bounded error if and only if it is a family of LTGs with polynomial integer weight.*

### Remark 2.4

The near-deterministic computation of *n*-bit LTGs with polynomial integer weight is obtained by running the computation poly(*n*) times and computing the majority vote of all measurement outcomes. It is intriguing that the majority function is indeed an LTG—and hence matchgate-computable—however, in order to properly amplify the success probability, the majority gate itself needs to be computed with suitably high success probability (the latter e.g. being exponentially close to 1). However, owing to theorem 2.2, the majority function *cannot* be computed with good success probability by any matchgate circuit. Therefore, to obtain the proper amplification, a final *non*-matchgate computation is needed to compute the majority vote—even though the latter comes intriguingly close to being suitably matchgate-computable!

### (c) An equivalent classical computer

As a final result, we will construct a *classical* computational scheme that is equivalent to the matchgate circuit model in the following sense: any function which is matchgate-computable with probability at least *p* can be computed with probability at least *p* with our classical scheme, and vice versa. As we will show, the required classical computer is very simple, as it essentially requires a single sample of a fixed (i.e. independent of the input) probability distribution on the set of integers from 1 to *n* + 1, together with the possibility of performing a single bit flip of one of the input bits, depending on the outcome of the sampling. This characterization is a further illustration (in addition to, e.g. theorem 2.2) of the weak computational capabilities of matchgate circuits.

Whereas the general result will be stated below, here we illustrate the scheme with an example. Let *n* be odd and consider the majority function *f*_{maj} on *n*-bits, which is an LTG. It can be shown that the margin of *f*_{maj} is *ϵ*_{maj} = *n*^{−1}. Owing to theorem 2.1, the optimal success probability of computing *f*_{maj} with a matchgate circuit is2.2Now consider the following elementary classical computation:

— Choose an

*n*-bit input string*x*.— Generate a random integer

*k*between 1 and*n*.— Output the bit value

*x*_{k}.

It can easily be shown that, for every *x*, the output of this computation is *f*_{maj}(*x*) with probability at least *p*_{maj}. In other words, the above elementary classical computation is capable of computing the majority function with the same probability of success as the optimal matchgate circuit can!

The above example is not coincidental, as we will show that *every* LTG *f* can similarly be associated with a simple classical computation of the above nature.

## 3. Matchgates

In this section, we recall some basic properties of matchgates, which were defined in equation (2.1). We emphasize that, henceforth, the term ‘matchgate circuit’ will always refer to a circuit composed of matchgates acting on nearest-neighbour qubit lines, as commonly done.

We first recall a celebrated result about the classical simulation of matchgate circuits, first proved in Valiant (2002) and subsequently investigated by a series of other authors (DiVincenzo & Terhal 2002; Cai & Choudhary 2006*a*,*b*; Jozsa & Miyake 2008; Bravyi 2009).

### Theorem 3.1

*Consider a poly-size n-qubit circuit composed of matchgates acting on nearest-neighbour qubits. The circuit acts on an arbitrary standard basis input and is followed by a standard basis measurement of the first qubit. Let p*_{0} *denote the probability of obtaining the bit 0 as an outcome. Then there exists a classical algorithm that computes p*_{0} *up to m bits in poly(n,m) time.*

As a consequence of this result, there exists a poly-time classical algorithm to sample from (a distribution that is exponentially close to) the distribution {*p*_{0},1−*p*_{0}}, i.e. any matchgate computation of the above type can be simulated classically in poly-time.

We discuss some further well-established properties of matchgates, which will be used in the proof of theorem 2.1. We refer to e.g. Jozsa & Miyake (2008) for elementary proofs of these properties.

First, without loss of generality, in the following we will always consider poly-size families of matchgate circuits, as it is known that any, possibly exponential size, *n*-qubit matchgate circuit family can be re-expressed as a matchgate circuit family of size *O*(*n*^{3}). Second, consider the *n*-qubit Jordan–Wigner operators:3.1where *X*_{k}, *Y*_{k} and *Z*_{k} denote the Pauli *X*, *Y* and *Z* operators acting on qubit *k*, respectively. Then an *n*-qubit unitary operation *U* is a matchgate circuit (up to a global phase) if and only if there exists an operator *R*∈*SO*(2*n*) such that, for every *μ*∈[2*n*], it is the case that3.2It further holds that *U* is a matchgate circuit if and only if there exists a Hermitian operator *H* lying in the linear span of the products *c*_{μ}*c*_{ν} (where *μ*≠*ν*), such that . Such an operator *H* is sometimes called a quadratic Hamiltonian. Quadratic Hamiltonians describe the physics of systems of non-interacting fermions. We will not discuss this connection to fermionic physics here as it would lead us too far outside of the scope of this work, and we refer to e.g. DiVincenzo & Terhal (2002).

The following are some examples of matchgates and matchgate circuits. The fermionic SWAP (fSWAP) operation is easily seen to be a matchgate. This operation sends the basis state |*ab*〉 to (−1)^{ab}|*ba*〉, for every *a*,*b* = 0,1, i.e. it swaps the qubits and adds an overall minus sign if both qubits are in the state |1〉. Other elementary examples of matchgate circuits are the products *c*_{μ}*c*_{ν} for any *μ*≠*ν*. Indeed, any such product can be written as an exponential of a quadratic Hamiltonian. Denoting *H*: = i*c*_{μ}*c*_{ν} it is easily verified that *H* = *H*^{†} = *H*^{2}. Hence3.3where in the first identity we have used that , since *H* = *H*^{2}. To obtain a more non-trivial example of a matchgate circuit, consider the Hamiltonian of the one-dimensional transverse Ising model:3.4for some real constants *J*_{k} and *h*_{k}. It can readily be verified that3.5showing that *H*_{I} is a quadratic Hamiltonian. Therefore, for every real *t*, the time-evolution operator *e*^{itHI} can be written as a (poly-size) matchgate circuit.

The notion of a matchgate-computable Boolean function was introduced in §2. Here, we discuss some simple examples. It can easily be seen that every Boolean function which is either constant or which depends on a single input bit can be computed with unit probability by an elementary matchgate circuit composed of operators *c*_{μ}*c*_{ν} and fSWAP gates acting on *n* + 1 qubits. Note that the only possible functions of this type are the functions *x* → 0, *x* → 1, *x* → *x*_{k} and *x* → 1−*x*_{k}, for some *k*. We show that *x* → 1−*x*_{k} is matchgate-computable with unit probability; the other three cases are treated similarly. For each *k*∈[*n*], denote the operator *U*_{k} acting on *n* + 1 qubits by3.6Note that where *x*_{¬k} denotes the bit string obtained by flipping the *k*th bit of *x*. Now consider an elementary matchgate computation, where first the state *U*_{k}|*x*,0〉 is prepared, followed by measurement of qubit *k*. This computation yields the bit 1−*x*_{k} with unit probability. This shows that the desired function can be computed with unit probability by applying a suitable matchgate circuit and measuring *some* qubit in the computational basis. By applying a suitable sequence of fSWAP gates immediately before the measurement, we may assume w.l.o.g. that the first qubit is measured. Indeed, as the measurement is in the computational basis, the minus sign of the fSWAP gate has no relevance, and this gate acts as a simple SWAP.

Remarkably, as we will prove in theorem 2.2, constant and single-bit functions are the *only* functions that are matchgate-computable with high success probability.

## 4. Linear threshold gates

In this section, we discuss some elementary features of LTGs. For convenience we recall here their definition. An *n*-bit Boolean function *f* is an LTG if there exists an *n*-dimensional real vector *w* and a real number *θ*, such that4.1for every *n*-bit string *x*. The pair (*w*,*θ*) is called a representation of *f*. Definition (4.1) has an elementary geometrical interpretation. Taking an arbitrary *w* and *θ*, the linear equation *w*^{T}*z* + *θ* = 0 defines a hyperplane that divides the *n*-dimensional real space into two parts, say *H* _{+} and *H*_{−}, where *H* _{+} consists of all , such that *w*^{T}*z* + *θ* ≥ 0 and *H*_{−} is defined as the complement of *H* _{+} . The LTG *f* associated with (*w*,*θ*) then simply evaluates whether a given {±1}-vector lies in *H* _{+} or *H*_{−}. Stated differently, a Boolean function *f* is an LTG iff there exists a hyperplane in *n*-dimensional real space that separates the sets of inputs *x* that are mapped to 0 and 1, respectively.

It can be easily verified that the constant and single-bit functions are LTGs. Other examples are the the *n*-bit AND, OR and majority function. The AND gate, for example, has a representation (*w*,*θ*) given by *w* = (1,…,1) and *θ* = −*n* + 1/2. It is also known that not all functions are LTGs. For example, the two-bit parity gate4.2is not an LTG, as can be easily verified.

Every LTG has infinitely many representations. For example, rescaling the vector (*w*,*θ*) with a positive multiplicative constant trivially leads to the same associated function. We will say that the representation (*w*,*θ*) is normalized if the 1-norm of this vector is equal to 1, i.e. ∥*w*∥_{1} + |*θ*| = 1. Interestingly, every LTG has a representation (*w*,*θ*), where each *w*_{k} and *θ* are *integers*. The intuition behind this result is the following. It is easy to show that every LTG has a representation (*w*,*θ*), where each *w*_{k} and *θ* are rational numbers, say *w*_{k} = *a*_{k}/*b*_{k} and *θ* = *c*/*d* for suitable integers *a*_{k},*b*_{k},*c* and *d*; this essentially follows from the fact that the rationals are dense in the reals and the property that small perturbations of a representation do not change the associated LTG. Multiplying the rational representation (*w*,*θ*) with the product then yields an integer representation.

Further, it is known that every LTG on *n* bits has a representation (*w*,*θ*) where each of the components of *w*, as well as the number *θ*, are integers not greater than 2^{N} in absolute value, with (Muroga *et al.* 1961); moreover, there exist LTGs where such large numbers are required (Hastad 1994). This shows that every LTG *f* admits a representation that can be fully described in terms of bits, and that *f*(*x*) can be evaluated in poly-time when this particular representation is provided.

Finally, we recall that that, given a representation (*w*,*θ*) of an LTG *f*, the margin of this representation is defined to be the minimal value of over all *n*-bit strings *x*. The margin *ϵ*(*f*) ≡ *ϵ* of *f* is then the maximal margin over all *normalized* representations. Note that *ϵ*(*f*), which should in principle be defined as a supremum, is indeed a maximum. This can be argued with standard methods.^{5} In §6, we will focus in more detail on the properties of margins of LTGs, which will lead to the proofs of theorems 2.2 and 2.3. Before doing so, we provide the proof of theorem 2.1 in the next section.

## 5. Proof of theorem 2.1

In this section, we prove theorem 2.1. The proof will proceed in three steps. In step 1, we reduce the study of matchgate-computable functions to the investigation of matrix elements of the form 〈*x*|*U*^{†}*Z*_{1}*U*|*x*〉, where |*x*〉 denotes a computational basis state, *U* is a matchgate circuit and *Z*_{1} is the Pauli *Z* operator acting on the first qubit. In step 2, which represents the main ingredient of the proof of theorem 2.1, the most general form of such matrix elements is characterized. Finally, in step 3 the proof is completed by combining steps 1 and 2.

### (a) Step 1

Let *f* be an *n*-bit Boolean function, let *U* be an arbitrary *m*-qubit unitary operation for some *m* ≥ *n* and fix *p*∈(0.5,1]. Furthermore, we denote 〈*Z*〉_{x}: = 〈*x*,0|*U*^{†}*Z*_{1}*U*|*x*,0〉. We now state the following claim.

### Claim

*U* computes *f* with probability at least *p* if and only if, for every *x*, one has

|〈

*Z*〉_{x}| ≥ 2*p*−1 andsign〈

*Z*〉_{x}= (−1)^{f(x)}.

To prove this claim, consider the preparation of *U*|*x*,0〉 followed by a computational basis measurement of the first qubit and let *p*_{x} denote the probability that the measurement outcome is *f*(*x*), for every *x*. Then *U* computes *f* with probability at least *p* if and only if *p*_{x} ≥ *p* for every *x*. We thus have to show that (i) and (ii) are equivalent to the condition *p*_{x} ≥ *p* for all *x*.

We will distinguish between the cases *f*(*x*) = 0 and *f*(*x*) = 1. We start with the former case. As *p*_{x} and 1−*p*_{x} are the probabilities of obtaining the measurement outcomes 0 and 1, respectively, one has5.1Now suppose first that *p*_{x} ≥ *p* for every *x* (with *p*∈(0.5,1] as stated above). Conditions (i) and (ii) then follow immediately. Conversely, assume that (i) and (ii) are true. As (ii) is satisfied, we have 〈*Z*_{1}〉_{x} ≥ 0 and using (i) it thus follows that 〈*Z*_{1}〉_{x} ≥ 2*p*−1. Invoking equation (5.1) then implies that *p*_{x} ≥ *p* for every *x*, as desired. This completes the proof for the case *f*(*x*) = 0.

The case *f*(*x*) = 1 is treated analogously; the main distinction is that now *p*_{x} represents the probability of measuring 1. Consequently, equation (5.1) is replaced by5.2The remainder of the argument is completely analogous.

### (b) Step 2

Conditions (i) and (ii) imply that the study of matchgate-computable functions reduces to the investigation of matrix elements of the form 〈*x*,0|*U*^{†}*Z*_{1}*U*|*x*,0〉, where *U* is an arbitrary matchgate circuit. Next, we investigate the most general form which such matrix elements may take. A complete characterization of this problem is obtained in the following theorem.

### Theorem 5.1

*Let U be an n-qubit unitary operator. If U is a matchgate circuit then there exists an* *with* ∥*a*∥_{1} ≤ 1, *such that*5.3*for every n-bit string x. Conversely, for every* *with* ∥*a*∥_{1} ≤ 1, *there exists an n-qubit matchgate circuit U, such that equation (5.3) holds.*

In the proof of this theorem we will need the following elementary fact.

### Lemma 5.2

*Consider a vector* *with* ∥*a*∥_{1} ≤ 1. *Then there exist* *with* ∥*u*∥_{2} = 1 *and* ∥*v*∥_{2} ≤ 1, *such that* *a*_{k} = *u*_{k}*v*_{k} *for every* *k* ∈ [*n*].

### Proof.

Define *u* and *v* by5.4for every *k*∈[*n*], respectively. Obviously, *a*_{k} = *u*_{k}*v*_{k}. Moreover, ∥*u*∥_{2} = 1 and ∥*v*∥_{2} = ∥*a*∥_{1} ≤ 1, as can be easily verified. This proves the lemma. ■

### Proof of theorem 5.1.

We first prove the forward direction. Denote *O*: = *U*^{†}*Z*_{1}*U* and let *R* be the *SO*(2*n*) rotation associated to *U* via equation (3.2). Letting *ρ* and *ρ*′ denote the first, respectively, second, row of *R* and using that *Z*_{1} = −i*c*_{1}*c*_{2}, it follows that5.5where the sum is over all *μ*,*ν*∈[2*n*]. As 〈*x*|*O*|*x*〉 is a diagonal entry of *O* for every *x*, we only need to focus on the diagonal part of this operator, i.e. . Using the explicit representation (3.1) of the *c*_{μ}, it is easily verified that5.6Setting *a*_{k}: = *ρ*_{2k−1}*ρ*′_{2k}−*ρ*_{2k}*ρ*′_{2k−1} for every *k*∈[*n*] and using that is zero since *ρ* and *ρ*′ are two distinct rows of an orthogonal matrix, it follows that5.7The (*x*,*x*) diagonal entry of *O* thus reads:5.8This shows that equation (5.3) is satisfied. Note also that |〈*x*|*O*|*x*〉| ≤ 1 for every *x* since *O* is unitary. Moreover, it is easily verified that there exists an *x* such that . This shows that ∥*a*∥_{1} ≤ 1.

To prove the reverse direction, consider an arbitrary with ∥*a*∥_{1} ≤ 1. Owing to lemma 5.2, there exist *n*-dimensional real vectors *u* and *v* with ∥*u*∥_{2} = 1 and ∥*v*∥_{2} ≤ 1, such that *a*_{k} = *u*_{k}*v*_{k} for every *k*∈[*n*]. Furthermore, it is elementary that for every such *u* and *v* there exists a vector that is orthogonal to *u* and that satisfies . Consequently, the 2*n*-dimensional vectors5.9are unit vectors (w.r.t. the 2-norm) that are orthogonal. Let *R* be any *SO*(2*n*) rotation having *ρ* and *ρ*′ as first, respectively, second row. Let *U* be the *n*-qubit matchgate circuit associated to *R*. Analogous to the proof of the forward direction of the theorem, a direct calculation shows that the diagonal part of *U*^{†}*Z*_{1}*U* equals5.10It immediately follows that equation (5.3) is satisfied. This completes the proof. ■

### (c) Step 3

We now show how the above result leads to the proof of theorem 2.1. Invoking step 1, it suffices to show that, for every *n*-bit Boolean function *f* and *p*∈(0.5,1], the following are equivalent:

— There exists an

*m*-qubit matchgate circuit*U*, for some*m*≥*n*, such that conditions (i) and (ii) in step 1 hold;—

*f*is an LTG with margin*ϵ*≥ 2*p*−1.

We first prove the forward direction of the claim. Let *U* be a matchgate circuit on *m* qubits, such that (i) and (ii) hold. We first invoke theorem 5.1. This yields a vector with 1-norm at most 1, such that equation (5.3) holds. With the notations and , it then immediately follows that5.11for every *n*-bit string *x*. Together with condition (ii) in step 1, this shows that *f* is an LTG with representation . Normalizing the vector w.r.t. the 1-norm yields a normalized representation and *θ*: = *γb*, where Note that *γ*^{−1} ≤ ∥*a*∥_{1} ≤ 1. Using equation (5.11) and condition (i) of step 1 it follows that5.12Moreover, using the definitions of *w* and *θ* and the fact that *γ* ≥ 1, it finally follows that5.13for every *x*. This shows that the margin of *f* is at least 2*p*−1.

We now show the converse. Consider an *n*-bit LTG *f*. Let *ϵ*∈(0,1] be its margin with associated (normalized) representation (*w*,*θ*) and denote *p*: = (*ϵ* + 1)/2. Owing to theorem 5.1, there exists an (*n* + 1)-qubit matchgate circuit *U*, such that5.14for every *n*-bit string *x* and for every *y* = 0,1. This readily implies that5.15for every *x*. Moreover, as *ϵ* is the margin of *f*, it follows that5.16for every *x*. This shows that conditions (i) and (ii) in step 1 are fulfilled. This completes the proof of theorem 2.1.

### Remark 5.3

It follows from the above argument that an *n*-bit Boolean function *f* is computable by an *m*-qubit matchgate circuit with probability at least *p*, for *some* *m* ≥ *n*, if and only if *f* is computable with probability at least *p* by a matchgate circuit acting on at most *n* + 1 qubits.

## 6. Margins of threshold gates

In this section, we analyse the properties of margins of LTGs in more detail. In particular, the proofs of theorems 2.2 and 2.3 will follow from the considerations in this section.

### (a) Large margins

Next, we investigate the subclass of LTGs with large margin. We will in particular show that any LTG with margin strictly larger than 1/2 is essentially trivial. The proof of theorem 2.2 will follow immediately from this property.

Recall that, formally, a Boolean function *f* on *n* bits is said to depend on its *k*th variable, if there exists an *n*-bit string *x*, such that *f*(*x*)≠*f*(*x*_{¬k}), where *x*_{¬k} is the string obtained by flipping the *k*th bit of *x*. We can now state the following result:

### Lemma 6.1

Any LTG with margin *ϵ* can depend on at most *t* = 1/*ϵ* of its variables.

### Proof.

Let *f* be an *n*-bit LTG and let *ϵ* be the margin of *f* with associated normalized representation (*w*,*θ*). We make the following claim. *Claim:* if *f* depends on its *k*th variable then |*w*_{k}| ≥ *ϵ*. The proof of the lemma immediately follows from correctness of this claim, by using that ∥*w*∥_{1} ≤ 1 as (*w*,*θ*) is a normalized representation. We now prove the claim. For simplicity but w.l.o.g., we set *k*: = 1 and assume that *f* depends on its first variable. We prove that |*w*_{1}| ≥ *ϵ*. Denote . If *f* depends on its first variable, there must exist an , such that have opposite signs. We consider the following two possibilities: (a) or (b) . In case (a), it follows that , and hence we must have . Since *ϵ* is the margin of (*w*,*θ*), it follows that6.1Hence, |*w*_{1}| ≥ *ϵ*. Case (b) is treated analogously. ■

It follows that any LTG that depends on all its *n* variables can admit a margin of size at most 1/*n*, and any LTG with constant margin can depend on at most a constant number of its input bits. What is more, if *ϵ* is sufficiently close to 1 *viz.* *ϵ* > 1/2, then *f* can depend on at most one of its variables. Indeed, it follows from lemma 6.1 that *f* can depend on at most *t* = *ϵ*^{−1} < 2 input bits, i.e. *t* is 0 (corresponding to a constant function) or 1. Combining these considerations with theorem 2.1, the forward direction of theorem 2.2 follows immediately: indeed, owing to theorem 2.1, any Boolean function which is matchgate-computable with probability *p* > 3/4 must be an LTG with margin *ϵ* > 1/2, and hence of the form indicated. The proof of the converse direction of theorem 2.2 is elementary, as discussed in §3.

More general than theorem 2.2, we have actually shown that any function which can be computed by a matchgate circuit with success probability at least *p* is an LTG that depends on at most *O*(*p*^{−1}) of its input bits. As a consequence, whenever a constant success probability is considered (i.e. independent of the input size), only functions can be computed that depend on a constant number of input bits. Conversely, we have proved that any LTG depending on *k* of its input bits can be computed by a matchgate circuit with success probability of at most (1/2) + *O*(*k*^{−1}). Therefore, any LTG that depends on all its *n* input bits can be computed by a matchgate circuit with probability at most (1/2) + *O*(*n*^{−1}), which always lies at least polynomially close to 0.5.

### Remark 6.2 (relation to Jozsa *et al.* (2010))

As shown above, if *p* = *O*(1) then matchgate circuits *U* can merely compute functions *f*(*x*) that depend on *O*(1) input bits, i.e. bounded-error matchgate computations have a rather limited power. It is interesting to compare with the study of Jozsa *et al.* (2010). In order to understand the relation between Jozsa *et al.* (2010) and the present work it is important to remark that in the study of Jozsa *et al.* (2010), one considers matchgate circuits *U* ≡ *U*_{x} which may depend, via an arbitrary log-space classical computation, on the *entire* input *x*. This definition thus effectively supplements matchgate circuits with the power of log-space classical computation. Within this setting, it was shown that the class of problems computable with bounded error by such log-space-generated matchgate circuits *U*_{x} is non-trivial, coinciding with the class of all problems computable with a quantum computer acting on qubits. In contrast, in the present work we always consider matchgate circuits that depend only on the *size* of the input, i.e. one circuit *U* ≡ *U*_{n} takes all inputs *x* of size |*x*| = *n*, as commonly done. The feature that bounded-error matchgate computations have such limited power in our work, whereas in Jozsa *et al.* (2010) they are equivalent to the entire class of quantum log-space computations thus seems to be an intriguing manifestation of the distinction.

We conclude this section with an example. Let *n* be odd and let *f*_{maj} denote the majority function on *n* bits, i.e. *f*_{maj}(*x*) is 0 iff the *n*-bit string *x* contains more zeros than ones. It can easily be verified that *f*_{maj} is an LTG with normalized representation (*w*,*θ*) defined by *w*_{k}: = *n*^{−1} for every *k* and *θ*: = 0. Moreover, the minimal value of over all *x* is easily shown to be *n*^{−1}, showing that *n*^{−1} is a lower bound for the margin of *f*_{maj}. As *f*_{maj} depends on all its *n* variables, its margin is at most *n*^{−1} owing to lemma 6.1. This shows that the margin of the majority function is precisely *n*^{−1} ≡ *ϵ*_{maj}. Owing to theorem 2.1, there hence exists a matchgate circuit that computes this function with probability6.2Moreover, any matchgate circuit computing the majority function can do so with probability at most *p*_{maj}.

### (b) Margins and integer representations

Next, we focus on the possible types of asymptotic behaviour that the margins of a family of LTGs may exhibit. We will in particular be interested in the distinction between margins that are polynomially bounded and margins that are exponentially small in the input size. As discussed in §2, the subclass of (families of) LTGs with polynomially bounded margin coincides with those functions that are matchgate-computable with poly-bounded error. In the following, we will in particular prove a simple characterization of the families of LTGs with poly-bounded margin.

An important parameter of an LTG *f* in the present context will be the integer weight *ω*(*f*) ≡ *ω* of *f*, defined to be the minimal 1-norm ∥*w*∥_{1} + |*θ*| of any possible integer representation of *f*. A family of LTGs {*f*_{n}: *n* = 1,2,…}, where *f*_{n} acts on *n* bits, is said to have polynomial integer weight if the integer weight *ω*_{n} of *f*_{n} scales polynomially with *n*. Interestingly, it turns out that the margin of an LTG and its integer weight are closely related concepts:

### Theorem 6.3

*Consider an n-bit LTG with margin ϵ and integer weight ω. Then*6.3

Note that, in the case of large *n*, the second inequality in equation (6.3) simplifies to *ω* ≤ *O*(*n*/*ϵ*). As an immediate corollary of theorem 6.3, the following property follows:

A family of LTGs has poly-bounded margin if and only if it has polynomial integer weight.

Combining this result with theorem 2.1 then proves theorem 2.3.

### Proof of theorem 6.3.

We first prove the first inequality. Let (*v*,*φ*) be an integer representation with ∥*v*∥_{1} + |*φ*| = *ω*. Normalizing (*v*,*φ*) leads to the representation (*w*,*θ*) defined by *w*: = *ω*^{−1}*v* and *θ* = *ω*^{−1}*φ*. We claim that (*w*,*θ*) has margin at least *ω*^{−1}, implying that *ϵ* ≥ *ω*^{−1} as desired. To prove the claim, note that the sign of equals (−1)^{f(x)} for every *n*-bit string *x*. This implies that for any *x*. As the components of *v* and *φ* are integers, is an integer as well for any *x*. Hence, the property implies that . It follows that , i.e. the margin of (*w*,*θ*) is at least *ω*^{−1}.

Next, we prove the second inequality. Let (*w*,*θ*) be a normalized representation of *f* with margin *ϵ*. Let *d* be a positive integer; for now *d* is arbitrary but we will fix a value later. Let *w*_{kμ} and *θ*_{μ} represent the *μ*th bit in the binary expansion^{6} of *w*_{k} and *θ*, respectively. Now let *v*_{k} and *φ* be the rational numbers obtained by truncating the binary expansion of *w*_{k}, respectively, *θ*, after the *d*th bit (and keeping the same overall signs). That is, we define and for every *k*, where the sums run from 1 to *d*. Note that6.4It further follows from the definitions of *v* and *φ* that |*w*_{k}−*v*_{k}| ≤ 2^{−d} and |*φ*−*θ*| ≤ 2^{−d}. This implies that6.5We now choose *d* to be the smallest positive integer, such that (*n* + 1)2^{−d} is strictly smaller than *ϵ*. Then, as , the quantity6.6must have the same sign as for every *x*. Note that equation (6.6) coincides with for every *x*. This shows that (*v*,*φ*) is also a representation of *f*. But then also multiplying (*v*,*φ*) with 2^{d} leads to a representation of *f*. The latter representation is integer, and moreover has 1-norm at most 2^{d}, since the 1-norm of (*v*,*φ*) is at most 1 owing to equation (6.4). This shows that the integer weight of *f* is at most 2^{d}. Finally, for our choice of *d* one has6.7To see this, remark that *d* is defined to be the smallest integer strictly larger than . But then *d* must satisfy6.8which is equivalent to equation (6.7). This proves the second inequality in equation (6.3). ■

## 7. An equivalent classical computer

Theorem 2.1 connects the optimal success probability *p* of computing a linear threshold function *f* with any matchgate circuit with the margin *ϵ* of this LTG. This is a somewhat peculiar connection, e.g. since the definition of the margin of an LTG *a priori* does not seem to have anything to do with probabilities. In order to understand this relation better, in this section we construct a very simple class of *classical* computers that are capable of (probabilistically) computing LTGs with precisely the same relation between *p* and *ϵ*.

To motivate this class, we reiterate the following simple example that was discussed in §2. Let *f*_{maj} denote the *n*-bit majority function as before, and let *ϵ*: = *n*^{−1} be its margin. Owing to theorem 2.1, there exists a matchgate circuit that computes this function with probability *p*_{maj} defined in equation (6.2), and this is the optimal success probability that any matchgate circuit can achieve. Now consider the following elementary classical computation, consisting of the following steps:

— Choose an

*n*-bit input string*x*.— Generate a random integer

*k*between 1 and*n*.— Output the bit value

*x*_{k}.

We now claim that, for every *x*, the output of this computation is *f*_{maj}(*x*) with probability at least *p*_{maj}. To see this, note that the probability *p*_{x} that the above procedure outputs 0 is given by7.1and the probability of outputting 1 is *q*_{x} = 1−*p*_{x}. If *x* contains more zeros than ones—i.e. if *f*_{maj}(*x*) is zero—then the probability *p*_{x} is at least *p*_{maj}, as can easily be verified. Similarly, if *x* contains more ones than zeros, *q*_{x} is at least *p*_{maj} as well. Thus, for any *x* the output of the computation is *f*_{maj}(*x*) with probability at least *p*_{maj}. In other words, the above classical computation computes the majority function with the same probability of success which can be achieved by the optimal matchgate circuit. Next, we will show that every LTG *f* with margin *ϵ* can be associated with a classical computation of the above nature.

The relevant class of classical computations is defined as follows. Fix a probability distribution on the set of integers from 1 to *n* + 1, together with a string *c* of *n* + 1 bits. We define the *weighted majority sampling* (WMS) computation associated with and *c* to consist of the following steps:

— Choose an

*n*-bit input string*x*.— Sample from the distribution , yielding

*k*∈[*n*+ 1] with probability*π*_{k}.— If

*k*≤*n*then output the bit*z*_{out}: =*x*_{k}⊕*c*_{k}. If*k*=*n*+ 1 then output*z*_{out}: =*c*_{n + 1}.

We say that an *n*-bit Boolean function *f* is WMS-computable with probability at least *p* if there exist and *c*, such that the above three-step procedure yields the output *z*_{out} = *f*(*x*) with probability at least *p* for every *n*-bit input *x*. We prove that the classes of WMS-computable and matchgate-computable functions precisely coincide.

### Claim

Let *p*∈(0.5,1]. A function is matchgate-computable with probability at least *p* iff this function is WMS-computable with probability at least *p*.

Consider a WMS computation with associated and *c*. It will be convenient to consider a slightly modified computation, where the output is instead of the bit *z*_{out}. This will facilitate notation in the proof (but does not play any essential role otherwise). Further, we let denote the expected value of given that *x* is the input of the computation.

We now prove the claim. Let *f* be an arbitrary *n*-bit Boolean function. It follows from §5*a* that *f* is matchgate-computable with probability at least *p* iff there exists a matchgate circuit *U* acting on *m* ≥ *n* qubits such that, for every *x*, one has

(a) |〈

*Z*〉_{x}| ≥ 2*p*−1 and(b) sign〈

*Z*〉_{x}= (−1)^{f(x)}.

Furthermore, using an argument analogous to that in §5*a*, it can easily be shown that *f* is WMS-computable with probability at least *p* if and only if there exist and *c* such that, for every *x*:

(a′) and

(b′) ,

for every *x*. We thus have to prove that, for every function, conditions (a) and (b) hold for some matchgate circuit *U* iff (a′) and (b′) hold for some and *c*.

Suppose first that (a′) and (b′) are satisfied for some and *c*. We define and by7.2for every *k*∈[*n*]. Note that the vector (*w*,*θ*) has unit 1-norm. Now let *x* be an arbitrary bit string and run the WMS computation as described above. Then the expected value of is7.3Owing to theorem 5.1, there exists a matchgate circuit *U* on *n* + 1 qubits such that7.4As for every *x*, it follows that conditions (a) and (b) are satisfied for *U*.

To prove the converse, consider an *m*-qubit matchgate circuit *U* such that (a) and (b) hold. Owing to theorem 5.1, there exists (*v*,*φ*) with 1-norm at most 1, such that7.5for every *n*-bit string *x*. Normalizing (*v*,*φ*) w.r.t. the 1-norm yields a normalized representation *w*: = *γv* and *θ*: = *γφ*, where *γ*^{−1}: = ∥*v*∥_{1} + |*φ*|. Note that *γ*^{−1} ≤ 1. Now choose and *c* such that equation (7.2) is satisfied. Using an argument similar to the first part of the proof, the expected value of the associated WMS computation is . We thus have7.6for every *x*, where *γ* ≥ 1. Using the identity , and the fact that (a) and (b) hold, it immediately follows that (a′) and (b′) are satisfied for .

## Acknowledgements

The author is grateful to S. Bravyi, I. Cirac, R. Jozsa, C. Kraus and K. Vollbrecht for discussions. Work supported by the excellence cluster MAP.

## Footnotes

↵1 Henceforth, whenever we refer to a ‘function’ we will often mean a Boolean function. This will be clear from the context.

↵2 The term ‘matchgate’ sometimes refers to a larger class of operations (tensors), which may be both non-unitary and which may act on more than two qubits, containing the unitary two-qubit gates (2.1) as a subclass; cf. Cai & Choudhary (2006

*a*,*b*) and Bravyi (2009). In this paper, however, a matchgate is always taken to be a unitary two-qubit operation as defined in equation (2.1).↵3 For convenience, we always assume that the first qubit is measured. This does not entail any loss of generality when considering matchgates, as any matchgate circuit followed by the measurement of the

*k*th qubit line can be mapped to an equivalent matchgate circuit followed by measurement of the first qubit (by an appropriate use of fSWAP gates); see §3.↵4 That is, the success probability is exponentially (in

*n*) close to 1.↵5 To see this, first note that the margin of a representation (

*w*,*θ*) ≡is a continuous function of*z*, being defined as the minimum of a finite number (i.e. 2*z*^{n}) of continuous functions for every*x*. Thus,*ϵ*(*f*) is the supremum of a continuous function in*z*, over all representationsof*z**f*with ∥∥*z*_{1}= 1. As the set of all such normalized representations is a compact set, it follows that the supremum is reached.↵6 Any real number

*a*∈[1,−1] can be expanded in a unique way as , where each*a*_{μ}∈{0,1}.

- Received June 23, 2010.
- Accepted August 10, 2010.

- This journal is © 2010 The Royal Society