On the Complexity of Quantum Circuit Compilation

Authors

  • Adi Botea IBM Research, Dublin
  • Akihiro Kishimoto IBM Research, Dublin
  • Radu Marinescu IBM Research, Dublin

DOI:

https://doi.org/10.1609/socs.v9i1.18463

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.

Downloads

Published

2021-09-01