Pauli Product Measurement

This compilation pass takes a (Clifford + T) circuit and maps it to a circuit consisting solely of non-Clifford Pauli product rotations and Pauli product measurements (steps 1-3 below). When axuillary magic states are available, this can subsequently be mapped entirely to Pauli product measurements (step 4). The pass can be seen as four separate passes, which we describe as follows:

1. Decomposition of (Clifford + T) into Pauli product rotations (PPRs)
2. Commutation of Clifford PPRs past other PPRs
3. Absorption of Clifford PPRs into terminal measurements
4. Decomposition of non-Clifford PPRs into Pauli product measurements (PPMs) (via magic state injection)

Decomposition of (Clifford + T) into Pauli product rotations (PPRs)

This pass is implemented as catalyst.passes.to_ppr.

A Pauli word, here referred to as a Pauli product, is a tensor product of Pauli matrices

For example, X \otimes I \otimes Y \otimes Z \otimes I \otimes X, or the short-hand notation X_0 Y_2 Z_3 X_5 if we index qubits in ascending order starting from 0.

Clifford + T circuits can be fully described by Pauli product rotations (PPRs)

(note the missing factor of 1/2 compared with qml.PauliRot).

All Clifford + T gates can be decomposed in Pauli rotations with either \frac{\pi}{4} (Clifford) or \frac{\pi}{8} angle (non-Clifford).

We take on the graphical representations from [1] in Figure 5 therein.

(Clifford + T) gates and their PPR representations, taken from Figure 5 in [1]. (Image from Game of Surface Codes by Daniel Litinski, CC BY 4.0)

Note that Pauli rotations have a simple closed form formula

which is just Euler's formula.

Commutation of Clifford PPRs past other PPRs

This pass is implemented as catalyst.passes.commute_ppr.

The goal of this section is to move all Clifford gates to the right-hand side of the circuit and all non-Clifford gates to the left-hand side of the circuit. This is important as it allows techniques like T-parallelization and T-depth reduction.

This is possible due to special commutation relations for PPRs when one of them is Clifford with angle \frac{\pi}{4}. The rules are summarized in Figure 4 in [1], which we reproduce here:

Rewrite rules for PPRs taken from Figure 4 in [1]. Commutation relations for Clifford PPRs with arbitrary PPRs for the two possible cases of the generating Paulis commuting (PP' = P'P) and anti-commuting (PP' = -P'P). (Image from Game of Surface Codes by Daniel Litinski, CC BY 4.0)

A fundamental property of Pauli products P is that they generally either commute or anti-commute. This can be seen by looking at the product of two single-qubit Pauli matrices \sigma^i,

where i= 1, 2, 3 corresponds to X, Y, Z, respectively. The commutator is then simply [\sigma^i, \sigma^j] = 2i \varepsilon_{i j k} \sigma_k and the anti-commutator \{\sigma^i, \sigma^j \} = 2\delta_{ij} \mathbb{I}.

In particular, we always either have [P_i, P_j] = 0 or \{P_i, P_j\} = 0 because the Levi-Civita-symbol \varepsilon_{ijk} is always zero when the Kronecker delta symbol \delta_{ij} is non-zero and vice-versa. We can exploit this property to move all Clifford gates past the non-Clifford gates to the end of the circuit, which is the goal of this section.

Together with Euler's formula we can derive the rules for moving around PPRs. Consider the case where the two generating Pauli products commute, [P, P'] = 0. This implies that

and we can move gates past each other. In the case where P and P' anti-commute (\{P, P'\} = 0), we get

We are not aware of a neat way to derive this, but one can prove it using Euler's formula, P^2=\mathbb{I}, and the fact that \sin(\frac{\pi}{4}) = \cos(\frac{\pi}{4}).

The same tricks can be used to derive the the following rules:

Rewrite rules for PPRs taken from Figure 4 in [1]. Commutation relations for a controlled Clifford Pauli C(P_1, P_2) with arbitrary PPRs for anti-commuting case. (Image from Game of Surface Codes by Daniel Litinski, CC BY 4.0)

Absorption of Clifford PPRs into terminal measurements

This pass is implemented as catalyst.passes.merge_ppr_ppm.

After moving all Clifford gates to the right-hand side of the circuit, we have three parts: non-Clifford gates, Clifford gates, and Z-measurements. We can combine the latter two parts by classically processing all the Clifford PPRs.

First note that PPR followed by a Pauli-Z measurement is just a measurement in a new basis, and a Clifford PPR followed by some other Clifford PPR is yet again another Clifford PPR. There are again two distinct cases for when the Pauli products are commuting or anti-commuting.

Absorption rules for merging a Clifford Pauli rotation and a Pauli measurement (Image from Game of Surface Codes by Daniel Litinski, CC BY 4.0)

When [P, P'] = 0, we trivially have

In particular, the PPR has no effect on the measurement.

For the case of \{P, P'\} = 0, we can use Eq. (7) from above with \phi=-\pi/2, yielding P'_{-\frac{\pi}{2}}= \cos\left(-\frac{\pi}{2}\right) \mathbb{I} - i \sin\left(-\frac{\pi}{2}\right) P' = iP'. Similarly, (iPP')_{-\frac{\pi}{2}} = i(iPP'), and hence,

In a measurement of some arbitrary Pauli product P', this becomes

Decomposition of non-Clifford PPRs into Pauli product measurements (PPMs)

In fault tolerant quantum computing (FTQC), T gates are performed by injecting a so-called magic state |m\rangle = |0\rangle + e^{i \frac{\pi}{4}} |1\rangle. The standard magic state injection works as follows:

|ψ> ─╭●───────S─┤  
|m> ─╰X──┤↗├──║─┤  
          ╚═══╝   

Taking some arbitrary input state |\phi \rangle = a |0\rangle + b |1\rangle, we get the following state after the CNOT gate,

Consequently, by measuring the auxiliary qubit introduced by the magic state |m\rangle, we either get the desired state T|\psi\rangle = a|0\rangle + b e^{i\frac{\pi}{4}}|1\rangle when measuring 0, or \propto S T|\psi\rangle when measuring 1. Depending on the outcome, we perform an additional S gate to correct for the mistake we introduced and overall have an action equivalent to a T gate.

This notion of magic state injection can be extended to non-Clifford Pauli product rotations P_{\frac{\pi}{8}} in the following way.

Magic state injection to perform non-Clifford Pauli product rotation. (Image from Game of Surface Codes by Daniel Litinski, CC BY 4.0)

Conditional Clifford Pauli rotations can be commuted to the back of the circuit, such that we only have Pauli product measurements, provided that magic states are available.