It is well known that the first three levels of the Clifford hierarchy (over $n$-qubits) $C_1, C_2, C_3, \dots, C_n, \dots $ correspond to

$$C_1 \equiv \text{Pauli group}$$

$$C_2 \equiv \text{Clifford group}$$

$$C_3 \equiv \text{Universal unitaries}$$

As any third-level element brings $C_2$ towards universal quantum computation, this fact is very often used in schemes of computation based on magic-state injection and fault-tolerant implementations. My question is then the following:

Are there specific examples of applications that necessarily require gates in the higher levels of the Clifford hierarchy?

It is well-known as well that $C_i \subset C_{i+1}$ for any $i \in \mathbb{N}$, and inclusions do not work the other way around, i.e., there exists always an element in a higher level that is not present in a lower level. One example of a family that is always in $C_i$ but not in $C_{i-1}$ is the family of unitaries $\text{diag}(1,e^{2\pi i/2^i})$.

  • 2
    $\begingroup$ That depends on what you mean by "necessarily require". As you say, any gate that's further down the hierarchy can be approximated by gates in $C_3$ to arbitrary accuracy. If you're asking about exact implementation, then the Fourier transform is a good example of a subroutine that uses gates elsewhere in the hierarchy. Hence any algorithm that uses Fourier transform, e.g. Shor's. $\endgroup$
    – DaftWullie
    Feb 16, 2023 at 9:18
  • 1
    $\begingroup$ I think the "necessarily require" would mean that would be totally unreasonable -- the cost would increase, gate complexity would increase, one would need asymptotical approximations, etc. -- to achieve the same results by using elements in $C_3$ instead. In the case of Shor, would be related to write the algorithm equivalently by using only elements in $C_3$ and not higher orders. $\endgroup$
    – R.W
    Feb 17, 2023 at 15:59
  • $\begingroup$ where "totally unreasonble" = exactly what people plan to do with fault-tolerant quantum computers. $\endgroup$
    – DaftWullie
    Feb 17, 2023 at 16:28


Your Answer

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