key: cord-0047330-pa7j7x0g
authors: Boykett, Tim
title: Maximality of Reversible Gate Sets
date: 2020-06-17
journal: Reversible Computation
DOI: 10.1007/978-3-030-52482-1_12
sha: 2ae84c256b54b5cfc03800bf4d1d0e4c331b6a1b
doc_id: 47330
cord_uid: pa7j7x0g

We investigate collections of reversible gates closed under parallel and serial composition. In order to better understand the structure of these collections of reversible gates, we investigate the lattice of closed sets and the maximal members of this lattice, that is, collections that are not all gates, but the addition of a single new gate will allow us to construct all gates. We find the maximal closed sets over a finite alphabet. We then extend to ancilla and borrow closure for reversible gates. Here we find some structural results, including some examples.

For a given finite set A, we investigate the collections of reversible gates, or bijections of A k for all k. The work derived from Tomasso Toffoli's work [14] and as such we call closed systems of bijections reversible Toffoli Algebras (RTAs). We also consider ancilla and borrow closure, where an extra input and output is allowed; an ancilla is provided and returned in a particular state, whereas a borrowed bit is provided and returned in an arbitrary state.

The work also relates to permutation group theory, as an RTA C is a Nindexed collection of permutations groups,

In previous papers, Aaronson, Grier and Schaeffer have determined all ancilla closed gates on a set of order 2 [1] , and the author, together with Jarkko Kari and Ville Salo, has investigated generating sets [2, 3] and other themes.

In this paper, we determine the possible maximal closed systems, relying strongly on Liebeck, Praeger and Saxl's work [11] , and determine some properties of maximal borrow and ancilla closed RTAs.

We show that the maximal RTAs are defined by an index that defines the single arity at which the RTA is not the full set of bijections. We then show that for different indices and orders of A, only certain possibilities can arise. For ancilla and borrow closed RTAs we find that there is similarly an index below which the maximal RTAs are full symmetry groups and above which they are never full.

We start by introducing the background properties of RTAs and some permutation group theory. The next section is an investigation of maximality, with the main result, Theorem 4, taking up the main body of this section. We then investigate properties of borrow and ancilla closed RTAs.

In any RTA C, the unary part C [1] is found as a wreath product in all other parts, C [1] wrS n ≤ C [n] because the wire permutations give us the right hand factor while f 1 ⊕ · · · ⊕ f n for f i ∈ C [1] gives us the left hand side.

Let q be a prime power, GF (q) the field of order q, AGL n (q) the collection of affine invertible maps of GF (q) n to itself. We note that for all m ∈ N, AGL n (q m ) ≤ AGL nm (q). For a prime p, let Aff(p m ) = n∈N AGL nm (p) be the RTA of affine maps over A = GF (p) m .

We say that an RTA

. , x n , a) and g n+1 (x 1 , . . . , x n , a) = a implies that f ∈ C. If an RTA is ancilla closed then it is borrow closed. For any prime power q, Aff(q) is borrow and ancilla closed.

In this section we introduce some results from permutation group theory that will be of use. The maximal subgroups of permutation groups have been determined.

). Let n ∈ N. Then the maximal subgroups of S n are conjugate to one of the following G. It is worth noting that in the imprimitive case, A is a disjoint sum of k sets of order m, giving an equivalence relation with k equivalence classes of order m, the wreath product acts by reordering the equivalence classes as S k , then acting as S m on each equivalence class. In the wreath case, the set A is a direct product of k copies of a set of order m, the wreath product acts by permuting indices by S k then acting as S m on each index. Lemma 1. Let A be a set of even order and n ≥ 3. Then S A wrS n ≤ Alt(A n ).

Proof. S A wrS n is generated by S A acting on the first coordinate of A n and S n acting on coordinates.

The action of S A on A n is even because for each cycle in the first coordinate, the remaining n − 1 coordinates are untouched. Every cycle occurs |A| n−1 times, which is even, so the action of S A lies in Alt(A n ). S n is generated by S n−1 and the involution (n − 1 n). By the same argument, each cycle of the action occurs an even number of times, so the action of S n−1 and the involution ((n − 1) n) on A n lies in Alt(A n ) so we are done.

We have a similar inclusion for affineness.

Proof. AGL n (2) is generated by the permutation matrices {π (1,i) | i = 2, . . . , n} and the matrix 1 1 0 1 ⊕ i n−2 . These bijections are even parity because they only act on two entries, thus have parity divisible by 2 n−2 modulo 2 which is 0.

Proof. The same argument as above applies for S A . The action of S 2 swaps

pairs. This is even iff 4 divides |A|.

In this section, we will determine the maximal RTAs on a finite set A.

We have some generation results from other papers that will be useful. 

Theorem 20]).

We show that we can map these to 111, 112, 113 ∈ A 3 . There are three cases. See Fig. 1 .

Then λ will map a, b, c to the situation in the first case.

Case 3: Suppose a 3 = b 3 = c 3 . Then one of a 1 , b 1 , c 1 or a 2 , b 2 , c 2 must contain at least two values, wlog let a 1 , b 1 , c 1 be so. Then π (13) [3] .

For |A| = 5 the result follows from Theorem 2.

We know that this is not true for A of order 2, where B 2 (A) generates a group of order 1344 in B 3 (A), which is of index 15 in Alt(A 3 ) and is included in no other subgroup of B 3 (A). However we find the following.

Proof. For A of order 4 or more, we use the same techniques as in Lemma 5.

For A of order 2, we calculate. We look at C [4] as a subgroup of S 16 . The wire permutations Π [4] are generated by (2, 9, 5 , 3)(4, 10, 13, 7)(6, 11)(8, 12, 14, 15) and (5, 9)(6, 10)(7, 11) (8, 12) . Then i 1 ⊕ B 3 (A) is a subgroup of B 4 (A) acting on the indices {2, 3, 4}, generated by (1, 2, 3, 4, 5, 6, 7, 8) (9, 10, 11, 12, 13, 14, 15, 16) and (1, 2)(9, 10). It is a simple calculation to determine that this group is the entire alternating group A 16 , so Alt(A 4 ) ⊆ C [4] .

We can now state our main theorem.

for exactly one i and M belongs to the following classes: [1] is one of the classes in Theorem 1.

nonabelian simple group, with |A| = |T | (up to conjugacy) 7. i = 2, |A| ≡ 0 mod 4 and M [2] is an almost simple group (up to conjugacy) 8. i ≥ 3, |A| is even and

Remember that compositions of mappings of arity at least j will also be of arity at least j, so

. Thus M was not maximal, proving our first claim.

For the rest of the proof, take M maximal with

Suppose i = 1. Then B 1 (A) = S A and we are interested in the maximal subgroups of S A . From Theorem 1 we know that these are in one of the 7 classes.

Suppose

By the action of S A acting on the ith coordinate we obtain a ρb with a j = a j and b j = b j for all j = i. By the action of S i on coordinates we can move this inequality to any index. Thus by transitivity we can show that ρ = (A n ) 2 and is thus trivial, so our action cannot be imprimitive.

We now consider the cases of A odd and even separately.

, so by Theorem 2 we have all of B(A) and thus M is not maximal, a contradiction. [2] must be precisely this. So the case of A order 3 is left. We want to know which maximal subgroups of Sym(A 2 ) contain S A wrS 2 . There are 7 classes of maximal subgroups, we deal with them in turn.

-From the discussion above we know that M [2] is transitive and primitive on A 2 , so the second and third cases do not apply. Thus we are left with the case i = 2. From the above we know that the intransitive and imperfect cases cannot arise. Thus we need to consider the wreath, affine, diagonal and almost simple cases.

-|A| = 2: S A wrS 2 has order 8, B 2 (2) has order 24, so M [2] = S A wrS 2 is maximal and we are done. 

It is not immediately clear that all the classes of maximal RTAs can actually exist. So let us investigate a few small examples. Let us take A of order 2. For i = 1 we find no nontrivial subgroups, so the maximal is M [1] of order 1. For i = 2 case 4 gives us S 2 wrS 2 of order 8 as a maximal subgroup. We note that B 2 (A) = AGL 2 (2), i.e. all binary bijections are affine maps. For i ≥ 3 we have M [i] alternating as the only example, as we know from Toffoli [14] and others that the alternating bijections of arity i are generated by the collection of all permutations of arity less than i.

Taking A of order 3, we obtain a few more examples. For i = 1 we write A = {1, 2, 3} and we know that S 3 has maximal subgroups A 3 as well as (1 2) For A of order 4 things get a touch more complex. For i = 1 we get a number of maximal subgroups. A 4 is maximal. By fixing one element we obtain 4 maximal subgroups isomorphic to S 3 as intransitive subgroups. By imposing an equivalance relation with two classes of two elements each ( 1, 2 | 3, 4 or 1, 3 | 2, 4 or 1, 3 | 2, 3) we obtain subgroups isomorphic to S 2 wrS 2 that act imprimitively on A. AGL 2 (2) is of order 24, same as S 4 , we see that the affine maps are precisely the permutations, not maximal. There is no nonabelian simple group to allow a diagonal maximal subgroup. The wreath product also fails by order, and no nonabelian simple group of order less than 24 exists, so the almost simple case cannot arise. For i ≥ 2 we find M [2] = Alt(A 2 ) a maximal subgroup. For i = 2 we see that there are no nonabelian finite simple groups of order 16, so case 6 cannot arise. It can be shown by investigation of [4] that M [2] cannot be an almost simple group.

For orders 5 and above, we know that the maximal RTAs for i = 1 can be obtained by permutation group analysis directly. For A of odd order we have the wreath case S A wrS 2 maximal in B 2 (A) and none others. For A even we have the alternating and wreath cases easily constructible. We are left with the question whether, for A of order a multiple of 4, the diagonal or almost simple cases can actually arise.

The possibilities for the diagonal case with A of order equal to the order of a finite simple nonabelian group start with A of order 60. The other possibility is that |A| 2 = |T | for some finite simple nonabelian group T . The only known result in this direction is in [13] where they show that symplectic groups Sp (4, p) where p is a certain type of prime, now known as NSW primes, have square order. The first of these groups is of order (2 4 · 3 · 5 · 7 2 ) 2 corresponding to A of order (2 4 · 3 · 5 · 7 2 ) = 11760. We note that the sporadic simple groups have order that always contains a prime to the power one, so they are not of square order. We know that the Alternating group can never have order that is a square, as the highest prime less than n will occur exactly once in the order of the group. It might be possible that there are other finite simple groups of square order. As far as we are aware, there have been no further results in this direction.

Each of these possibilities is far beyond the expected useful arities for computational processes.

The other case is to look at almost simple groups. Let A be of order 4k, then we are looking for an almost simple action of degree 16k 2 . In [4] we saw that all primitive actions of degree 16 are alternating, that is, they are subgroups of A 16 . In order to find an example, we can hope to use results about primitive permutation groups of prime power [5] and product of two prime power [10] degrees, so we would be able to investigate A of order 4k for k ≤ 14. Once again this would include all examples of arities expected to be useful for computational processes.

The strength of Theorem 4 is partially due to the fact that there is no effect of the existence of mappings of a certain arity in a given RTA on the size of the lower arity part, as there are no operators to lower the arity of a mapping. This does not apply with ancilla and borrow closure. In this section we collect some results about maximal ancilla and borrow closed RTAs. The following result reflects the first part of Theorem 4. We will call k the index of the maximal ancilla closed or borrow closed RTA. From Theorem 2 we then note the following. In this case, we can say a bit more for index 2. If A is of order 3, then by the argument in Theorem 4 above, we find that M = Aff(A), the affine maps over a field of order 3. Otherwise A is at least 5 and B 1 (A) is no longer affine. See Lemma 11 below.

Similarly, we obtain the following, but see Corollary 1 below for a stronger result. Using similar arguments, we obtain the following. Suppose M is maximal with k = 4. We know that M [3] = B 3 (A). Then by Lemma 6 we find that M [4] [2] = B 2 (A) by Lemma 7. Let f ∈ N [2] − Deg(A) [2] , then f ⊕ f ∈ N [4] − Deg(A) [4] so N [4] (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 (241, 242) . With the wire permutations we obtain a subgroup of S 256 that is the alternating group, so M [4] = Alt(A 4 ) and by Theorem 3 we then get M [5] = Alt(A 5 ) and thus M is not maximal. Suppose A is even with more than 6 elements. The degenerate RTA Deg(A) ≤ M because M [1] = B 1 (A), but because Deg(A) is maximal and M [2] is a supergroup of Deg(A) [2] , M is all of B(A) and is not maximal. Let A be of even order, so a power of 2. Let f ∈ B n (A), f ∈ N − M . We know from Lemma 2 above that M [n] ≤ Alt(A n ) is not maximal, so the odd order argument above does not hold. By [12] we know that N We look at a few concrete examples. By [1] we know that for A of order 2, we have the following maximal ancilla closed RTAs.

-The affine mappings, -The parity respecting mappings, which either preserve the number of 1s mod 2, or invert it, -The odd prime-conservative mappings, that preserve the number of 1s mod p, an odd prime.

The affine mappings have index 3, the parity respecting index 2 and the odd prime-conservative mappings have index 1.

It remains an open problem whether these are the borrow closed maximal RTAs over A of order 2.

For A of order 3, we know that the affine maps Aff (3) is an index 2 maximal borrow closed RTA and a maximal ancilla closed RTA.

For A of order 4, we can say the following about index 2 maximals. There are the following inclusions, S 4 wrS 2 < ASp < AGL 4 (2) < Alt(4 2 ) where ASp is a group of order 11520 that consists of the affine maps where the linear part is a symplectic linear map in Sp (4, 2) . If M [2] = Alt(4 2 ) then M includes the affine maps properly. We know that the affine maps are maximal, a contradiction. M [2] = AGL 4 (2) for the affine maps that we know form a maximal borrow and ancilla closed RTA. It is possible that M [2] = S 4 wrS 2 or M [2] = ASp for some maximal M .

For A of order 5 or more, we know that index 2 arises only for the degenerate RTA Deg(A).

We have determined the maximal RTAs, using results from permutation group theory and some generation results.

As we have not been able to construct explicitly an example of a maximal RTA with i = 2 and M [i] of diagonal or almost simple type, the conjecture remains that these are not, in fact, possible. We note however that if such examples exist, they will arise for A of order 8 or more, so will probably not be relevant for any practical reversible computation implementation.

In future work we aim to determine the weight functions as described by [8] for maximal RTAs, in order to determine whether they hold some interesting insights.

The results for borrow and ancilla closed RTAs are not as comprehensive. We hope to determine these in the foreseeable future. We note interestingly that for a state set of order 5 or more, Lemma 11 indicates that if we can implement all permutations of the state set, we need only have one non-degenerate gate in order to implement all gates under borrow or ancilla closure. Similarly we see that once we can implement all affine maps on a state set of prime power order, then only one nonaffine gate is needed to implement all gates. For the ancilla case, many of the techniques of [1] will prove useful. In the ancilla case, we know all maximal RTA with index 2 except for A of order 4.

The classification of reversible bit operations

Closed systems of invertible maps

Finite generating sets for reversible gate sets under general conservation laws

On the list of finite primitive permutation groups of degree ≤ 50

A note on primitive permutation groups of prime power degree

Memoryless computation: new results, constructions, and extensions

GAP -Groups, Algorithms, and Programming

Galois connection for multiple-output operations

Towards an algebraic theory of Boolean circuits

On permutation groups of degree a product of two prime-powers

A classification of the maximal subgroups of the finite alternating and symmetric groups

Permutation groups containing affine groups of the same degree

Simple groups of square order and an interesting sequence of primes

Reversible computing

The research has been supported by Austrian Science Fund (FWF) research projects AR561 and P29931.Acknowledgements. Michael Guidici has helped extensively with understanding primitive permutations groups, for which I thank him greatly.