On the Complexity of Quantum Circuit Compilation

Proceedings of the International Symposium on Combinatorial Search, 11

Volume

Vol. 11 No. 1 (2018): Eleventh Annual Symposium on Combinatorial Search

Short Papers

Quantum circuit compilation (QCC) is an important problem in the emerging field of quantum computing. The problem has a strong relevance to combinatorial search, as solving approaches recently published include constraint programming and temporal planning. In this paper, we focus on a complexity analysis of quantum circuit compilation. We formulate a makespan optimization problem based on QCC, and prove that the problem is NP-complete. To the best of our knowledge, this is the first study on the theoretical complexity of QCC.

10.1609/socs.v9i1.18463