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