Parity Table

The parity table $P_T$ describes the phase factor in the phase polynomial intermediate representation. Technically, the parity table on its own is not an intermediate representation as it further requires the phase angles $\boldsymbol{\alpha}$ and parity matrix $P$ to describe (CNOT, $R_Z$) circuits (phase polynomials),

Sometimes, the phase factor $\frac{\boldsymbol{\alpha}}{2} \left(1 -2 \cdot P_T \boldsymbol{x} \right)$ itself is called the phase polynomial, which adds confusion to the terminology. We refer to phase polynomial intermediate representation for a full overview.

Inputs

• (CNOT, $R_Z$) circuit with $n$ qubits and $m$ $R_Z$ gates

Outputs

• $m \times n$ binary matrix $P_T$ with $(P_T)_{ij} \in \{0, 1\}$

Example

Image taken from [1].

We go through each gate of the circuit and note down its action on the binary input state $|x_1, x_2, x_3, x_3\rangle$. A CNOT gate adds the control value onto the target value. A $R_Z$ gate collects the current parity, which is the logical value of that qubit. E.g. the first CNOT alters the first qubit value to $x_1 \oplus x_2$. The corresponding parity that we collect at the first $R_Z$ gate is $(1, 1, 0, 0)$, as we have $n=4$ qubits in total, and its angle $\theta_1$. We continue doing so throughout the circuit and collect the parities $\theta_1 (x_1 \oplus x_2)$, $\theta_2 (x_1 \oplus x_2 \oplus x_3)$, and $\theta_3 (x_1 \oplus x_3 \oplus x_4)$, which we can summarize in the corresponding parity table

and angle vector $\boldsymbol{\theta} = (\theta_1, \theta_2, \theta_3)$.

The overall accumulated phase of the circuit is given by

Typical usage

Parity tables are utilized in the phase polynomial intermediate representation for (CNOT, $R_Z$) circuits.

References

[1] "Phase polynomials synthesis algorithms for NISQ architectures and beyond", Vivien Vandaele, Simon Martiel, Timothée Goubault de Brugière arXiv:2104.00934, 2021

@misc{PennyLane-ParityTable,
title={Parity Table},
howpublished={\url{https://pennylane.ai/compilation/parity-table}},
year={2025}
}