Search Space Reduction for Efficient Quantum Compilation

Quantum computers have demonstrated exponential speedup for certain computational tasks like integer factorization, molecular simulation, and machine learning, compared to the classical computers. One of the most challenging problems in quantum computing is quantum compilation, which involves the translation of a quantum circuit into a representation that adheres to the constraints imposed by the quantum hardware. However, this process of mapping the logical qubits to physical qubits incurs a significantly large search space, which needs to be analyzed to obtain the optimal mapping. A non-optimal mapping or compilation strategy introduces additional hardware overhead, thereby rendering inefficiency. Recently, researchers have proposed a technique to reduce the search space for efficient quantum compilation. However, this approach focuses on a generic solution involving only the physical architecture, and hence, as shown in our paper, often fails to incorporate the optimal solution in the reduced search space. To this end, we propose PERM and SGO (PAS), which, to the best of our knowledge, is the first quantum compilation strategy that facilitates a reduced search space comprising a more optimal solution in terms of additional CNOT gates compared to the existing technique. Our experimental evaluation using the MQT benchmarks demonstrates the efficacy of our approach, which furnishes up to 428x reduction compared to the unoptimized search space, and 57.1x reduction compared to existing research, while providing savings in terms of additional CNOT gates by up to 53.85%.