6
$\begingroup$

This question is inspired by

Is the Clifford group finite?

Which shows that that the Clifford group (the second level of the Clifford hierarchy) is finite. (finite meaning 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

https://arxiv.org/pdf/1710.07256.pdf

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 $ 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 $$ 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 $ Ad_V $ for the $ k $th level. But we can actually obtain a much tighter bound since $ 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 $ Ad_V $ for the $ k $th level. The final question is how many different $ V \in SU_{2^n} $ can correspond to the same $ 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.

$\endgroup$
2
  • $\begingroup$ Nice question! It was very useful to me! $\endgroup$
    – R.W
    Dec 6, 2022 at 14:20
  • $\begingroup$ @R.W that's great to hear! If you don't mind sharing, what was it useful for? I'm always interested in stuff people are up to with the Clifford hierarchy! $\endgroup$ Dec 6, 2022 at 17:43

1 Answer 1

6
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ The first statement doesn't seem obvious to me. How is the third hierarchy a subset of all maps from the Pauli to Clifford? $\endgroup$
    – unknown
    Dec 2, 2022 at 18:08
  • 2
    $\begingroup$ @unknown I've updated my question with some details fleshing out the bound that Markus Heinrich describes here. $\endgroup$ Dec 2, 2022 at 22:16
  • 1
    $\begingroup$ As far as I know $C^k$ is not a group for $k>2$, so how could $Ad_V$ be a group homomorphism? $\endgroup$
    – unknown
    Dec 2, 2022 at 22:58
  • 1
    $\begingroup$ @unknown any element from the third level maps by definition Paulis to Cliffords, those the third level is a subset of all maps from the Pauli to the Clifford group (up to phases). $Ad_V$ is a group homomorphism of the unitary group, but not as a map $P_n\rightarrow \mathcal{C}^{k}$. However, it is still determined by its action on the generators of $P_n$ $\endgroup$ Dec 3, 2022 at 18:46
  • $\begingroup$ Ya exactly, $ Ad_V $ is always an injective group homomorphism from $ P_n $ to $ SU_{2^n} $ it just also has the property that whenever $ V \in \mathcal{C}^k $ then the image of $ Ad_V:P_n \to SU_{2^n} $ lies within $ \mathcal{C}^{k-1} $. $\endgroup$ Dec 3, 2022 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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