On the Complexity of Quantum Circuit Compilation
Adi Botea, Akihiro Kishimoto, Radu Marinescu
2021Proceedings of the International Symposium on Combinatorial Search86 citationsDOIOpen Access PDF
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.
Topics & Concepts
Computer scienceQuantumFocus (optics)Computational complexity theoryCircuit complexityField (mathematics)Constraint (computer-aided design)Theoretical computer scienceRelevance (law)Quantum circuitQuantum computerAlgorithmMathematicsQuantum networkElectronic circuitPhysicsPure mathematicsQuantum mechanicsPolitical scienceGeometryOpticsLawQuantum Computing Algorithms and ArchitectureComputability, Logic, AI AlgorithmsComplexity and Algorithms in Graphs