PermRowCol Algorithm

The PermRowCol algorithm was introduced by van der Griend and Li in 2022 [1]. It is an extension of RowCol [2] that may further reduce CNOT counts by allowing dynamic qubit allocation.

Inputs

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

Intermediate representation

• Parity matrix

Outputs

• CNOT circuit respecting the connectivity graph
• New mapping from logical to physical qubits

Example

In PermRowCol a parity matrix is reduced to a permutation matrix via connectivity-constrained CNOT gates. The main difference compared to RowCol [2] is that qubits do not necessarily stay in place, but instead can be dynamically allocated to different spots (like in a SWAP operation).

For example, consider the following parity matrix:

and a linear connectivity graph G = (0) - (1) - (2).

With a fixed qubit mapping we would need several CNOT operations to obtain the identity matrix, whereas with dynamic qubit mapping we can simply perform \text{CNOT}_{1, 0} while remembering that qubits 1 and 2 are now exchanged:

The resulting permutation matrix is permuting the qubits according to (0, 2, 1). PermRowCol by itself often yields worse CNOT counts than RowCol, but may yield significantly better performance when additionally utilizing reverse traversal, see benchmarks.

Typical usage

PermRowCol can be useful whenever dynamic qubit allocation is permitted. It typically performs well in conjunction with reverse traversal (RT) assuming that enough classical compilation resources are available for RT. For example, this is the case in contexts where circuits are sliced into smaller sub-circuits with efficient intermediate representations, such as slice-and-build protocols.

References

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

[2] "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

[3] "Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices", Gushu Li, Yufei Ding, Yuan Xie, 1809.02573, 2018