We propose the theory of Cayley graphs as a framework to analyse gate counts and quantum costs resulting from reversible circuit synthesis. Several methods have been proposed in the reversible logic synthesis literature by considering different libraries whose gates are associated to the generating sets of certain Cayley graphs. In a Cayley graph, the distance between two vertices corresponds to the optimal circuit size. The lower bound for the diameter of Cayley graphs is also a lower bound for the worst case for any algorithm that uses the corresponding gate library. In this paper, we study two Cayley graphs on the Symmetric Group
S2n: the first, denoted by
In, is defined by a generating set associated to generalized Toffoli gates; and the second, the hypercube Cayley graph
Hn, is defined by a generating set associated to multiple-control Toffoli gates. Those two Cayley graphs have degree
n2n−1 and order
2n!. Maslov, Dueck and Miller proposed a reversible circuit synthesis that we model by the Cayley graph
In. We propose a synthesis algorithm based on the Cayley graph
Hn with upper bound of
(n−1)2n+1 multiple-control Toffoli gates. In addition, the diameter of the Cayley graph
Hn gives a lower bound of
n2n−1.
We study perfect state transfer on Cayley graphs from the point of view that state transfer is a property of a graph and not of a group. This paper is a bridge between the classical question about isomorphic Cayley graphs of non-isomorphic groups and quantum walks on graphs.
We show that a Cayley graph of a group with an abelian subgroup of index two is a Cayley graph of an abelian group under any one of three hypotheses, two drawn from the theory of isomorphic Cayley graphs. A statement of the same kind holds for extraspecial groups: every Cayley graph of an extraspecial
p-group of order
p2n+1 with a conjugacy-closed connection set is a Cayley graph of
Zp2n+1. From these results we deduce that every explicit construction of perfect state transfer in the six papers we survey, on dihedral, dicyclic, generalized dihedral,
V8n and extraspecial
2-groups, is a non-abelian presentation of an abelian Cayley graph. Moreover, we show that a non-abelian group with an abelian subgroup of index two admits a connected Cayley graph with perfect state transfer if and only if its order is divisible by four.
Genuinely non-abelian examples do exist. We prove that, for every odd prime power
q≥5, the
SL(2,q) graph of Pantangi and Sin, which they showed to admit perfect state transfer, is a Cayley graph of no abelian group; to our knowledge, this is the first infinite family of Cayley graphs with perfect state transfer provably admitting no abelian Cayley presentation. We also construct an infinite family of Cayley graphs with peak state transfer and determine all regular subgroups of the automorphism group of every member.
An appendix records a census of the connected vertex-transitive graphs with perfect state transfer on at most
30 vertices.