Dynamic qubit allocation and routing for constrained topologies by CNOT circuit re-synthesis

Many quantum computers have constraints regarding which two-qubit operations are locally allowed.
To run a quantum circuit under those constraints, qubits need to be allocated to different quantum
registers, and multi-qubit gates need to be routed accordingly. Recent developments have shown that
Steiner-tree based compiling strategies provide a competitive tool to route CNOT gates. However,
these algorithms require the qubit allocation to be decided before routing. Moreover, the allocation
is fixed throughout the computation, i.e. the logical qubit will not move to a different qubit register.
This is inefficient with respect to the CNOT count of the resulting circuit.
In this paper, we propose the algorithm PermRowCol for routing CNOTs in a quantum circuit.
It dynamically reallocates logical qubits during the computation, and thus results in fewer output
CNOTs than the algorithms Steiner-Gauss[12] and RowCol[23].
Here we focus on circuits over CNOT only, but this method could be generalized to a routing and
allocation strategy on Clifford+T circuits by slicing the quantum circuit into subcircuits composed of
CNOTs and single-qubit gates. Additionally, PermRowCol can be used in place of Steiner-Gauss in
the synthesis of phase polynomials as well as the extraction of quantum circuits from ZX-diagrams.