  Many physical implementations of quantum computers impose stringent memory
constraints in which 2-qubit operations can only be performed between qubits
which are nearest neighbours in a lattice or graph structure. Hence, before a
computation can be run on such a device, it must be mapped onto the physical
architecture. That is, logical qubits must be assigned physical locations in
the quantum memory, and the circuit must be replaced by an equivalent one
containing only operations between nearest neighbours. In this paper, we give a
new technique for quantum circuit mapping (a.k.a. routing), based on Gaussian
elimination constrained to certain optimal spanning trees called Steiner trees.
We give a reference implementation of the technique for CNOT circuits and show
that it significantly out-performs general-purpose routines on CNOT circuits.
We then comment on how the technique can be extended straightforwardly to the
synthesis of CNOT+Rz circuits and as a modification to a recently-proposed
circuit simplification/extraction procedure for generic circuits based on the
ZX-calculus.
