  Executing quantum circuits on currently available quantum computers requires
compiling them to a representation that conforms to all restrictions imposed by
the targeted architecture. Due to the limited connectivity of the devices'
physical qubits, an important step in the compilation process is to map the
circuit in such a way that all its gates are executable on the hardware.
Existing solutions delivering optimal solutions to this task are severely
challenged by the exponential complexity of the problem. In this paper, we show
that the search space of the mapping problem can be limited drastically while
still preserving optimality. The proposed strategies are generic,
architecture-independent, and can be adapted to various mapping methodologies.
The findings are backed by both, theoretical considerations and experimental
evaluations. Results confirm that, by limiting the search space, optimal
solutions can be determined for instances that timeouted before or speed-ups of
up to three orders of magnitude can be achieved.
