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


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?

  • 1
    $\begingroup$ 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. $\endgroup$ Mar 6 at 17:34
  • $\begingroup$ 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 $\endgroup$
    – DaftWullie
    Mar 7 at 8:02
  • 2
    $\begingroup$ 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. $\endgroup$
    – DaftWullie
    Mar 8 at 7:52
  • 2
    $\begingroup$ This paper is potentially relevant semanticscholar.org/paper/… $\endgroup$ Apr 7 at 2:36
  • 1
    $\begingroup$ @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. $\endgroup$
    – unknown
    Jun 4 at 16:43

1 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.

  • $\begingroup$ 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! $\endgroup$ Apr 1 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.