6

This question is inspired by the question Is the Clifford group finite? where it is shown that the Clifford group (the second level of the Clifford hierarchy) is finite. Here, finite means finite mod global phases. The Pauli group, which is the first level of the Clifford hierarchy, is also finite. Is the $ k $-th level of the Clifford hierarchy finite, even for $ k \geq 3 $?

Edit: This paper claims above equation 2 that "The $M$-th level of this hierarchy is a finite set of unitaries (if the global phases are ignored)". I don't see a reference or proof for finiteness. How does one show this?

Update: I think this is the bound that Markus Heinrich is describing. The $ n $-qubit Pauli group $ P_n $ as a subgroup of $ SU_{2^n} $ is an extraspecial 2 group of order $ 2^{2n+1} $. It is generated as a group by $ 2n $ elements (the $ n $ Pauli $ X $s and the $ n $ Pauli $ Z $s). The $ k $-th level of the Clifford hierarchy for $ n $ qubits is defined by $$ \mathcal{C}^k:=\{ V \in SU_{2^n}: VgV^{-1} \in \mathcal{C}^{k-1}, \text{for all } g \in P_n \} $$ So every $ V $ in this set defines a group homomorphism $ {\rm Ad}_V: SU_{2^n} \to SU_{2^n} $ which has the additional property that when we restrict the domain to $ P_n $ then the image lies in $ \mathcal{C}^{k-1} $. That is, every $ V \in \mathcal{C}^k $ defines a map $ {\rm Ad}_V: P_n \to \mathcal{C}^{k-1} $. There are at most $| \mathcal{C}^{k-1} |^{|P_n|}=|\mathcal{C}^{k-1}|^{2^{2n+1}}$ such set maps $ {\rm Ad}_V $ for the $ k $-th level. But we can actually obtain a much tighter bound since $ {\rm Ad}_V $ is a group homomorphism and thus is determined by where it sends the $ 2n $ generators of $ P_n $. So in fact there are at most $ |\mathcal{C}^{k-1}|^{2n} $ such maps $ {\rm Ad}_V $ for the $ k $-th level.

The final question is how many different $ V \in SU_{2^n} $ can correspond to the same $ {\rm Ad}_V $. It is well know that the kernel of the adjoint map for a semisimple Lie group is exactly the center. So the kernel of the adjoint map for $ SU_{2^n} $ is all $ 2^n $ multiplies of the identity matrix by $ e^{2 \pi i /2^n} $. This is all a fancy way of saying that conjugation by $ V,V' $ gives the same map if and only if $ V,V' $ differ by a global phase. There are only $ 2^n $ global phases in $ SU_{2^n} $. So we just multiply the number of possible $ Ad_V $ by $ 2^n $. So a bound for the number of elements is $$ |\mathcal{C}^k| \leq 2^n |\mathcal{C}^{k-1}|^{2n} $$ For example that tells us that for $ n=1 $ qubit $ |\mathcal{C}^3| \leq 2 (48)^{2} $ I'm sure there are better bounds that can be obtained, especially for the $ k=3 $ case, if, as alluded to in the answer by Markus Heinrich, you know more about certain subgroups of the Clifford group.

Frederik vom Ende
  • 4,163
  • 3
  • 12
  • 49

1 Answers1

6

The third level is certainly finite, as it is a subset of all maps from the Pauli to the Clifford group, and both are finite sets. By induction, every level is thus finite.

It is a much harder problem to actually compute the cardinality of the $k$-th level. Even for the third level, this is non-trivial. However, it can in principle be done by a counting argument similar to the computation of the cardinality of the Clifford group, but requires some understanding of the Abelian subgroups of the Clifford group. I cannot give the argument right away, but I think it should be possible, given a few hours of time and the right literature. However, I also think that this counting argument cannot be generalized to higher levels.

Nevertheless, is should be possible to give an upper bound on the cardinality, at least for $k=3$. It is known that the third level consists of generalized semi-Clifford unitaries (https://arxiv.org/abs/0810.5108), which may be exploited for a simpler counting argument. A related, more recent result is obtained in http://arxiv.org/abs/2006.14040

Markus Heinrich
  • 5,652
  • 11
  • 22