Circuit Transformations for Quantum Architectures

Abstract

Quantum computer architectures impose restrictions on qubit interactions. We propose efficient circuit transformations that modify a given quantum circuit to fit an architecture, allowing for any initial and final mapping of circuit qubits to architecture qubits. To achieve this, we first consider the qubit movement subproblem and use the routing via matchings framework to prove tighter bounds on parallel routing. In practice, we only need to perform partial permutations, so we generalize routing via matchings to that setting. We give new routing procedures for common architecture graphs and for the generalized hierarchical product of graphs, which produces subgraphs of the Cartesian product. Secondly, for serial routing, we consider the token swapping framework and extend a 4-approximation algorithm for general graphs to support partial permutations. We apply these routing procedures to give several circuit transformations, using various heuristic qubit placement subroutines. We implement these transformations in software and compare their performance for large quantum circuits on grid and modular architectures, identifying strategies that work well in practice.

arXiv comment29 pages, 1 figure. LuaTeX paper source available at https://gitlab.umiacs.umd.edu/eschoute/arct-paper ; updated with changes from published version, tightened lower bound for modular architectures

References in corpus (14)

• Characterizing Quantum Supremacy in Near-Term Devices
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Toward the first quantum simulation with quantum speedup
• Experimental Comparison of Two Quantum Computing Architectures
• Optimal Quantum Circuits for General Two-Qubit Gates
• Synthesis of Quantum Circuits for Linear Nearest Neighbor Architectures
• Compiling quantum circuits to realistic hardware architectures using temporal planners
• Quantum Circuit Placement
• Interaction cost of non-local gates
• Linear Depth Stabilizer and Quantum Fourier Transformation Circuits with no Auxiliary Qubits in Finite Neighbor Quantum Architectures
• An $\Theta (\sqrt{n})$-depth Quantum Adder on a 2D NTC Quantum Computer Architecture
• Noise-Adaptive Compiler Mappings for Noisy Intermediate-Scale Quantum Computers
• Unitary Entanglement Construction in Hierarchical Networks
• Computation at a distance

Cited by in corpus (29)

• Software Mitigation of Crosstalk on Noisy Intermediate-Scale Quantum Computers
• Automated distribution of quantum circuits via hypergraph partitioning
• Optimal Layout Synthesis for Quantum Computing
• Optimality Study of Existing Quantum Computing Layout Synthesis Tools
• Quantum Circuit Transformation Based on Simulated Annealing and Heuristic Search
• Resource-Efficient Quantum Computing by Breaking Abstractions
• rustworkx: A High-Performance Graph Library for Python
• Toward a 2D Local Implementation of Quantum LDPC Codes
• Phase polynomials synthesis algorithms for NISQ architectures and beyond
• Improving Quantum Computation by Optimized Qubit Routing
• Robust Qubit Mapping Algorithm via Double-Source Optimal Routing on Large Quantum Circuits
• Architecture aware compilation of quantum circuits via lazy synthesis
• 2QAN: A quantum compiler for 2-local qubit Hamiltonian simulation algorithms
• Finding Small and Large k-Clique Instances on a Quantum Computer
• Quantum routing with fast reversals
• Exploring ab initio machine synthesis of quantum circuits
• Fast simulation of quantum algorithms using circuit optimization
• Using Spectral Graph Theory to Map Qubits onto Connectivity-Limited Devices
• Decoding techniques applied to the compilation of CNOT circuits for NISQ architectures
• Quantum Circuit Mutants: Empirical Analysis and Recommendations
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• Full Characterization of the Depth Overhead for Quantum Circuit Compilation with Arbitrary Qubit Connectivity Constraint
• Fidelity decay and error accumulation in random quantum circuits
• Software-Hardware Co-Optimization for Computational Chemistry on Superconducting Quantum Processors
• Quantum Circuit Transformation: A Monte Carlo Tree Search Framework
• A Variation-Aware Quantum Circuit Mapping Approach Based on Multi-agent Cooperation
• Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis
• Error Mitigation in Quantum Computers through Instruction Scheduling
• Nuwa: A Quantum Circuit Transpiler Based on a Finite-Horizon Heuristic for Placement and Routing