Skip to main content
15 votes
Accepted

Is there a closure property for the entire Clifford hierarchy?

It is actually possible to show that there is a simple, single-qubit operator (identified in discussion with John van de Wetering), which is a product of elements of $\mathcal C^{(3)}$ but which does ...
Niel de Beaudrap's user avatar
6 votes
Accepted

Universal Gate Set, Magic States, and costliness of the T gate

The T state $Z^{1/4}|+\rangle$ has four core advantages over most other states: You can physically inject T states at pretty high fidelity. It has a reasonably cheap distillation circuit, as far as ...
Craig Gidney's user avatar
  • 37.1k
6 votes
Accepted

Where does the Clifford circuits stand in the complexity hierarchy?

Clifford circuits alone are not universal for classical computation, at least not under common complexity-theoretic assumptions. More precisely, Aaronson and Gottesman showed that deciding whether the ...
Markus Heinrich's user avatar
6 votes
Accepted

Is this single qubit gate in the Clifford hierarchy?

I assume that you mean entries in $\mathbb Q[\zeta_{2^k}]$, up to a global phase, right? This is certainly true for $k=1,2$: Clearly, any element of the Pauli group has, up to a global phase, entries ...
Markus Heinrich's user avatar
6 votes
Accepted

Is the Clifford hierarchy finite?

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 ...
Markus Heinrich's user avatar
5 votes
Accepted

Can Clifford gates be diagonalized using a gate from the third level of the Clifford hierarchy?

TL;DR: No, this isn't always possible. In fact, a third of the gates in the single-qubit Clifford group cannot be diagonalized by a matrix in $\mathcal{C}^{(3)}$. First note that the Pauli matrices $\...
Adam Zalcman's user avatar
  • 22.4k
5 votes

Where does the Clifford circuits stand in the complexity hierarchy?

are the Clifford gates alone, without magic states, Turing complete? A circuit has a fixed size, so it can't increment a number larger than that size. A Turing machine can increment an n-digit number,...
Craig Gidney's user avatar
  • 37.1k
4 votes

Can every unitary be approximated by gates from the Clifford Hierarchy?

This is too long for a comment but not an answer. First we must define some notion of closeness of unitaries. Other metrics should be fine, but operator norm seems like a good one. Now I think your ...
Jonas Anderson's user avatar
3 votes

Universal Gate Set, Magic States, and costliness of the T gate

Imagine you're interested in implementing a gate $$ P_k=\left(\begin{array}{cc} 1 & 0 \\ 0 & e^{i\pi/2^k} \end{array}\right), $$ so $Z=P_0$, $S=P_1$ and $T=P_2$. Now imagine that you're going ...
DaftWullie's user avatar
  • 58.2k
3 votes
Accepted

Are all powers $g^m$ in the Clifford hierarchy if $g$ is?

TL;DR: Clifford hierarchy is not closed under raising to integer powers. One suitable counterexample is $g:=TH$ which resides in the third level $\mathcal{C}^{(3)}$ of the Clifford hierarchy, but ...
Adam Zalcman's user avatar
  • 22.4k
3 votes
Accepted

Inverses and the Clifford Hierarchy

This partial answer breaks the question of the closure of the levels of the Clifford hierarchy under inversion into two parts: the easy question of closure under complex conjugation and the harder ...
Adam Zalcman's user avatar
  • 22.4k
2 votes
Accepted

The Clifford hierarchy and $ e^{2 \pi i/2^k} $

The answer is: Yes (assuming the generalized semi-Clifford conjecture is true) Conjecture 2 of https://arxiv.org/abs/0712.2084 is that for any number of qubits $ n $ all elements of all levels $ k $ ...
Ian Gershon Teixeira's user avatar
2 votes
Accepted

Diagonal gates in qubit Clifford hierarchy are generated by $ C^i Z^{1/2^j} $

First note that any diagonal gate on qubits can be written as some product of $U=\exp (i\theta_j \vec{Z}_j)$ where $\vec{Z}_j$ is any qubit Pauli $Z$ string. In Diagonal gates in the Clifford ...
Jonas Anderson's user avatar
1 vote

Universal Gate Set, Magic States, and costliness of the T gate

To shorten Craig's answer, T is a single qubit gate, diagonal in the Z basis, and still a relatively simple, easy-to-understand rotation. H for example is not a rotation. For your last question - the ...
Yaron Jarach's user avatar
1 vote
Accepted

Is every diagonal gate whose non-zero entries are $2^k$th roots of unity in the two qubit Clifford hierarchy?

TL;DR: Yes, every $4\times 4$ diagonal gate whose non-zero entries are $2^k$th roots of unity are in the $(k+1)$th level of the two-qubit Clifford hierarchy. This is a consequence of the fact that $Z$ ...
Adam Zalcman's user avatar
  • 22.4k
1 vote
Accepted

Which monomial matrices are in the Clifford hierarchy?

$ \mathcal{C}^{(1)} $ is the Pauli group and all elements of the Pauli group are monomial matrices. Thus the monomial matrices in the first level of the Clifford hierarchy are exactly all the Pauli ...
Ian Gershon Teixeira's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible