  Layout synthesis, an important step in quantum computing, processes quantum
circuits to satisfy device layout constraints. In this paper, we construct
QUEKO benchmarks for this problem, which have known optimal depths and gate
counts. We use QUEKO to evaluate the optimality of current layout synthesis
tools, including Cirq from Google, Qiskit from IBM,
$\mathsf{t}|\mathsf{ket}\rangle$ from Cambridge Quantum Computing, and recent
academic work. To our surprise, despite over a decade of research and
development by academia and industry on compilation and synthesis for quantum
circuits, we are still able to demonstrate large optimality gaps: 1.5-12x on
average on a smaller device and 5-45x on average on a larger device. This
suggests substantial room for improvement of the efficiency of quantum computer
by better layout synthesis tools. Finally, we also prove the NP-completeness of
the layout synthesis problem for quantum computing. We have made the QUEKO
benchmarks open-source.
