On the Complexity of Quantum Circuit Compilation

TLDR

Quantum circuit compilation (QCC) is an important problem in quantum computing, closely related to combinatorial search with recent approaches using 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.

Abstract

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.