Different forms of computational systems, such as binary computers and Turing
Machines, are known to be able to efficiently simulate each other. This is the basis of the Church-Turing Thesis which stipulates that any sufficiently powerful model of computing is equivalent to any other – any algorithm in one model can be translated, in polynomial time, to an equivalent algorithm in another. In 1982 a new form of computation was introduced which is based on the effects of Quantum Mechanics. It is currently unknown if Quantum Computing can be efficiently simulated by a classical computer, and thus might be a more powerful system of computing.
The aim of this dissertation is to study the complexity of quantum computations
from the perspective of groups. Two groups will receive extensive study. Each Toffoli group is determined and a minimal generating set for each will be constructed, also the type of simple group created by the direct limit of the Toffoli groups will be determined. The frames of each Pauli group will be analyzed and lead to a different realization of the Clifford Group. Let h be the Hadamard Gate, a purely quantum operator, and let P2n be the collection of permutation matrices of alternating type. We will see how SO2n(ℤ[1/2]).〈H〉 = 〈(h⊗I)σ|σ∈P2n〉, and that this suggests an algorithm which decomposes a quantum operator into a sequence of basic operators which are purely quantum or purely classical. This metric, and another based on buildings, will be explored.