  In Layout Synthesis, the logical qubits of a quantum circuit are mapped to
the physical qubits of a given quantum hardware platform, taking into account
the connectivity of physical qubits. This involves inserting SWAP gates before
an operation is applied on distant qubits. Optimal Layout Synthesis is crucial
for practical Quantum Computing on current error-prone hardware: Minimizing the
number of SWAP gates directly mitigates the error rates when running quantum
circuits. In recent years, several approaches have been proposed for minimizing
the required SWAP insertions. The proposed exact approaches can only scale to a
small number of qubits. Proving that a number of swap insertions is optimal is
much harder than producing near optimal mappings. In this paper, we provide two
encodings for Optimal Layout Synthesis as a classical planning problem. We use
optimal classical planners to synthesize the optimal layout for a standard set
of benchmarks. Our results show the scalability of our approach compared to
previous leading approaches. We can optimally map circuits with 9 qubits onto a
14 qubit platform, which could not be handled before by exact methods.
