  Recent years have witnessed the fast development of quantum computing.
Researchers around the world are eager to run larger and larger quantum
algorithms that promise speedups impossible to any classical algorithm.
However, the available quantum computers are still volatile and error-prone.
Thus, layout synthesis, which transforms quantum programs to meet these
hardware limitations, is a crucial step in the realization of quantum
computing. In this paper, we present two synthesizers, one optimal and one
approximate but nearly optimal. Although a few optimal approaches to this
problem have been published, our optimal synthesizer explores a larger solution
space, thus is optimal in a stronger sense. In addition, it reduces time and
space complexity exponentially compared to some leading optimal approaches. The
key to this success is a more efficient spacetime-based variable encoding of
the layout synthesis problem as a mathematical programming problem. By slightly
changing our formulation, we arrive at an approximate synthesizer that is even
more efficient and outperforms some leading heuristic approaches, in terms of
additional gate cost, by up to 100%, and also fidelity by up to 10x on a
comprehensive set of benchmark programs and architectures. For a specific
family of quantum programs named QAOA, which is deemed to be a promising
application for near-term quantum computers, we further adjust the approximate
synthesizer by taking commutation into consideration, achieving up to 75%
reduction in depth and up to 65% reduction in additional cost compared to the
tool used in a leading QAOA study.
