  A physical limitation in quantum circuit design is the fact that gates in a
quantum system can only act on qubits that are physically adjacent in the
architecture. To overcome this problem, SWAP gates need to be inserted to make
the circuit physically realizable. The nearest neighbour compliance problem
(NNCP) asks for an optimal embedding of qubits in a given architecture such
that the total number of SWAP gates to be inserted is minimized. In this paper
we study the NNCP on general quantum architectures. Building upon an existing
linear programming formulation, we show how the model can be reduced by
exploiting the symmetries of the graph underlying the formulation. The
resulting model is equivalent to a generalized network flow problem and follows
from an in-depth analysis of the automorphism group of specific Cayley graphs.
As a byproduct of our approach, we show that the NNCP is polynomial time
solvable for several classes of symmetric quantum architectures. Numerical
tests on various architectures indicate that the reduction in the number of
variables and constraints is on average at least 90%. In particular, NNCP
instances on the star architecture can be solved for quantum circuits up to 100
qubits and more than 1000 quantum gates within a very short computation time.
These results are far beyond the computational capacity when solving the
instances without the exploitation of symmetries.
