Abstract
In the Noisy Intermediate-Scale Quantum (NISQ) era, hardware connectivity constraints necessitate the transformation of ideal quantum circuits into hardware-compliant versions. This paper introduces a two-stage algorithm combining simulated annealing for initial qubit placement with a double look-ahead heuristic search for gate scheduling. The approach achieves a 57% reduction in gate overhead on the IBM Q20 architecture compared to previous methods, while maintaining polynomial-time complexity.
Introduction
We are currently in the Noisy Intermediate-Scale Quantum (NISQ) era. While theorists design algorithms assuming "ideal" quantum computers where every qubit can interact with every other qubit, real-world hardware is significantly more restricted. Physical qubits in a Quantum Processing Unit (QPU) are typically laid out in specific grids or graphs. A two-qubit operation, such as a CNOT gate, can only be performed if the two qubits are physical neighbors.
To run complex algorithms, information must be "shuffled" across the chip using SWAP gates to bring necessary qubits into proximity. However, every SWAP gate adds noise and increases circuit depth, which can lead to decoherence before a calculation finishes. Quantum Circuit Transformation (QCT) aims to map logical qubits to physical ones while inserting the minimum number of SWAP gates.
Methods
The proposed algorithm utilizes a two-stage approach to minimize gate overhead:
- Initial Mapping via Simulated Annealing (SA): Rather than starting with a random layout, the algorithm uses SA to find a configuration that optimally fits the initial layers of the circuit. This stochastic optimization allows the algorithm to avoid local optima and find a globally superior starting point.
- Heuristic Search with Double Look-ahead: During circuit execution, the algorithm decides which SWAP gates to insert using a novel "double look-ahead" mechanism. This involves a cost function that weights future gates and a search look-ahead that explores "grandchild" states. By selecting moves that lead to the best consecutive operations, the algorithm avoids "dead ends" common in greedy approaches.
- Fallback and Pruning: To ensure termination, the algorithm employs "remote CNOT" operations if the search stalls. Additionally, a pruning mechanism discards suboptimal paths to maintain computational efficiency.
Experimental Evaluation
The algorithm was evaluated using standard benchmarks (e.g., QFT, adders, and logic circuits) against the coupling graphs of real-world hardware architectures.
Key Results
- IBM Q20 (Tokyo): The proposed method reduced the number of added gates by 57% on average compared to previous state-of-the-art methods.
- IBM QX5: The algorithm achieved a 10% reduction over A*-based search methods.
- Efficiency: The search remains computationally efficient, finding solutions for circuits with up to 10,000 gates in under one minute on standard hardware. The authors proved the algorithm runs in polynomial time relative to circuit size and qubit count.
Conclusion and Future Work
This research demonstrates that combining global optimization for initial mapping with sophisticated look-ahead heuristics can drastically improve the efficiency of quantum circuit execution on NISQ devices. Future work will focus on making the algorithm "noise-aware" by incorporating individual gate error rates and accounting for crosstalk between adjacent qubits.
Summary updated