Architecture aware compilation of quantum circuits via lazy synthesis

Abstract

Qubit routing is a key problematic related to quantum circuit compilation. It consists in rewriting a quantum circuit by adding the least possible number of instructions to make the circuit compliant with some architecture's connectivity constraints. Usually, this problem is tackled via either SWAP insertion techniques or re-synthesis of portions of the circuit using architecture aware synthesis algorithms. In this work, we propose a meta-heuristic that couples the iterative approach of SWAP insertion techniques with greedy architecture aware synthesis routines. We propose two new compilation algorithms based on this meta-heuristic and compare their performances to state-of-the-art quantum circuit compilation techniques for several standard classes of quantum circuits and show significant reduction in the entangling gate overhead due to compilation.

References in corpus (14)

• Quantum Computing in the NISQ era and beyond
• Improved Simulation of Stabilizer Circuits
• Magic State Distillation: Not as Costly as You Think
• Matchgates and classical simulation of quantum circuits
• Quantum circuit optimizations for NISQ architectures
• Hadamard-free circuits expose the structure of the Clifford group
• QIRAL: A High Level Language for Lattice QCD Code Generation
• staq -- A full-stack quantum processing toolkit
• On the qubit routing problem
• On the CNOT-complexity of CNOT-PHASE circuits
• Circuit optimization of Hamiltonian simulation by simultaneous diagonalization of Pauli clusters
• Circuit Transformations for Quantum Architectures
• Computation at a distance
• Optimizing T gates in Clifford+T circuit as $\pi /4$ rotations around Paulis

Cited by in corpus (7)

• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Phase polynomials synthesis algorithms for NISQ architectures and beyond
• SWAP-less Implementation of Quantum Algorithms
• Lower T-count with faster algorithms
• Readout Error Mitigation for Mid-Circuit Measurements and Feedforward
• A graph-state based synthesis framework for Clifford isometries
• Global Synthesis of CNOT Circuits with Holes