- Compilation/
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 with bits ,
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
where each row represents the qubits appearing in the parity equations of the output states listed above (i.e., the first row is representing and the second row is representing ).
Constructing the parity matrix
We can construct the parity matrix of a CNOT circuit by starting from an identity matrix and adding (modulo ) 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
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 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 to the identity matrix via Gauss-Jordan elimination restricted to row additions. We will sometimes write this short-hand as , equivalently for the gate or row addition .
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
Adding row 2
to row 0
leads to
The corresponding gate is . We perform the next steps in the same fashion and overall obtain the Gauss-Jordan elimination
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.