{'fraction_non_alphanumeric': 0.037818085762085056, 'fraction_numerical': 0.013647970414722198, 'mean_word_length': 4.207473635946814, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Fermionic Linear Optics and Matchgates

Fermionic linear optics is efficiently classically simulatable. Here it is shown that the set of states achievable with fermionic linear optics and particle measurements is the closure of a low dimensional Lie group. The weakness of fermionic linear optics and measurements can therefore be explained and contrasted with the strength of bosonic linear optics with particle measurements. An analysis of fermionic linear optics is used to show that the two-qubit matchgates and the simulatable matchcircuits introduced by Valiant generate a monoid of extended fermionic linear optics operators. A useful interpretation of efficient classical simulations such as this one is as a simulation of a model of non-deterministic quantum computation. Problem areas for future investigations are suggested.


Introduction
It is conjectured that standard quantum computation is more efficient than probabilistic computation. The conjecture is supported by the ability to efficiently factor large numbers [1] and simulate physics [2] using quantum computers, by proofs that quantum computers are more powerful with respect to some black boxes [3], and by results showing exponential improvements in communication complexity [4].
To delineate the conjecture one can consider models of computation where the basic operations are multiplication of linear operators in a given set G. Each operator in G is associated with a complexity (e.g. the length of its name), so that the complexity of a product g 1 g 2 . . . is the sum of the complexities of the g i . One can then ask questions about the complexity of calculating quantities like: 1. Computing the entries in a standard basis of a product. 2. Computing the trace of a product. When G is the a set of elementary quantum gates, the power of quantum computers is equivalent to being able to efficiently sample from a probability distribution with expectation an entry of a product and variance O(1) (see [5]). The power of one-bit quantum computers [5] is equivalent to sampling from a probability distribution with expectation the trace of a product and variance O(2 n ), where n is the number of qubits.
A special case is when the set G is the group of operators normalizing the group generated by the Pauli matrices (bit flip, sign flip). For n qubits, this group has order 2 O(n 2 ) and plays a crucial role in encoding and decoding stabilizer codes [6] and in fault tolerant quantum computation [7]. In [8] it is shown that even when this group is extended by projections onto the logical states of qubits, the complexities of the two questions above are polynomial. Two similarly defined groups consist of the linear optics operators for fermions and for bosons. In both cases, the groups are Lie groups of polynomial dimension in the number of modes. (Modes play the same role as qubits in these systems). A few simulatability results were known for these groups. For example, for bosons, the orbit of the vacuum state under the linear optics operators consists of Gaussian states, for which many relevant quantities can be efficiently computed. Similarly, particle preserving linear optics operators applied to exactly one boson lead only to states that are equivalent to classical waves [9,10].
Recently, Valiant [11] demonstrated a set of products of operators (those definable by a class of "matchcircuits") for which the complexities of the first question and many of its generalizations are polynomial. Terhal and DiVincenzo [12] realized that this set includes the unitary linear optics operators for fermions and that as a consequence, it is unlikely that it is possible to realize quantum computation in fermions by means of linear optics operators and particle detectors with feedback. They give a direct and efficient simulation of these operators based on fermionic principles. This result is at first surprising: In [13] it was shown that with bosons, linear optics operators and particle detectors with feedback are sufficient for realizing quantum computation. The difference between fermions and bosons is explained by realizing that the effects of particle detectors are expressible as limits of non-unitary linear optics operators in fermions but not in bosons. As a result, the states achievable with fermionic linear optics operators and particle measurements are in the closure of a "simple" set.
Since matchgate operators are non-unitary, one can ask what additional power is provided by Valiant's simulation of matchgates. Here it is shown that the two-qubit matchgates densely generate the monoid given by the closure of a group of extended fermionic linear optics operators in the Jordan-Wigner representation [14]. This group defines the non-deterministic computations that can be physically realized with unitary linear optics operators and particle measurements. The equivalence of two-qubit matchgates and fermionic linear optics two-qubit operators generalizes to the set of simulatable matchcircuits introduced by Valiant.

Fermionic Linear Optics
Let I, X (k) , Y (k) , Z (k) denote the identity and the Pauli operators acting on qubit k. Define U k = Z (1) . . . Z (k−1) U (k) (U 1 = U (1) ) for U = X, Y . Then the U k define a representation of fermionic mode operators. In particular, (X k + iY k )/2 and (X k − iY k )/2 represent the annihilation and creation operators for mode k. Let L 1 be the linear span of the identity together with the U k for 1 ≤ k ≤ n, where n is the number of modes (or qubits). The set G 1 of fermionic linear optics operators is the set of invertible matrices that preserve L 1 by conjugation. That is, g ∈ G 1 iff for all A ∈ L 1 , gAg −1 ∈ L 1 . The terminology refers to the property that conjugation of an annihilation or a creation operator results in a linear combination of such operators. Let L 2 be the set of products of two operators in L 1 , so that L 2 = L 1 L 1 . The group G 2 of extended linear optics operators is the set of invertible matrices that preserve L 2 . Note that G 1 ⊆ G 2 . (In bosons, the analogous definitions lead to identical groups.) The group G 2 is considered to be "unphysical" for fermions, due to the presence of odd products of annihilation and creation operators. In Sect. 6 it is shown that G 2 is naturally viewed as a subgroup of G 1 for one more mode.
The space L 2 is a (complex) Lie algebra. It is spanned by the Pauli operator products given by I, U k , Z (k) , and U (k) Z (k+1) . . . Z (k+l) V (k+l+1) with U, V ∈ {X, Y }. The dimension of L 2 is 2n 2 +n+1. By considering general sums of Pauli products, one can check that if for every A ∈ L 2 , [X, A] ∈ L 2 , then X ∈ L 2 . It follows that L 2 is the Lie algebra of G 2 . All strictly quadratic (in L 1 ) terms of L 2 , together with the identity also form a Lie algebra L ′ 2 of dimension 2n 2 − n, which is the Lie algebra of G 1 . Physically, realizable operators are continuously generated from the identity. As a result, for the remainder of the paper, G i is assumed to be given by the exponentials of L i . 1 In using (extended) linear optics operators for computation, one starts with the vacuum state |v n = |0 . . . 0 1...n and applies operators in G 1 (G 2 ) and measurements in the number basis |0 k , |1 k for a mode. The outcomes of measurements are given by applying the measurement projections |0 k k 0| = 1 2 (I + Z (k) ) and |1 k k 1| = 1 2 (I − Z (k) ). For standard computation, which projection "happens" is determined by the square amplitude of the result of applying it. For non-deterministic computation we can "choose" the outcome. In either case, analysis of the capabilities requires studying products of operators in G i and the measurement projections. Let S i be the monoid given by the topological closure of G i .
If G 2 and measurements could be used for efficient faithful quantum computation, then the set of states S n obtained with such operators from the n-mode vacuum state has to contain sufficiently large subspaces. That is, the 2 m dimensional state space of m qubits must be contained in S n with n = O(poly(m)). The following theorem makes this unlikely.

Theorem 1 The monoid generated by measurement projections and
Proof. This is a consequence of the fact that the measurement projections are limits of elements of G 2 : Since G 2 is a 2n 2 + n + 1-dimensional Lie group, Thm. 1 implies that S 2 |v n is the closure of a small dimensional space. This suggests that S 2 is not sufficiently strong for quantum computation. The fact that the normalizer of the Pauli group together with standard measurements are insufficient [8] follows in a similar way. That is, applying normalizer operators and projections onto stabilizer codes to the standard initial state always results in stabilizer states.
Note that a similar result cannot be shown for bosonic linear optics operators with particle measurements. Only the projection operator onto the 0 boson state of a mode is expressible as a limit of (non-unitary) linear optics operators. This provides an explanation of why efficient linear optics quantum computation is possible [13].

Matchgates and Linear Optics Operators
In [11], Valiant introduced a family of linear operators (called matchgates) acting on qubits. Matchgates are based on a graph theoretic construction. Valiant showed that under certain conditions, the coefficients of matrices defined by products of matchgates could be efficiently calculated. Matchgates acting on two qubits were shown to satisfy a set of 5 equations, the matchgate identities. If B is the matrix defined by a matchgate acting on two qubits, then the following are 0: Let M 2 be the set of matrices B satisfying the identities M i = 0 and either 11|B|11 = 0 or B is diagonal. Valiant showed that these matrices are realizable by matchgates.

Theorem 2
The closure of M 2 is S 2 for two modes (or qubits).
Proof. The Lie algebra which densely generates S 2 is spanned by the 11 operators Here UV abbreviates U (1) V (2) . One can check that for This means that T is an eigenvector of the Lie group L generated by L⊕L = {A⊗I + I ⊗A : A ∈ L}. Note that L = {B ⊗ B : B ∈ G 2 }. L preserves antisymmetric vectors, so the statement that LT ∝ T is equivalent to R T LT = 0 for all R antisymmetric such that R T T = 0. The dimension of such R is 5, and here is a basis: Define the expressions Since for two qubits L T 2 = L 2 , members B of G 2 satisfy the identities E i = 0, E T i = 0. Because these identities are all derived from an eigenvector condition, the set of matrices B satisfying them is a closed monoid G ′ 2 containing G 2 . Using the equivalence one can check that the following hold Mathematica instructions to check the above relationships are included verbatim in Appendix A.
Since diagonal matrices trivially satisfy E i = 0, E T i = 0 (i > 1) and E 1 − E T 1 = 0, the identities imply that M 2 ⊆ G ′ 2 . Let M ′ 2 = {B ∈ M 2 : 11|B|11 = 0}. By directly solving for the entries of B other than 11|B|11 in the first summand of the M i , one can see that M ′ 2 is an analytically coordinatizable 11 complex dimensional manifold. The diagonal members of M 2 are in the closure of M ′ 2 . The identities also imply that the elements of G 2 , and therefore those of S 2 , satisfy M i = 0. It follows that the B ∈ S 2 with B diagonal or 11|B|11 = 0 are in M 2 .
For invertible B, the identities E i = 0 imply that B(XY )B T = λXY for λ = 0. It follows that the tangent space at B is exactly that of G 2 at B. Consequently, M ′ 2 and G 2 contain the same invertible matrices satisfying 11|B|11 = 0. It remains to show that these matrices are dense in both sets. For M ′ 2 it suffices to observe that for fixed 11|B|11 = 0, there is an invertible B ∈ M ′ 2 , which implies that the determinant function is not null on this linearly defined subset. Hence the complement of the determinant's null set is dense. For G 2 the density property follows from the fact that the subgroup generated by XI and XX acts transitively on the basis states.

Simulatable Matchcircuits
Valiant showed that any composition of operators consisting of two qubit matchgates on the first two qubits and gates of the form e t(X (k) X (k+1) ) and e t(Y (k) Y (k+1) ) is efficiently simulatable in the following sense: If B is a product of m such gates, then many sums of squares or square norms of entries of B can be computed efficiently in m and n (the number of qubits). Let M be the set of all products of the gates mentioned.

Theorem 3
The closure of M is S 2 .
Proof. By definition and by Thm. 2, M ⊆ S 2 . It suffices to show that the invertible operators in M generate G 2 . This can be checked directly by using the Bloch sphere rules for conjugating products of Pauli matrices by 90 • rotations (e −iU π/4 ) around other products [15]. For example, . The latter operator can be deduced similarly to the way Z (1) Z (2) X (3) was obtained. Induction can be used to extend to arbitrarily many qubits.

Non-deterministic Computations
A non-deterministic computation with fermionic linear optics consists of a sequence of linear operators and measurements, where one post-conditions on the measurement outcome in the sense that one multiplies the state by the appropriate projection operator. The outcome is not normalized. Let U be the implemented operator. The minimal quantities one wishes to compute efficiently are tr( v n |U † (I ± Z (k) )U|v n ), which give the relative probabilities of the outcome of a measurement on the k'th mode. Suppose that implementable operators form a monoid and include the standard measurement projections. Since |v n v n | = k ((I + Z)/2) and (I + Z) = (I + Z) † (I + Z), it suffices to be able to compute, for each implementable U, tr(U † U) = kl |U kl | 2 . This motivates a definition that works for any monoid generated by elementary operators: An efficient simulation is defined to be an efficient algorithm for computing tr(U † U) for an explicitly implemented (as a product of elementary operators) U. Efficiency is defined in terms of the implementation complexity of U. With this definition, Valiant demonstrated an efficient simulation of matchcircuits composed of certain matchgates. The purpose of this section is to discuss how that leads to an efficient simulation of a dense subset of the monoid S 2 with naturally defined generators.
An elementary fermionic gate is an operator of the form αe itU = q + rU with U one of the products of Pauli operators in L 2 other than the identity. The coefficients q and r are required to be complex rationals with q = 0. Let d be the number of digits needed to denote these rationals. The description length of q + rU is Ω(2 log(n) + d), where the summand 2n is the description length of U, one of O(n 2 ) many possible Pauli products. The elementary projection is the operator (I + Z (n+1) )/2. It is implementable non-deterministically by post-selection on a particle measurement.
The elementary fermionic gates can be realized in terms of the operators allowed in simulatable matchcircuits: Simply conjugate one of these operators by the appropriate sequence of 90 • allowed operators. Note that the 90 • operators are elementary if scaled by √ 2. The standard measurement projections are allowed in matchcircuits. It is therefore possible to take a product of elementary fermionic gates and projections, and efficiently express them using allowed matchgates. It follows that Valiant's algorithm can be used to efficiently simulate the monoid E 2 generated by elementary fermionic gates and projections. The goal is to show that these operators densely generate S 2 .
Theorem 4 Except for a scale factor, the operators of G 2 on n modes are implementable by first adjoining a mode in state |0 n+1 , applying a sequence of unitary operators of G 2 for n + 1 modes and elementary projections and finally discarding mode n + 1.
Proof. It suffices to show that e tZ (n) with real t is implementable up to a scale. This follows from the observation that other real exponentials of Pauli operators are conjugates of e tZ (n) by unitary operators, and these together with unitary operators generate G 2 .
To implement e ±tZ (n) realize the following sequence of operators: 1. Adjoin |0 n+1 (if that hasn't already been done).
To see how this works, apply it to α|0 n + β|1 n .
Step 2 is a partial swap with a phase and results in α|0 n + β(cos(s)|1 n |0 n+1 + i sin(s)|0 n |1 n+1 ). The elementary projection results in (α|0 n + cos(s)β|1 n )|0 n+1 . It follows that the effect is the same as applying a scalar multiple of e − ln(cos(s))Z (n) /2 . The other sign in the exponent can be obtained by replacing step 2. with: Proof. This follows from Thm. 4 and the fact that the elementary rotations e itU for U a Pauli product densely generate all such rotations. (See, for example, [16].) It can be seen that the ability to efficiently simulate non-deterministic computation as defined above leads to an efficient simulation of a quantum computation with measurements and future operators conditioned on the measurement outcomes. The method is described in [12] and basically consists of simulating, at each step, the random measurement outcome, using a calculation of the conditional probability distribution.
A potentially easier problem then efficient simulation of a monoid is to determine, for an implemented U, whether U = 0. Observe that if it was possible to use S 2 with elementary generators to efficiently and faithfully realize quantum computation, then the zero-test algorithm can be used to efficiently solve problems in polynomial quantum non-deterministic time as defined in [17]. In [18] it was shown that this is hard for the polynomial hierarchy.

Identifying the Lie Algebras: G 1 is General
Let L • 2 be the set of trace zero members of L 2 . The adjoint action of G 2 on L • 2 permits representing members of G 2 as (2n 2 + n) × (2n 2 + n) matrices. The representation is faithful up to scalar multiples, because L • 2 algebraically generates all operators on the n qubits. This means that products of elementary operators can be efficiently computed in the representation. The reverse procedure, i.e. finding a decomposition of a represented operator in terms of a product of exponentials of Pauli products is also possible, though less obviously so. For this purpose it is more useful to recognize L • 2 as the Lie algebra so 2n+1 C and work in the fundamental representation. One way to recognize L • 2 is to realize that it is (isomorphic to ) a subalgebra of L ′ 2 for one more qubit. The mapping is accomplished by modifying the members of the form U k by multiplying with X (0) . This makes the operators strictly quadratic for fermionic modes 0, . . . , n (in this order). Then observe that L ′ 2 's adjoint action on L 1 is the fundamental representation of so 2n+2 C. The algebra can now be identified. Incidentally, this construction shows that in a sense L 2 is no more general then L ′ 2 despite appearances. This together with the results of the previous section implies that the simulation algorithm of Terhal and DiVincenzo [12] can be used to simulate S 2 with the same generality as Valiant's.
Here is the direct way to identify L • 2 as a Lie algebra: In the fundamental representation so 2n+1 C is spanned by the antisymmetric matrices s ij = |i j| − |j i| for 0 ≤ i < j ≤ n. The identification is made via the correspondences This identification of L • 2 permits efficiently representing a product of elementary operators as a (2n + 1) × (2n + 1) matrix. Let A be a matrix thus obtained. Then A T A = I, and this identity characterizes the Lie group generated by the s kl . The process of representing a matrix satisfying A T A = I as a product of elementary operators is straightforward by using a variant of Gaussian elimination to represent A as a product of O(n 2 ) matrices of the form e its kl = (I +s 2 kl )−cos(t)s 2 kl + i sin(t)s kl (t may be complex). By using conjugation rules by 90 • rotations, one can then expand this into a O(n 3 ) product consisting only of operators that are allowed for Valiant's simulatable matchcircuits.

Concluding Comments
It is true that bosons can be represented by paired fermions. So why does this not lead to an efficient realization of quantum computers by using this representation together with techniques for bosonic linear optics? One answer is that the bosonic linear optics operators in this representation correspond to Hamiltonians that are quartic in the annihilation and creation operators and are therefore not in L 2 . It is in fact not hard to see that adding to L 2 only the Hamiltonian Z (1) Z (2) , the Lie algebra generated contains all products of Pauli matrices and so generates all invertible matrices [19].

Suggested problem areas for future investigations:
1. Determine the complexity of efficiently simulating representations of the three families of simple complex Lie groups. Is the complexity polynomial in the dimension of the groups? Notes: The results of Valiant, Terhal and Divincenzo and this paper show that the answer is "yes" for one family of representations.
The answer might depend on the choice of generators and elementary operators. The fundamental representation of each such group can be used to make a reasonably natural definition.
Which projectors in a representations are to be assumed as elementary operators? They should be in the closure of the Lie group.
Semisimple Lie algebras can be analyzed in terms of their simple parts. What about non-semisimple ones?
2. What finite monoids of operators are efficiently simulatable? Notes: Again, the choice of generators may be crucial, and it is desirable that it is "natural" in some sense.
The monoids associated with n-ary stabilizer codes via the appropriate normalizer are efficiently simulatable in terms of the number of systems used.
Is the stabilizer code example naturally generalizable?
3. Problem areas 1. and 2., but for efficiently determining whether a product of generators is zero. Is this sometimes strictly easier to do?
4. Find a group or monoid of operators where the probabilistic behavior of a (quantum) computation is efficiently simulatable, but the non-deterministic behavior is not.

Notes:
It is necessary to define what is meant by "probabilistic" behavior. The one case where an interpretation is readily available is if the group is unitary and the initial state as well as standard measurements are provided. For a monoid, one approach is to allow as measurements some or all partitions of unity definable by its operators. The monoid should be (densely) generated by its unitary operators and projections associated with measurements.