2019/12/05 by Marc Grau Davis, Marc Davis, Davis, Marc Grau +10 · 4 citations
Computer Science · Physics and Astronomy · #Emerging Technologies (cs.ET) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #cs.ET #quant-ph
paper · pdf · doi:10.48550/arxiv.1912.02727
Presented at the 3rd International Workshop on Quantum Compilation as part of the International Conference On Computer Aided Design 2019
arxiv created 2019/12/05 · openalex publication_date 2019/12/05 · arxiv updated 2019/12/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present an algorithm for compiling arbitrary unitaries into a sequence of gates native to a quantum processor. As accurate CNOT gates are hard for the foreseeable Noisy- Intermediate-Scale Quantum devices era, our A* inspired algorithm attempts to minimize their count, while accounting for connectivity. We discuss the search strategy together with metrics to expand the solution frontier. For a workload of circuits with complexity appropriate for the NISQ era, we produce solutions well within the best upper bounds published in literature and match or exceed hand tuned implementations, as well as other existing synthesis alternatives. In particular, when comparing against state-of-the-art available synthesis packages we show 2.4x average (up to 5.3x) reduction in CNOT count. We also show how to re-target the algorithm for a different chip topology and native gate set, while obtaining similar quality results. We believe that empirical tools like ours can facilitate algorithmic exploration, gate set discovery for quantum processor designers, as well as providing useful optimization blocks within the quantum compilation tool-chain.