# Circuit from finite group of gates and classical simulations

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?

• Following the proof of GK theorem, it seems that it cannot be trivially extended to every finite group. On the other hand, I do not see simple counter-examples as well. Mar 6 at 17:34
• I suppose that the Clifford case has a lot more structure and a lot more going for it than you've picked out in your question. There are two groups: the Clifford group and (an Abelian subgroup of) the Pauli group. There are three very useful things here: (i) the initial state is easily decomposed in terms of the Pauli subgroup, (ii) since the subgroup is Abelian, we can just deal with $n$ individual terms instead of a product of $n$ terms (which would have $2^n$ components), and (iii) the action of the Clifford group on the Pauli group is easily calculated Mar 7 at 8:02
• One difficulty that we have with this question is that I don't believe the gap between quantum universality and quantum simulability is well understood. After all, that would instantly answer your question - a finite group of quantum gates cannot be approximately universal. So, if the answer to your question were negative, we'd be looking at a group which is neither universal nor classically simulable. Mar 8 at 7:52
• This paper is potentially relevant semanticscholar.org/paper/… Apr 7 at 2:36
• @IanGershonTeixeira I think if you take $G$ to be any polycyclic group then you should be able to efficiently simulate gates in its normalizer $C$ (in some bigger group, for example all unitaries if working in a complex representation). You track the action of a gate in $C$ by tracking its affect on the generators of $G$ : $G \to U^{-1} G U$. This just maps the exponents of the generators to another set of exponents...a generalized tableaux of sorts. Jun 4 at 16:43

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.

• I agree, this is an important point. The group is not just one, there is a different group for each number of qubits $n$. So a scaling must be specified. If I'm not wrong, the scale you mention, $N\propto 2^n$, applies to Clifford gates. So the task could be stated as: show that $N\propto 2^n$ implies that the output of the circuit, applied to $\left|0\right>$, can be classically calculated in polynomial time. Btw, this is my interest; maybe the user that asked the question is more interested in something else! Apr 1 at 10:41