RowCol Algorithm

Overview

The RowCol algorithm was introduced by Wu et al. in 2019 in 1910.14478 [1]. It maps a CNOT circuit to a new CNOT circuit under constrained connectivity. It utilizes the parity matrix intermediate representation of CNOT circuits.

RowCol and variations thereof are typically used in compilation on devices with limited connectivity and also often serves as a subroutine for more involved compilation passes such as those in [5] or [6].

Inputs

• CNOT circuit
• Connectivity graph G(V, E)

Intermediate representation

• Parity matrix

Outputs

• CNOT circuit respecting the connectivity graph of size \mathcal{O}(n^2) in the worst case for n qubits

Context in literature

RowCol allows the construction of CNOT circuits of size 2n^2 in the worst case for any connected graph G. This builds upon and improves earlier results in 1904.00633 [2], which only achieves 2n^2 sizes when there is a Hamiltonian path in the graph. Otherwise, the asymptotic scaling is \mathcal{O}(n^3). It also improves upon 1904.01972 [3], where the circuit sizes are 4n^2.

There are relevant follow-ups and extensions. Notably, Meijer-van de Griend and Li introduced PermRowCol in 2205.00724 [4], which maps the underlying parity matrix to permutation matrices instead of identity matrices. This requires relabeling of qubits but leads to lower CNOT counts.

RowCol is typically applied to subcircuits containing only CNOTs. Murphy and Kissinger in 2308.16496 [5] introduced temporal qubits that allow the application of RowCol and variants thereof to CNOT routing in general circuits without slicing out pure CNOT subcircuits.

Example

Take this example circuit

0: ─╭●──────────╭SWAP─╭SWAP─────────────┤  
1: ─╰X─╭●───────│─────│─────────────────┤  
2: ────╰X─╭●────│─────╰SWAP─╭SWAP───────┤  
3: ───────╰X─╭●─│───────────╰SWAP─╭SWAP─┤  
4: ──────────╰X─╰SWAP─────────────╰SWAP─┤  

and the connectivity graph

(1) - (4) - (5)
       |       
      (3)
       |
      (2)

taken from figure 6 in 1910.14478.

RowCol maps this CNOT circuit to the following new circuit with 10 CNOT gates, respecting the connectivity graph.

0: ──────────╭●────╭X──────────┤  
1: ─╭X───────│─────│─────╭●────┤  
2: ─╰●─╭X────│──╭●─│──╭●─╰X────┤  
3: ────╰●─╭●─╰X─╰X─╰●─╰X─╭●─╭X─┤  
4: ───────╰X─────────────╰X─╰●─┤ 

Typical usage

RowCol and variations thereof are typically used in compilation on devices with limited connectivity.

RowCol is also often used as a subroutine for more involved compilation passes such as [5] or [6].

References

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

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

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

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

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

[6] "Towards a generic compilation approach for quantum circuits through resynthesis", Arianne Meijer-van de Griend, 2304.08814v1, 2023

@misc{PennyLane-RowCol,
  title={RowCol Algorithm},
  howpublished={\url{https://pennylane.ai/compilation/rowcol-algorithm}},
  year={2025}
}