Two-step approach to scheduling quantum circuits

Abstract

As the effort to scale up existing quantum hardware proceeds, it becomes necessary to schedule quantum gates in a way that minimizes the number of operations. There are three constraints that have to be satisfied: the order or dependency of the quantum gates in the specific algorithm, the fact that any qubit may be involved in at most one gate at a time, and the restriction that two-qubit gates are implementable only between connected qubits. The last aspect implies that the compilation depends not only on the algorithm, but also on hardware properties like connectivity. Here we suggest a two-step approach in which logical gates are initially scheduled neglecting connectivity considerations, while routing operations are added at a later step in a way that minimizes their overhead. We rephrase the subtasks of gate scheduling in terms of graph problems like edge-coloring and maximum subgraph isomorphism. While this approach is general, we specialize to a one dimensional array of qubits to propose a routing scheme that is minimal in the number of exchange operations. As a practical application, we schedule the Quantum Approximate Optimization Algorithm in a linear geometry and quantify the reduction in the number of gates and circuit depth that results from increasing the efficacy of the scheduling strategies.

Edited text. Added figure summarizing the two-step approach

References in corpus (2)

• Efficient Distributed Quantum Computing
• Compiling quantum circuits to realistic hardware architectures using temporal planners

Cited by in corpus (19)

• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Challenges and Opportunities of Near-Term Quantum Computing Systems
• Asymptotic Improvements to Quantum Circuits via Qutrits
• A Hardware-Aware Heuristic for the Qubit Mapping Problem in the NISQ Era
• ADAPT: Mitigating Idling Errors in Qubits via Adaptive Dynamical Decoupling
• Pulse-level noisy quantum circuits with QuTiP
• Impact of qubit connectivity on quantum algorithm performance
• Enabling Multi-programming Mechanism for Quantum Computing in the NISQ Era
• Formal Constraint-based Compilation for Noisy Intermediate-Scale Quantum Systems
• Interaction graph-based characterization of quantum benchmarks for improving quantum circuit mapping techniques
• Orchestrated Trios: Compiling for Efficient Communication in Quantum Programs with 3-Qubit Gates
• HamLib: A library of Hamiltonians for benchmarking quantum algorithms and hardware
• Robust Qubit Mapping Algorithm via Double-Source Optimal Routing on Large Quantum Circuits
• Integrated Analysis of Performance and Resource of Large-Scale Quantum Computing
• Communication Trade Offs in Intermediate Qudit Circuits
• Universal quantum state preparation via revised greedy algorithm
• Fast simulation of quantum algorithms using circuit optimization
• On connectivity-dependent resource requirements for digital quantum simulation of $d$-level particles
• Q-fid: Quantum Circuit Fidelity Improvement with LSTM Networks