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
13 votes
Accepted

Why are non-Clifford gates more complex than Clifford gates?

Yes, you are correct. Non-Clifford gates cannot be transversely implemented, instead implementation generally requires distilling magic states or Toffoli states. In practice this requires ...
Jonathan Trousdale's user avatar
12 votes

Clifford gates are transversal What exactly does this transversal mean? What is the difference between non-Clifford gates and Clifford gates?

Transversal and Clifford are not as closely linked as your question would seem to imply. Transversal gates are those for which an error-correcting code can achieve the transformation on a logical ...
DaftWullie's user avatar
  • 58.1k
11 votes
Accepted

Is the Clifford group finite?

Sometimes, there is a bit of confusion around the Clifford group in the field ... and it's a matter of definition. A lot of people define the Clifford group $\mathrm{Cl}_n(p)$ of $n$ qudits of prime ...
Markus Heinrich's user avatar
10 votes

How do I check if a gate represented by Unitary $U$ is a Clifford Gate?

Here's a simple strategy based on the idea that Clifford operations conjugate Pauli products into other Pauli products. If $U$ is a Clifford operation, then $U P U^\dagger$ (where $P$ is a Pauli ...
Craig Gidney's user avatar
  • 37.1k
10 votes
Accepted

How can one argue that the $S$-gate is Clifford while $T$-gate is not?

By definition, conjugation by a Clifford gate preserves the Pauli group $G = \langle X, Y, Z\rangle$. It is easy to check that $SXS^\dagger = Y, SYS^\dagger = -X$ and $SZS^\dagger = Z$. Since $G = \...
Adam Zalcman's user avatar
  • 22.3k
9 votes

How can one argue that the $S$-gate is Clifford while $T$-gate is not?

Geometrically: For a single qubit, we have the Bloch sphere and the stabiliser states span an octahedron inside it. Unitaries act in the adjoint representation as $SO(3)$, i.e. they induce rotations ...
Markus Heinrich's user avatar
9 votes
Accepted

Are almost-Clifford circuits almost easy to simulate?

Short answer: Yes, this should be possible. However, the details have to be filled out. The key is to relate this to magic monotones. There has been some development since the 2016 Bravyi-Gosset paper....
Markus Heinrich's user avatar
9 votes
Accepted

How do I check if a gate represented by Unitary $U$ is a Clifford Gate?

Following Dehaene and de Moor (Theorem 6 in particular), every Clifford unitary can be represented (up to a global scalar factor) by an expression of the form $$ U = 2^{-k/2} \!\!\!\!\!\!\sum_{\...
Niel de Beaudrap's user avatar
9 votes
Accepted

Prove that adding any non Clifford gate to the Clifford group yields a universal gate set

There is at least one other way to prove this I'm aware of. The argument uses the concept of a unitary 2-design and how this restricts the representation theory of a group. To avoid pathological cases,...
Markus Heinrich's user avatar
9 votes
Accepted

Is the Clifford group a semidirect product?

$ \newcommand{\F}{\mathbb{F}} \newcommand{\C}{\mathbb{C}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Sp}{\mathrm{Sp}} \newcommand{\Cl}{\mathrm{Cl}} \newcommand{\P}{\mathcal{P}} $Here's the short version:...
Markus Heinrich's user avatar
8 votes
Accepted

How do I create an inverse identity gate?

As a general rule, you wouldn't bother constructing this: it is just a global phase that has no observable consequence. If you really insist on doing this, introduce an ancilla qubit in the $|1\rangle$...
DaftWullie's user avatar
  • 58.1k
8 votes
Accepted

Is the SWAP gate a Clifford Gate? How would I express it using the Clifford Gate generators?

It's well known that you can make a swap out of three CNOTs. For reference, Stim's gate documentation includes H+S+CX decompositions of a lot of Clifford gates including the swap: ...
Craig Gidney's user avatar
  • 37.1k
8 votes

What are the relations between the permutation group and the Clifford group?

I guess you're talking about unitaries which preserve computational basis states, i.e. which act as $U|x\rangle = |f(x)\rangle$ where $f:\,\mathbb F_2^n \rightarrow \mathbb F_2^n$ is a reversible ...
Markus Heinrich's user avatar
8 votes
Accepted

Is every Clifford gate conjugate to a diagonal Clifford gate?

No, $D$ isn't guaranteed to be Clifford. That would require all entries on the diagonal to differ by multiples of 90 degrees (all be 1, $i$, $-i$, or -1 up to global phase). But that would imply $D$ ...
Craig Gidney's user avatar
  • 37.1k
7 votes
Accepted

Definition of the Pauli group and the Clifford group

Note that the second definition actually doesn't make more sense in the context of the stabiliser formalism, as neither of $\pm i Y$ have a +1 eigenspace. That means that you can only describe states ...
Niel de Beaudrap's user avatar
7 votes
Accepted

What is the set of generators for the qutrit Clifford group?

From the paper Normal form for single-qutrit Clifford+T operators and synthesis of single-qutrit gates, the Clifford group in $p>2$ dimensions acting on a sigle qudit is generated by $S$ and $H$ ...
epelaez's user avatar
  • 2,875
7 votes
Accepted

Why do we care about the number of $T$ gates in a quantum circuit?

If you are trying to implement a fault-tolerant quantum computation, you need to implement unitary gates that act on logical qubits. You typically have a finite set of these gates available, and what ...
DaftWullie's user avatar
  • 58.1k
7 votes
Accepted

Does conjugation by a Clifford send each non-identity Pauli to every other non-identity Pauli with equal frequency?

Conjugating a non-identity Pauli operator $P$ by Clifford operators yields all non-identity Pauli operators, including $P$, with equal frequency. Proof Let $G_n$ and $C_n$ denote the $n$-qubit Pauli ...
Adam Zalcman's user avatar
  • 22.3k
7 votes
Accepted

In the Clifford group, is the center of $ \overline{\text{Cl}_n} \equiv\text{Cl}_n/U(1)$ trivial?

Yes, the center of $\overline{\text{Cl}_n}$ is trivial. Summary The proof consists of two parts. First, we establish that if $[U]\in Z(\overline{\text{Cl}_n})$ is an element of the center then $U$ is ...
Adam Zalcman's user avatar
  • 22.3k
6 votes

Definition of the Pauli group and the Clifford group

The difference in definitions is from either taking the unitary group or the projective unitary group. That accounts for the constant prefactors of $\pm i$ that are missing. In lieu of a tikz ...
AHusain's user avatar
  • 3,633
6 votes

How is a Toffoli gate built without using T gates?

The $T$ gate as well as all possible single qubit rotations are non-entangling operations. That means if we have a circuit composed of single bit rotations, any non-entangled $n$-bit input, it will ...
Bertrand Einstein IV's user avatar
6 votes
Accepted

Proof for Cardinality of the Clifford Group

What the author wrote is completely correct, they did not make a mistake. The subgroup of Cliffords fixing $X_n$ and $Z_n$ is indeed isomorphic to $C_{n-1}$ as a group, this is simply because this ...
Markus Heinrich's user avatar
6 votes
Accepted

Getting non-Clifford after performing several Clifford gates in qiskit

The matrix $$ M = \frac{1}{\sqrt{2}}\begin{bmatrix}-i & 1\\-1 & i\end{bmatrix} $$ resembles $$ X/2 = \frac{1}{\sqrt{2}}\begin{bmatrix}1 & -i\\-i & 1\end{bmatrix}\tag1 $$ where we ...
Adam Zalcman's user avatar
  • 22.3k
6 votes
Accepted

Review paper on depth, qubits and $T$ gates number on Clifford+T decomposition for various "typical" algorithms

Copying over from "Are circuits with more than 1000 gates common?". Note that a Toffoli gate is roughly as expensive as 2T gates or 4T gates, depending on your architecture. According to ...
Craig Gidney's user avatar
  • 37.1k
6 votes
Accepted

What is the fastest classical simulator for quantum circuits with only Clifford gates?

As far as I know, the current fastest simulator for stabilizer circuits is my simulator Stim (source code on github, paper in Quantum, python package on pypi). This is especially true if you're doing ...
Craig Gidney's user avatar
  • 37.1k
6 votes

Finite subgroup of $U(4)$ containing a non-Clifford gate and all local Cliffords

This partial answer places additional restrictions on $U$. Constructing unitaries with infinite order By KAK decomposition, $U$ can be written as $$ U=(A_1\otimes A_0)e^{i\alpha X\otimes X + i\beta Y\...
Adam Zalcman's user avatar
  • 22.3k
6 votes
Accepted

Finite subgroup of $U(4)$ containing a non-Clifford gate and all local Cliffords

No. There is no way to add a non Clifford gate to the local Clifford group $ Cl_1^{\otimes 2} $ and get a finite group. Definitions: A subgroup $ G $ of $ GL_n(\mathbb{C}) $ is reducible if we can ...
Ian Gershon Teixeira'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

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