Publication
SoCS 2018
Conference paper

On the complexity of quantum circuit compilation

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.

Date

14 Jul 2018

Publication

SoCS 2018

Authors

Topics

Share