Pauli Frame Tracking

Clifford Hierarchy

Pauli frame tracking exploits the mathematical relationships between quantum gates defined by the Clifford hierarchy.

The lowest level of the hierarchy is the Pauli group: They are members of the set C_1 \in \{I, X, Y, Z\}.

Next is the Clifford group C_2 = {U: UPU^{\dagger} \in C_1 \forall P \in C_1 }, which maps Pauli group members to Pauli group members under conjugation. Examples of members in C_2 include H, S, CNOT, CY, CZ, and SWAP gates. In particular, observe that HXH^{\dagger} = Z \rightarrow HX = ZH.

Above that level is the non-Clifford group C_3 = \{U: UPU^{\dagger} \in C_2 \forall P \in C_1 \}. Members of C_3 include T, \mathrm{Toffoli}, and CCZ.

This hierarchy extends to the k^{\text{th}} level: C_k = \{U: UPU^{\dagger} \in C_{k-1} \forall P \in C_1 \}.

Suppose that the initial state of a single qubit is |\psi\rangle. After applying an X gate, the state is X|\psi\rangle. After applying a Hadamard gate, the state is HX|\psi\rangle = ZH|\psi\rangle = Z|\psi_2\rangle, ignoring any global phase. As illustrated in the Overview tab, this conjugation allows us to stay within the Pauli frame. The H gate may be physically executed, while the new Pauli record is updated to be Z instead of X. |\psi_2\rangle represents the updated state in the new Pauli frame. For software that performs Pauli frame tracking, this can be succinctly written as swapping the X and the Z bits, i.e.,

(0, 0) -> (0, 0)  # I -> I
(1, 0) -> (0, 1)  # X -> Z
(0, 1) -> (1, 0)  # Z -> X
(1, 1) -> (1, 1)  # XZ -> XZ

Indeed, this argument can be applied inductively for any number of Clifford gates applied sequentially. It is clear that a state can always be kept in the Pauli frame. Consequently, for error correction schemes that apply Pauli corrections, no correction gate ever needs to be applied. This allows the quantum program to proceed without waiting for measurement and decoding to finish.

Non-Clifford gates, however do not generally experience this advantage because non-Clifford gates do not generally map to Pauli gates under conjugation. That is why you must flush the Pauli record before applying the non-Clifford gate, as described in the Overview tab. For completeness, note that a T gate maps back to a Z gate i.e., TZT^\dagger = Z.

Why don’t you need a very long classical record for each qubit?

To avoid storing the entire history of gates applied to each qubit, a classical computer leverages Pauli gate relationships. When a Pauli record contains some gate, P, and parses the next Pauli gate to be implemented, the product of the two gates is transformed into the equivalent gate in the set \{I, X, Z, XZ\}, neglecting the global phase. For example, if P = X and the gate to be implemented is Y, then Z is stored because YX = -iZ. The global phase does not need to be stored because it cannot be measured. Therefore, only 2 classical bits are necessary to store a Pauli record, but there is additional classical overhead to track how the Pauli frame changes as gates are applied.