1. Compilation/

  2. Parity Table

Parity Table

Parity table

A circuit UU containing only (CNOT, RZR_Z) gates is called a phase polynomial. Such a circuit can be fully described by mapping computational basis states ∣x⟩=∣x1,..,xn⟩|\boldsymbol{x}\rangle = |x_1, .., x_n\rangle on nn qubits with xi∈{0,1}x_i \in \{0, 1\} as

∣x⟩=e−iθ2(1−2⋅PTx)∣Px⟩.|\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 PP is the so-called parity matrix and tracks the logical manipulation of the input vector ∣x⟩|\boldsymbol{x}\rangle. For circuits containing only CNOT gates, it is a full description and its own intermediate representation (IR).

When additional phase gates RZ(θ)=e−iθ2ZR_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 PTP_T. First, let us note that the action of a phase gate on a computational basis state is given by

RZ(θ)∣x⟩=e−iθ2(1−2x)∣x⟩.R_Z(\theta) |x\rangle = e^{-i \frac{\theta}{2} (1-2x)} |x \rangle.

A CNOT gate may alter the current state ∣x⟩|\boldsymbol{x}\rangle of the circuit, and we call the values of x\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 ∣x1,x2⟩|x_1, x_2\rangle and apply a CNOT1,2\text{CNOT}_{1, 2} gate,

CNOT1,2∣x1,x2⟩=∣x1,x1⊕x2⟩,\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 RZ2(θ)R_Z^2(\theta) rotation on the second qubit collects its current parity x1⊕x2x_1 \oplus x_2,

RZ2(θ)∣x1,x1⊕x2⟩=e−iθ2(1−2(x1⊕x2))∣x1,x1⊕x2⟩.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=(CNOT12,RZ2(θ))U = (\text{CNOT}_{12}, R_{Z_2}(\theta)) with

PT=(11);P=(1011),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∣x1,x2⟩=e−iθ2⋅(1−2(11)(x1x2))∣(1011)(x1x2)⟩.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 θ1(x1⊕x2)\theta_1 (x_1 \oplus x_2), θ2(x1⊕x2⊕x3)\theta_2 (x_1 \oplus x_2 \oplus x_3), and θ3(x1⊕x3⊕x4)\theta_3 (x_1 \oplus x_3 \oplus x_4), corresponding to the parity table

(110011101011),\begin{pmatrix}1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \end{pmatrix},

as well as the parity matrix

(1110101100100001),\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.