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
P = \begin{pmatrix} 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1\end{pmatrix}.
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
P = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0\end{pmatrix}
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
P = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{pmatrix}
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