PermRowCol Algorithm

Preliminaries

We briefly review two core concepts necessary to understand the PermRowCol algorithm: the parity matrix intermediate representation and the RowCol algorithm. For more details we refer to the linked pages.

Parity matrix

The parity matrix describes the action of a CNOT circuit. The action of a CNOT gate on a computational basis state |x_0 x_1\rangle with x_i \in \{0, 1\} is:

In circuit form, this is the following:

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

The corresponding parity matrix P is:

In particular, a computational basis input state \boldsymbol{x} = (x_0, x_1) is mapped to the (row) vector-matrix product P \boldsymbol{x}.

One way to interpret this is to say that \text{CNOT}_{x_\text{control} x_\text{target}} corresponds to adding the row of the control qubit to the row of the target qubit in the parity matrix. We will sometimes use the shorthand notation x_\text{control} \rightarrow x_\text{target} for that.

We can then describe a whole CNOT circuit with this logic by means of its action on arbitrary computational basis states |x_0 x_1 .. x_{n-1}\rangle. Take, for example, the following circuit.

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

The corresponding parity matrix is given by:

The rows of the parity matrix show how the input bits are transformed. In particular, we can read out x_0 \mapsto x_1 and x_1 \mapsto x_0 \oplus x_1, etc. from the parity matrix directly.

This is the example from Fig. 3 in [1]. Note that the parity matrix in the reference is transposed, following our convention for the parity matrix, such that \boldsymbol{x}' = P \boldsymbol{x}.

RowCol algorithm

The RowCol algorithm synthesizes a CNOT circuit, given a parity matrix IR of the circuit and a connectivity graph G. For example, consider the parity matrix P from above and the simple connectivity graph:

(0) - (1) - (2) - (3)

The algorithm works by eliminating each vertex of the graph. An arbitrary non-cut vertex is eliminated by turning the row and column into elementary basis vectors. Let us consider the non-cut vertex (0) to be eliminated:

Eliminations are done using only CNOT gates that are allowed by the connectivity graph. In order to perform optimal deletions with no redundancy, so-called Steiner trees are utilized that yield a minimal sub-tree of G that encompasses all required qubits to delete the row/column. The details are described in an extensive example in the details section of the RowCol algorithm page.

This step is repeated for every vertex in the connectivity graph until the identity matrix is obtained. All CNOT operations along the way are recorded, and their reverse-ordered circuit is the result that implements the parity matrix.

PermRowCol algorithm

The RowCol algorithm enforces a fixed mapping between logical and physical qubits. This is because the synthesis targets the identity matrix. There are cases where we can save resources by loosening this requirement and allowing for a new qubit allocation. This is essentially what PermRowCol does: instead of targeting the identity matrix, we target a permutation matrix, therefore leading to a new logical qubit allocation. The resulting permutation matrix informs this allocation. For example, if the resulting permutation matrix is:

which corresponds to permuting the second and fourth qubit.

The algorithm works analogously to RowCol with the main difference that instead of eliminating the row and column with the same index, we eliminate some row i and another column j in one step, resulting in a permutation matrix instead. It is not clear, a priori, which permutation matrix is best to target. The authors propose a heuristic based on picking the row and respective column with the lowest Hamming weight (counting the number of 1s) to be eliminated.

Reverse Traversal

The results of PermRowCol can be significantly reduced when utilizing reverse traversal [3]. That is, after finishing one round of PermRowCol with some resulting permutation matrix, the process is restarted but with the inverse (=reverse) circuit and the former output permutation matrix as the input qubit allocation. This way, potentially better CNOT routings can be found, which is also seen in practice, see benchmarks. It may be worth noting that in many cases vanilla PermRowCol, in particular, without reverse traversal, performs worse than RowCol.