Parity Table

Korbinian Kottmann

Compilation/
Parity Table

Parity Table

Parity table

A circuit $U$ containing only (CNOT, $R_Z$ ) gates is called a phase polynomial. Such a circuit can be fully described by mapping computational basis states $|\boldsymbol{x}\rangle = |x_1, .., x_n\rangle$ on $n$ qubits with $x_i \in \{0, 1\}$ as

|\boldsymbol{x}\rangle = e^{-i \frac{\boldsymbol{\theta}}{2} \left(1 -2 \cdot P_T \boldsymbol{x}\right)} |P \boldsymbol{x}\rangle.

Let us go through each of the components:

The matrix $P$ is the so-called parity matrix and tracks the logical manipulation of the input vector $|\boldsymbol{x}\rangle$ . For circuits containing only CNOT gates, it is a full description and its own intermediate representation (IR).

When additional phase gates $R_Z(\theta) = e^{-i \frac{\theta}{2} Z}$ are involved, we need to additionally track the accumulated phase of the circuit. This is done in the so-called parity table $P_T$ . First, let us note that the action of a phase gate on a computational basis state is given by

R_Z(\theta) |x\rangle = e^{-i \frac{\theta}{2} (1-2x)} |x \rangle.

A CNOT gate may alter the current state $|\boldsymbol{x}\rangle$ of the circuit, and we call the values of $\boldsymbol{x}$ the current parity at that point in the circuit. Whenever there is a phase gate, we collect the current parity on the qubit the gate is acting on. The collection of those parities is the parity table.

This is best understood by going through a simple example: Let us start with the state $|x_1, x_2\rangle$ and apply a $\text{CNOT}_{1, 2}$ gate,

\text{CNOT}_{1, 2} |x_1, x_2\rangle = |x_1, x_1 \oplus x_2\rangle,

where the action is simply adding the control qubit value to the target qubit value. This is the same in the parity matrix IR.

Now, applying an $R_Z^2(\theta)$ rotation on the second qubit collects its current parity $x_1 \oplus x_2$ ,

R_{Z_2}(\theta) |x_1, x_1 \oplus x_2\rangle = e^{-i \frac{\theta}{2} (1-2(x_1 \oplus x_2))} |x_1, x_1 \oplus x_2\rangle.

Overall, we can describe the action of the circuit $U = (\text{CNOT}_{12}, R_{Z_2}(\theta))$ with

P_T = \begin{pmatrix} 1 & 1 \end{pmatrix}; P = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix},

and, in particular, as the following phase polynomial:

U |x_1, x_2\rangle = e^{-i \frac{\theta}{2} \cdot \left(1 - 2 \begin{pmatrix} 1 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \right)} |\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}\rangle.

We can go through the detailed example on the overview page. We go through each gate by hand and simply note the current parities in the circuit whenever they are altered.

Collecting the phase polynomial description by going through an example circuit and noting the current parities at each point of the circuit. By noting the current parities inside the circuit at each point of a new gate we can directly read out the parity table and parity matrix. Image taken from [1].

In particular, we get the phase factors $\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)$ , corresponding to the parity table

\begin{pmatrix}1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \end{pmatrix},

as well as the parity matrix

\begin{pmatrix}1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix},

which is just the collection of final parities at the end of the circuit.

Why PennyLane

Getting Started

Documentation

Ecosystem

Parity Table

Parity table