Circuit from finite group of gates and classical simulations

Question

Let $ G $ be a finite group of quantum gates. Is it true that any circuit made using only gates from the finite group $ G $ can be efficiently simulated on a classical computer?

Here by circuit made from $ G $ I mean a circuit in which all gates are from $ G $ and all states are prepared and measured in the computational basis.

The Gottesman-Knill theorem says that any Clifford ( $ G $ equals the Clifford group) circuit can be simulated efficiently on a classical computer. So the answer is yes for at least some choices of a finite group of gates $ G $. I would imagine that if $ G $ is a finite abelian group then the theory of computation is very simple and can also be simulated efficiently on a classical computer.

It is worth noting that classical reversible computation (on $ n $ bits say) is $ G $ circuits with $ G=S_{2^n} $ the symmetric group on the $ 2^n $ bit strings.

Every group of size $ |G| $ is a subgroup of a symmetric group on $ |G| $ letters. So we can take $ log_2(|G|) $ bits and certainly find $ G $ is a subgroup of the symmetric group on $ 2^{log_2(|G|)} $ bit strings. The way to realize a group as a permutation group is just to act it on itself by left multiplication

https://en.wikipedia.org/wiki/Cayley%27s_theorem

anyway I have no idea is this can be done efficiently but certainly this seems like a way to represent circuits using a finite group of gates as just reversible classical circuits.

Again my question is about efficient classical simulation: if $ G $ is a finite group of quantum gates can every circuit in which all gates are from the group $ G $ and all states are prepared and measured in the computational basis be simulated efficiently on a classical computer?

Answer 1

Let me give an answer which is not really intended as an answer (in that it doesn't address what I suspect the question is aimed at. For example, it does not cover the case of Clifford gates), and rather aiming to get clarification of the question itself.

Imagine you have a finite group $G$ of size $|G|=N$. Since it is a group, every pair has an action $g_ig_j=g_k$. Since we know this is a group, we must have a proof that it's a group, which means we must be able to calculate the values $k$ for a pair of inputs $(i,j)$. Hence, let us pre-calculate all $N^2$ results $g_ig_j$ and store them in a (sorted) lookup-table. Given that $N$ is finite, the entire calculation must be finite.

Now, if we have a circuit of length $M$ comprising elements of $g$, the entire computation comprises looking up pairs in turn and replacing them with single elements until all we have left is the single element $g$ that represents the entire computation. This only requires $M-1$ lookups in the table. Hence, the simulation time is $O(M)$.

Now, what I assume the question really wants to ask is to let $N$ be a function of $n$, the problem size (i.e. number of qubits) and that, for any natural number $n$, $N$ is finite. This, for example, allows the sizes such as $N\sim 2^n$ (or even crazier), but excludes continuous groups. My answer does not apply to those.

Or, perhaps the specification may be (which could be equivalent): let $G$ be a finite group of gates acting on at most $k$ qubits (e.g. $k=2$), and consider the family of circuits on $n$ qubits comprising application of members of $G$ on arbitrary subsets of qubits. Is the simulation efficient (i.e. polynomial) in $n$?

Both of these possible specifications have an element of scaling with the number of qubits which is not explicitly present in the question specification.