Bqa: A High-Performance Quantum Circuits Scheduling Strategy Based on Heuristic Search

Xin-miao Chen, Shi Wang, Yong-jin Ye, Yongzheng Wu, Bo JiangSSRN 2022 · DOI

TL;DR

This paper introduces BQA (Busy Qubits Avoid), a novel heuristic search strategy for optimizing quantum circuit scheduling. BQA aims to reduce execution time and improve reliability by intelligently inserting SWAP gates, particularly by leveraging qubit "busyness" to hide SWAP overhead, outperforming existing methods like Qiskit.

What Problem Does This Paper Address?

Quantum computers promise immense computational power, but their practical implementation faces significant hurdles. A key challenge is the limited connectivity between qubits on a physical chip. Quantum algorithms, however, often assume arbitrary qubit connectivity. To bridge this gap, compilers insert SWAP gates to bring non-adjacent qubits together for operations. Unfortunately, excessive SWAP gate insertion leads to longer execution times and increased susceptibility to decoherence errors, degrading performance and reliability. Existing methods for SWAP gate optimization often struggle to balance the cost of the SWAP gate itself with the cascading effects it has on subsequent operations. This paper tackles the problem of efficiently scheduling quantum circuits by optimizing SWAP gate insertion, specifically addressing the overhead and its impact on overall execution time and qubit utilization.

Methods

The core of BQA is a heuristic search strategy designed to optimize SWAP gate insertion. It operates by:

  • Modeling: Representing the quantum chip topology as a graph and the quantum circuit as a Directed Acyclic Graph (DAG) to capture gate dependencies.
  • Discriminator: Identifying two-qubit gates that require SWAP gates due to non-adjacent qubits.
  • Searcher: For gates requiring SWAPs, the searcher explores potential SWAP gate placements. It employs a heuristic function that considers two crucial factors:
  • Front Cost: The overhead introduced by the SWAP gate itself, aiming to "hide" this cost by overlapping it with other operations on "busy" qubits. This leverages the inherent parallelism of quantum circuits.
  • Backend Cost: The potential for the inserted SWAP gate to necessitate additional SWAP gates for subsequent operations, thus avoiding a cascade of SWAPs.
  • Time Accumulator: Tracks the execution time of each qubit in real-time, providing crucial information for the heuristic function to assess qubit "busyness" and potential for hiding SWAP overhead.
  • Mapping Table: Corrects qubit positions after SWAP gate insertions to ensure the final output state is accurate, mitigating a common issue with naive SWAP insertion.

The heuristic function combines these costs, aiming to find a SWAP placement that minimizes both immediate and future overhead.

Datasets

The paper does not explicitly mention using pre-existing datasets for training. Instead, it uses Python simulations to evaluate its method. The evaluation involves:

  • Quantum Algorithms: AND, OR, GROVER, and Quantum Volume (QV) algorithms with varying numbers of qubits (4, 6, 8, 10).
  • Topologies: Linear, ladder, and square qubit connectivity layouts.
  • Random Quantum Gate Sequences: Generated by controlling qubit number, gate count, and the probability of CNOT gates to analyze performance under different circuit structures.

Key Insights and Ideas

  • "Busy Qubits Avoid" (BQA) Strategy: The core idea is to leverage the imbalance in qubit activity ("busyness") to hide the overhead of SWAP gates. If a qubit is already heavily utilized, inserting a SWAP gate on it might not significantly increase its overall execution time, as it would likely be busy with other operations anyway.
  • Dual Cost Heuristic: The heuristic function's consideration of both "front cost" (immediate SWAP overhead) and "backend cost" (future SWAP requirements) is crucial for holistic optimization. This moves beyond simply minimizing the number of SWAPs to minimizing their overall impact.
  • Topology Matters: The performance of BQA, and indeed quantum circuit optimization in general, is significantly influenced by the underlying qubit connectivity. Less connected topologies (like linear) benefit more from BQA's optimization capabilities.
  • CNOT Gate Density is Key: The effectiveness of BQA is more pronounced in circuits with a higher density of CNOT gates, as these are the primary drivers for SWAP gate insertion.

Key Results

  • Significant Speedup: BQA demonstrated a substantial reduction in execution time compared to Qiskit's default optimization (opt3). In some cases, BQA achieved execution times that were only 0.5 times that of the Qiskit-compiled circuit.
  • Scalability: The performance advantage of BQA over Qiskit increased with the number of qubits, particularly for algorithms with a higher gate count. For a 10-qubit QV algorithm, BQA was significantly faster.
  • Topology Impact: On linear topologies, BQA showed a greater advantage than on ladder or square topologies, indicating that reduced qubit connectivity amplifies the benefits of BQA's optimization.
  • Random Gate Sequences: BQA consistently outperformed Qiskit across various probabilities of CNOT gates and increasing gate numbers, reinforcing its effectiveness in diverse circuit scenarios.

Limitations and Future Work

  • Simulation-Based Evaluation: The paper relies on numerical simulations rather than actual quantum hardware for evaluation. While this allows for precise measurement of theoretical performance, real-world hardware noise and imperfections could introduce additional complexities.
  • Heuristic Nature: As a heuristic search, BQA does not guarantee an absolutely optimal solution, though it aims for a highly effective one.
  • Future Work: The authors suggest that their approach can provide a boost to future quantum circuit optimization and quantum computing development. Further exploration into more complex topologies and larger-scale quantum algorithms would be valuable. The paper also implicitly suggests that integrating BQA into existing quantum compilation frameworks could further enhance their capabilities.

Summary updated

BibTeX
@misc{chen2022bqa,
  author = {Xin-miao Chen and Shi Wang and Yong-jin Ye and Yongzheng Wu and Bo Jiang},
  title = {{Bqa: A High-Performance Quantum Circuits Scheduling Strategy Based on Heuristic Search}},
  year = {2022},
  doi = {10.2139/ssrn.4261653},
  howpublished = {SSRN},
}
Figure