Clifford gates and non-Clifford gates

Introduction

Quantum computing has attracted significant attention for its potential to solve certain computational problems exponentially faster than classical computers. While concepts such as superposition and entanglement are often highlighted as key features, there is a deeper mathematical structure that explains what makes quantum computation so powerful: the use of operations that go beyond what can be efficiently simulated classically.

One of the critical distinctions in quantum computing is between operations that belong to the Clifford group—which can be efficiently simulated classically—and those that do not, such as Toffoli and T-gates¹. These non-Clifford gates are necessary for quantum speedup, as seen in algorithms like Grover’s search and Shor’s factoring algorithm.

In this document, we explore the Clifford group, its algebraic structure, and its importance in quantum computing. We will then highlight how non-Clifford gates play a critical role in providing the quantum advantage in algorithms like Grover’s and Shor’s.

Definition of the Clifford Group

The Clifford group is the set of quantum gates that, when conjugated with elements of the Pauli group, map Pauli operators to other Pauli operators (possibly up to a global phase). This makes the Clifford group the normalizer of the Pauli group in the unitary group.

The Pauli Group

The Pauli group on a single qubit is generated by the Pauli matrices \(X\), \(Y\), \(Z\), and the identity \(I\), along with global phases \(\{ \pm 1, \pm i \}\). The elements of the Pauli group are tensor products of these single-qubit matrices with the possible global phases mentioned above.

The Pauli matrices are defined as: \(\begin{aligned} X &= \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \\ Y &= \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, \\ Z &= \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}, \\ I &= \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}. \end{aligned}\)

Definition of the Clifford Group

A quantum gate \(U\) belongs to the Clifford group if it conjugates any Pauli operator (an element of the Pauli group) into another Pauli operator (up to a phase). That is, for any Pauli operator \(P\):

\[U P U^\dagger = P',\]

where \(P'\) is another Pauli operator (which may or may not be the same as \(P\)).

This property is key to understanding why Clifford circuits, made up of gates from the Clifford group, can be efficiently simulated on classical computers, as their action on stabilizer states (which are eigenstates of Pauli operators) remains well-structured.

This property of preserving the Pauli group under conjugation makes Clifford gates particularly useful in quantum error correction and stabilizer codes, where maintaining the Pauli structure is crucial for tracking errors and maintaining fault tolerance.

The Clifford group includes common quantum gates such as:

• Hadamard gate \(H\)
• CNOT gate (Controlled-NOT)
• Phase gate \(S\)

These gates transform Pauli operators while preserving the Pauli structure, making them classically simulatable. In fact, the set consisting of the Hadamard gate \(H\), phase gate \(S\), and \(\text{CNOT}\) gate is a generating set for the Clifford group. However, the Clifford group alone is not sufficient for universal quantum computation, as it only generates a proper subgroup of the unitary group. By including any non-Clifford gate in the set, universal quantum computation can be achieved.

Examples of Clifford Gates

Now, let’s see how these gates preserve the Pauli group.

Hadamard Gate

The Hadamard gate \(H\) is defined as:

\[H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}.\]

When conjugated with the Pauli operators, we observe the following:

\[H X H^\dagger = Z, \quad H Z H^\dagger = X, \quad H Y H^\dagger = -Y.\]

Thus, the Hadamard gate transforms \(X\) into \(Z\), and vice versa, while preserving the overall Pauli structure.

CNOT Gate

The CNOT gate acts on two qubits and is defined by:

\[\text{CNOT} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}.\]

Conjugating Pauli operators under the \(\text{CNOT}\) gate results in:

\[\text{CNOT}(X \otimes I)\text{CNOT}^\dagger = X \otimes X, \quad \text{CNOT}(I \otimes X)\text{CNOT}^\dagger = I \otimes X,\] \[\text{CNOT}(Z \otimes I)\text{CNOT}^\dagger = Z \otimes I, \quad \text{CNOT}(I \otimes Z)\text{CNOT}^\dagger = Z \otimes Z.\]

This shows that the \(\text{CNOT}\) gate preserves the structure of the Pauli group, making it a Clifford gate.

Phase Gate \(S\)

The Phase gate \(S\) is defined as:

\[S = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix}.\]

It conjugates the Pauli operators as follows:

\[S Z S^\dagger = Z, \quad S X S^\dagger = Y, \quad S Y S^\dagger = -X.\]

Thus, the phase gate also belongs to the Clifford group as it preserves the Pauli group structure.

Non-Clifford Gates and Universal Quantum Computation

While Clifford gates are important for quantum error correction and can be simulated efficiently, they are not sufficient for universal quantum computation. To achieve universal quantum computation, you need to include at least one non-Clifford gate. A common non-Clifford gate is the T-gate, defined as:

\[T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix}.\]

The T-gate applies a phase shift of \(\frac{\pi}{4}\) to the \(\ket{1}\) state. Unlike Clifford gates, the T-gate does not preserve the Pauli group under conjugation. For example:

\[T X T^\dagger \neq \text{Pauli operator}.\]

This lack of Pauli preservation is what makes the T-gate non-Clifford and, more importantly, makes it computationally powerful. Non-Clifford gates introduce additional computational resources that allow quantum circuits to perform tasks that Clifford circuits alone cannot.

Another important non-Clifford gate is the Toffoli gate. The Toffoli gate (controlled-controlled-NOT) is a three-qubit gate that applies a NOT operation to the third qubit only when both of the first two qubits are in the \(\ket{1}\) state. It plays a key role in many quantum algorithms, such as Grover’s algorithm, and is an important gate for classical reversible computation. Although the Toffoli gate is non-Clifford, it can be decomposed into Clifford gates and a sufficient number of T-gates (as we mentioned above).

The introduction of non-Clifford gates, such as the Toffoli or T-gate, increases the complexity of quantum circuits. Once non-Clifford operations are applied, the circuit can no longer be efficiently simulated classically, as the state space grows exponentially. This distinction is what enables quantum algorithms, such as Shor’s and Grover’s, to achieve speedups that surpass classical computation.

Quantum Speedup: The Role of Non-Clifford Gates

As circuits composed solely of Clifford gates can be efficiently simulated on classical computers, non-Clifford gates are essential for achieving quantum speedup. According to the Gottesman-Knill theorem¹, any quantum circuit that consists only of Clifford gates, along with measurements and preparation of stabilizer states, can be simulated efficiently using classical resources. This limits the computational power of Clifford-only circuits, making non-Clifford gates necessary for surpassing classical computation.

Grover’s Algorithm and Non-Clifford Gates

Grover’s search algorithm provides a quadratic speedup over classical search algorithms. The key component is the oracle, which marks the desired solution by flipping the phase of the corresponding state. This is typically implemented using Toffoli gates to construct complex Boolean functions that check the conditions for the solution. The use of Toffoli gates enables efficient evaluation of these Boolean functions, which is essential for the oracle’s operation in identifying the correct state among many possibilities.

Shor’s Algorithm and Non-Clifford Gates

Shor’s algorithm, which factors large integers exponentially faster than classical algorithms, requires non-Clifford gates for its implementation. During the modular exponentiation part of the algorithm, Toffoli gates are employed to construct the controlled modular arithmetic operations. In the quantum phase estimation step, the algorithm utilizes controlled rotation gates, which perform rotations conditioned on the state of another qubit. These gates apply precise phase shifts that are crucial for extracting periodicity information from the modular exponentiation process. Together, these non-Clifford gates play a pivotal role in achieving the necessary computational complexity that leads to the exponential speedup in Shor’s algorithm².

Conclusion

The Clifford group plays an essential role in the structure of quantum circuits, providing gates that preserve the Pauli group and allowing for classical simulability. However, it is the use of non-Clifford gates, such as the Toffoli gate in Grover’s and Shor’s algorithm, that provides the real power of quantum computing by enabling tasks that are quadratically/exponentially faster than their classical counterparts.

Reference

1. Gottesman, D. (1999). The Heisenberg representation of quantum computers ↩︎ ↩︎²

2. Kunihiro, N. (2003). Practical running time of factoring by quantum circuits: http://aqis-conf.org/archives/eqis03/program/posters/P610-Kunihiro.pdf ↩︎