AAAI Publications, Eleventh Annual Symposium on Combinatorial Search

Font Size: 
On the Complexity of Quantum Circuit Compilation
Adi Botea, Akihiro Kishimoto, Radu Marinescu

Last modified: 2018-07-02


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.

Full Text: PDF