On constructing benchmark quantum circuits with known near-optimal
  transformation cost
Current quantum devices impose strict connectivity constraints on quantum
circuits, making circuit transformation necessary before running logical
circuits on real quantum devices. Many quantum circuit transformation (QCT)
algorithms have been proposed in the past several years. This paper proposes a
novel method for constructing benchmark circuits and uses these benchmark
circuits to evaluate state-of-the-art QCT algorithms, including TKET from
Cambridge Quantum Computing, Qiskit from IBM, and three academic algorithms
SABRE, SAHS, and MCTS. These benchmarks have known near-optimal transformation
costs and thus are called QUEKNO (for quantum examples with known
near-optimality). Compared with QUEKO benchmarks designed by Tan and Cong
(2021), which all have zero optimal transformation costs, QUEKNO benchmarks are
more general and can provide a more faithful evaluation for QCT algorithms
(like TKET) which use subgraph isomorphism to find the initial mapping. Our
evaluation results show that SABRE can generate transformations with
conspicuously low average costs on the 53-qubit IBM Q Rochester and Google's
Sycamore in both gate size and depth objectives.
Sanjiang Li Xiangzhen Zhou Yuan Feng