Parity Matrix Intermediate Representation

The parity matrix is an intermediate representation to efficiently describe the action of CNOT circuits. They are utilized in CNOT routing algorithms like, e.g., RowCol.

Inputs

• CNOT circuit with n qubits

Outputs

• n \times n binary matrix P with P_{ij} \in \{0, 1\}

Example

Consider the following CNOT circuit,

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

and its corresponding parity matrix

The rows correspond to the input qubits and tell us how they are transformed. E.g., the first row tells us that qubit x_0 is transformed to x_0 \oplus x_3.

Very easy-to-read examples are SWAP circuits that just permute qubits, as the corresponding parity matrix is a permutation matrix.

x_0: ─╭SWAP─────────────┤  x_1
x_1: ─╰SWAP─╭SWAP───────┤  x_2
x_2: ───────╰SWAP─╭SWAP─┤  x_3
x_3: ─────────────╰SWAP─┤  x_0

Another typical example is a CNOT ladder, which continuously adds parities to lower qubits.

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

Typical usage

Parity matrices are utilized in CNOT routing algorithms like RowCol.

References

[1] "CNOT circuit extraction for topologically-constrained quantum memories", Aleks Kissinger, Arianne Meijer-van de Griend, arXiv:1904.00633, 2019

[2] "Quantum circuit optimizations for NISQ architectures", Beatrice Nash, Vlad Gheorghiu, Michele Mosca, arXiv:1904.01972, 2019

[3] "Optimization of CNOT circuits on limited connectivity architecture", Bujiao Wu, Xiaoyu He, Shuai Yang, Lifu Shou, Guojing Tian, Jialin Zhang, Xiaoming Sun, arXiv:1910.14478, 2019

[4] "Dynamic Qubit Routing with CNOT Circuit Synthesis for Quantum Compilation", Arianne Meijer-van de Griend, Sarah Meng Li, arXiv:2205.00724, 2022

[5] "Global Synthesis of CNOT Circuits with Holes", Ewan Murphy, Aleks Kissinger, arXiv:2308.16496, 2023