1. Compilation/
  2. Parity Matrix Intermediate Representation

Parity Matrix Intermediate Representation

The parity matrix describes a circuit containing only CNOT gates (referred to as a CNOT circuit). This can be motivated by looking at the action of the CNOT gate on a computational basis state x0x1|x_0 x_1\rangle with bits xi{0,1}x_i \in \{0, 1\},

CNOTx0x1x0,x1=x0,x0x1,\text{CNOT}_{x_0 x_1} |x_0, x_1\rangle = |x_0, x_0 \oplus x_1\rangle,

and the corresponding simple circuit it expresses.

x_0: ─╭●─┤  x_0
x_1: ─╰X─┤  x_0 ⊕ x_1

In particular, it flips the target bit whenever the control bit is 1:

+---------+--------+------+
| control | target | CNOT |
+---------+--------+------+
| 0       | 0      | 00   |
| 0       | 1      | 01   |
| 1       | 0      | 11   |
| 1       | 1      | 10   |
+---------+--------+------+

It has the parity matrix

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

where each row represents the qubits appearing in the parity equations of the output states listed above (i.e., the first row is representing x0x_0 and the second row is representing x0x1x_0 \oplus x_1).

Constructing the parity matrix

We can construct the parity matrix of a CNOT circuit by starting from an identity matrix P=IP = \mathbb{I} and adding (modulo 22) the row of a control qubit onto the row of the target qubit for every CNOT gate in the circuit. For example, the parity matrix for the previous example is

(1001)=CNOT01(1011).\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \stackrel{CNOT_{01}}{=} \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}.

Similarly, we can obtain the parity matrix representation for any CNOT circuit. This simple Python code achieves this:

def compute_parity_matrix(circ):
    num_wires = len(circ.wires)
    P = np.eye(num_wires)
    for op in circ.operations:
        control, target = op.wires
        P[target] = P[target] + P[control]

    return P % 2

Let us see this by constructing the following circuit and computing its parity matrix.

x_0: ────╭●───────╭X─╭●─┤  x_0 ⊕ x_3
x_1: ────│──╭X────│──│──┤  x_0 ⊕ x_1 ⊕ x_2 ⊕ x_3
x_2: ─╭X─╰X─╰●─╭X─│──╰X─┤  x_2 ⊕ x_3
x_3: ─╰●───────╰●─╰●────┤  x_3
CNOTs = [(3, 2), (0, 2), (2, 1), (3, 2), (3, 0), (0, 2)]
circ = qml.tape.QuantumScript([qml.CNOT(pair) for pair in CNOTs], [])

compute_parity_matrix(circ)
array([[1., 0., 0., 1.],
       [1., 1., 1., 1.],
       [0., 0., 1., 1.],
       [0., 0., 0., 1.]])

Note that we can read out the logical bit operations of the circuit from the parity matrix, where each 1 in the parity matrix row corresponds to the addition of the respective qubit value. In particular, the first row corresponds to x0x3x_0 \oplus x_3 from the circuit above.

Circuit synthesis via Gauss-Jordan elimination

Given a parity matrix, one can synthesize the corresponding CNOT circuit via a Gauss-Jordan elimination. The idea is to transform the parity matrix PP to the identity matrix via Gauss-Jordan elimination restricted to row additions. We will sometimes write this short-hand as iji \rightarrow j, equivalently for the CNOTij\text{CNOT}_{i j} gate or row addition Rj=Ri+Rj(mod 2)R_j = R_i + R_j (\text{mod}\ 2).

This is more easily understood with an example. Let us take the circuit

x_0: ─╭●─╭●────╭X─┤  x_0 ⊕ (x_2 ⊕ x_0) = x_2
x_1: ─╰X─│──╭X─│──┤  x_1 ⊕ x_0 ⊕ (x_2 ⊕ x_0) = x_1 ⊕ x_2
x_2: ────╰X─╰●─╰●─┤  x_2 ⊕ x_0

and its parity matrix

P=(001011101).P = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix}.

Adding row 2 to row 0 leads to

P=(100011101).P = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix}.

The corresponding gate is CNOT20\text{CNOT}_{2 0}. We perform the next steps in the same fashion and overall obtain the Gauss-Jordan elimination

(001011101)=20(100011101)=21(100110101)=01(100010101)=02(100010001).\begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix} \stackrel{2 \rightarrow 0}{=} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix} \stackrel{2 \rightarrow 1}{=} \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix} \stackrel{0 \rightarrow 1}{=} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix} \stackrel{0 \rightarrow 2}{=} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}.

We can synthesize the circuit from this process by going through it backwards and writing down the corresponding CNOT gates. In particular, we obtain

x_0: ─╭●─╭●────╭X─┤  x_2
x_1: ─│──╰X─╭X─│──┤  x_1 ⊕ x_2
x_2: ─╰X────╰●─╰●─┤  x_2 ⊕ x_0

This is a circuit equivalent to the original input circuit. You can see this by commuting the first two operations. We could have also performed the last two row additions in the opposite order and obtained the exact original circuit.