Pauli Decomposition

Pauli decomposition is the expression of any $2^n \times 2^n$ matrix as a linear combination of $n$-qubit Pauli strings (tensor products of the single-qubit Pauli matrices $\{I, X, Y, Z\}$). Since the $4^n$ Pauli strings form a complete orthogonal basis for the space of $2^n \times 2^n$ matrices, any operator on $n$ qubits can be uniquely decomposed in this form. This decomposition is fundamental to how quantum computers evaluate Hamiltonians and other observables.

Mathematical formulation

Any operator $A$ on $n$ qubits can be written as:

$A = \sum_{P \in \{I,X,Y,Z\}^{\otimes n}} a_P \cdot P$

where the sum runs over all $4^n$ Pauli strings and the coefficients are:

$a_P = \frac{1}{2^n} \text{Tr}(P \cdot A)$

This follows from the orthogonality of Pauli strings under the trace inner product: $\text{Tr}(P^\dagger Q) = 2^n \delta_{PQ}$.

For a Hermitian operator $A = A^\dagger$, all coefficients $a_P$ are real numbers.

Example: two-qubit Hamiltonian

Consider the Heisenberg interaction Hamiltonian:

$H = J_x X_1 X_2 + J_y Y_1 Y_2 + J_z Z_1 Z_2 + h_1 Z_1 + h_2 Z_2$

This is already in Pauli-decomposed form with five nonzero terms. The Pauli strings are $X \otimes X$, $Y \otimes Y$, $Z \otimes Z$, $Z \otimes I$, and $I \otimes Z$, with coefficients $J_x$, $J_y$, $J_z$, $h_1$, and $h_2$.

For a general $4 \times 4$ matrix on 2 qubits, the decomposition would involve all $4^2 = 16$ Pauli strings: $II$, $IX$, $IY$, $IZ$, $XI$, $XX$, $XY$, $XZ$, $YI$, $YX$, $YY$, $YZ$, $ZI$, $ZX$, $ZY$, $ZZ$.

Role in quantum computing

Measuring expectation values: To compute $\langle\psi|H|\psi\rangle$ on a quantum computer, decompose $H$ into Pauli strings and measure each one separately:

$\langle H \rangle = \sum_P a_P \langle P \rangle$

Each Pauli string $P$ can be measured by applying appropriate single-qubit rotations to diagonalize it, then measuring in the computational basis. Commuting Pauli strings can be measured simultaneously, reducing the number of distinct circuits needed.

Hamiltonian simulation: Trotterization simulates $e^{-iHt}$ by decomposing $H$ into Pauli terms and approximating the evolution as a product of easier-to-implement Pauli rotations:

$e^{-iHt} \approx \prod_P e^{-ia_P P t}$

Each $e^{-ia_P P t}$ can be implemented as a circuit using CNOT gates and single-qubit rotations.

Quantum chemistry: Molecular Hamiltonians, after the Jordan-Wigner or Bravyi-Kitaev transformation from fermionic to qubit operators, are expressed as sums of Pauli strings. A typical molecular Hamiltonian for 20 qubits may have thousands to millions of Pauli terms, and reducing this count through grouping and truncation is an active research area.

Computational considerations

The number of Pauli terms grows as $O(4^n)$ in the worst case, but physical Hamiltonians are typically sparse in the Pauli basis. The measurement cost of estimating $\langle H \rangle$ scales with the number of distinct measurement bases needed, which can be reduced by grouping commuting terms. Advanced techniques like classical shadow tomography can estimate many Pauli expectation values from a fixed number of random measurements.

Why it matters for learners

Pauli decomposition is the interface between physical problems (expressed as Hamiltonians) and quantum hardware (which measures Pauli observables). Understanding this decomposition is essential for working with VQE, Hamiltonian simulation, and quantum chemistry applications. It also clarifies why the number and structure of Pauli terms in a Hamiltonian directly determines the cost of evaluating it on a quantum computer.

See also

• Pauli Gates
• Pauli Group
• Expectation Value
• Variational Quantum Eigensolver
• Jordan-Wigner Transformation