On Optimal Subarchitectures for Quantum Circuit Mapping
Compiling a high-level quantum circuit down to a low-level description that
can be executed on state-of-the-art quantum computers is a crucial part of the
software stack for quantum computing. One step in compiling a quantum circuit
to some device is quantum circuit mapping, where the circuit is transformed
such that it complies with the architecture's limited qubit connectivity.
Because the search space in quantum circuit mapping grows exponentially in the
number of qubits, it is desirable to consider as few of the device's physical
qubits as possible in the process. Previous work conjectured that it suffices
to consider only subarchitectures of a quantum computer composed of as many
qubits as used in the circuit. In this work, we refute this conjecture and
establish criteria for judging whether considering larger parts of the
architecture might yield better solutions to the mapping problem. We show that
determining subarchitectures that are of minimal size, i.e., of which no
physical qubit can be removed without losing the optimal mapping solution for
some quantum circuit, is a very hard problem. Based on a relaxation of the
criteria for optimality, we introduce a relaxed consideration that still
maintains optimality for practically relevant quantum circuits. Eventually,
this results in two methods for computing near-optimal sets of
subarchitectures$\unicode{x2014}$providing the basis for efficient quantum
circuit mapping solutions. We demonstrate the benefits of this novel method for
state-of-the-art quantum computers by IBM, Google and Rigetti.
Tom Peham Lukas Burgholzer Robert Wille