In the noisy medium-scale quantum era, quantum computers are constrained by a limited number of qubits, restricted physical topological structures, and interference from environmental noise, making efficient and stable circuit scheduling a significant challenge. To improve the feasibility of quantum computing, it is essential to optimize the scheduling of quantum gates and the insertion of SWAP gates, reducing running time and enhancing computational efficiency. We propose a collaborative optimization framework that integrates the Quantum Exchange Lock Parallel Scheduler (QELPS) with the Full-level Joint Optimization SWAP Algorithm (FJOSA). In QELPS, SWAP conflict characteristics are used to adjust the layout of quantum gates across different levels while considering physical constraints and dynamically adapting to the circuit’s execution state. Quantum lock parallel technology enables the selective postponement of certain quantum gates, minimizing circuit depth and mitigating inefficiencies caused by excessive SWAP gate insertions. Meanwhile, FJOSA employs a cross-layer optimization strategy that combines heuristic algorithms with cost functions to improve gate scheduling at a global level. This approach effectively reduces quantum gate conflicts found in traditional methods and optimizes execution order, leading to better computational efficiency and circuit performance. Experimental results show that, compared to the traditional 2QAN algorithm, QELPS and FJOSA reduce additional gate insertions by 85.59% and 89.38%, respectively, while decreasing running time by 56.32% and 66.47%. These improvements confirm that the proposed method significantly enhances circuit scheduling efficiency and reduces resource consumption, making it a promising approach for optimizing quantum computation.
In the noisy medium-scale quantum era, quantum computers are constrained by a limited number of qubits, restricted physical topological structures, and interference from environmental noise, making efficient and stable circuit scheduling a significant challenge. To improve the feasibility of quantum computing, it is essential to optimize the scheduling of quantum gates and the insertion of SWAP gates, reducing running time and enhancing computational efficiency. We propose a collaborative optimization framework that integrates the Quantum Exchange Lock Parallel Scheduler (QELPS) with the Full-level Joint Optimization SWAP Algorithm (FJOSA). In QELPS, SWAP conflict characteristics are used to adjust the layout of quantum gates across different levels while considering physical constraints and dynamically adapting to the circuit’s execution state. Quantum lock parallel technology enables the selective postponement of certain quantum gates, minimizing circuit depth and mitigating inefficiencies caused by excessive SWAP gate insertions. Meanwhile, FJOSA employs a cross-layer optimization strategy that combines heuristic algorithms with cost functions to improve gate scheduling at a global level. This approach effectively reduces quantum gate conflicts found in traditional methods and optimizes execution order, leading to better computational efficiency and circuit performance. Experimental results show that, compared to the traditional 2QAN algorithm, QELPS and FJOSA reduce additional gate insertions by 85.59% and 89.38%, respectively, while decreasing running time by 56.32% and 66.47%. These improvements confirm that the proposed method significantly enhances circuit scheduling efficiency and reduces resource consumption, making it a promising approach for optimizing quantum computation.
Quantum computing has already demonstrated great computational potential across multiple domains and has received more and more attention. However, due to the connectivity limitations of Noisy Intermediate-Scale Quantum (NISQ) devices, most of the quantum algorithms cannot be directly executed without the help of inserting SWAP gates. Nevertheless, more SWAP gates lead to a longer execution time and, inevitably, lower fidelity of the algorithm. To this end, this paper proposes an optimized qubit mapping algorithm based on a dynamic look-ahead strategy to minimize the number of SWAP gates inserted. Firstly, a heuristic algorithm is proposed based on maximizing physical qubit connectivity to generate the optimal initial qubit mapping, which reduces the need for logical qubit shifts during subsequent SWAP gate insertion. Secondly, in the form of directed acyclic graphs, we identify quantum gates that violate the constraints of physical coupling and insert SWAP gates to remap qubits, thereby overcoming the limitations of qubit interactions. Finally, the optimal SWAP gate insertion strategy is built by comparing the cost of different SWAP gate insertion strategies through a multi-window look-ahead strategy to reduce the number of SWAP gates inserted. The experimental results show that the strategy in this paper decreases the number of SWAP gate insertions and significantly reduces the depth of quantum circuits when performing qubit mapping compared with state-of-the-art methods.
Currently, quantum computing is developing at a high speed because its high parallelism and high computing power bring new solutions to many fields. However, due to chip process technology, it is difficult to achieve full coupling of all qubits on a quantum chip, so when compiling a quantum circuit onto a physical chip, it is necessary to ensure that the two-qubit gate acts on a pair of coupled qubits by inserting swap gates. It will cause great additional cost when a large number of swap gates are inserted, leading to the execution time of quantum circuits longer. In this paper, we designed a way based on the business to insert swap gates BQA(Busy Qubits Avoid). We exploit the imbalance of the number of gates on qubits, trying to hide the overhead of swap gates. At the same time, we also expect swap gates to make as little negative impact on subsequent two-qubit gates as possible. We have designed a heuristic function that can take into account both of these points. Compared with qiskit, the execution time of the circuit optimized by our proposed method is only 0.5 times that of the qiskit compiled circuit. And when the number of two-qubit gates is large, it will achieve higher level than general conditions. This implies higher execution efficiency and lower decoherence error rate.
Abstract Quantum computing is currently a research hotspot in both academia and industry. The inherent parallelism of quantum computers and the resulting powerful computing power will bring new solutions to many problems that are difficult for classical computers. However, due to the limitations of technical conditions, it is difficult to achieve full direct coupling of all qubits on a quantum chip. When compiling a quantum circuit onto a physical chip, it is necessary to ensure those two-qubit gates act on pairs of directly coupled qubits by inserting SWAP gates. It will cause great additional cost when a large number of SWAP gates are inserted, leading to the execution time of quantum circuits longer. In this paper, we designed a strategy based on the business of each individual qubit to insert SWAP gates, named Busy-Qubits-Avoid Strategy. On the one hand, we try to hide the time overhead incurred by the inserted SWAP gates by exploiting the uneven distribution of quantum gates over qubits. On the other hand, we also expect the inserted SWAP gates to make as little negative impact on subsequent two-qubit gates as possible. We designed a heuristic function which take into account both of these points. Compared with Srabe and tket, we achieved a better effect. In addition, as the number of two-qubit gates increases, better optimization results will be achieved. This implies higher execution efficiency and lower decoherence error rate.
In the noisy intermediate-scale quantum (NISQ) era, as the scale of existing quantum hardware continues to expand, the demand for effective methods to schedule quantum gates and minimize the number of operations has become increasingly urgent. To address this demand, the Quantum Firefly Algorithm (QFA) has been designed by incorporating quantum information into the traditional firefly algorithm. This integration enables fireflies to explore multiple positions simultaneously, thereby increasing search space coverage and utilizing quantum tunneling effects to escape local optima. Through wave function evolution and collapse mechanisms described by the Schrödinger equation, a balance between exploring new solutions and exploiting known solutions is achieved by the QFA. Additionally, random perturbation steps are incorporated into the algorithm to enhance search diversity and prevent the algorithm from being trapped in local optima. In quantum circuit scheduling problems, the QFA optimizes quantum gate operation sequences by evaluating the fitness of scheduling schemes, reducing circuit depth and movement operations, while improving parallelism. Experimental results demonstrate that, compared to traditional algorithms, the QFA reduces SWAP gates by an average of 44% and CNOT gates by an average of 16%. When compared to modern algorithms, it reduces SWAP gates by an average of 7% and CNOT gates by an average of 12%.
Even as quantum computers continue to increase in number of qubits, high error rates limit the size of quantum circuits that can be executed. This results in low throughput and poor resource utilization on quantum computers. To address this, recent research has focused on extending circuit optimization and compilation techniques to support simultaneous execution of quantum circuits (i.e. quantum parallelism). While much work has been spent developing parallel mapping and gate scheduling techniques, there are few approaches to the problem of parallel job scheduling on quantum computers. There are several constraints that make quantum job scheduling different from classical scheduling. We propose a scheduling algorithm, QGroup, for parallelizing circuits of different lengths and shot counts while mitigating parallel slowdowns due to measurement synchronization. QGroup achieves a better parallelism-runtime tradeoff, with significant speedup and fidelity increase over existing methods. QGroup achieves improvement in both fidelity and runtime for noise-sensitive, diverse workloads.
The conventional approach for initial qubit mapping in the Noisy Intermediate-Scale Quantum (NISQ) era typically uses a static heuristic strategy, overlooking insufficient qubit neighborhood in subsequent operations, resulting in excess additional SWAP gates. To address this, we introduce a multifactor interaction cost function considering qubit distance, interaction time, and gate operation error rates, enhancing SWAP gate selection in the traditional strategy. Considering quantum hardware constraints, we propose Batch SWAP Optimization Strategy (BSOS). BSOS tackles qubit mapping challenges by leveraging optimal SWAP gate selection and a SWAP-based batch update technique, effectively minimizing SWAP gates throughout circuit execution. Experimental results show that BSOS significantly reduces additional gates by intelligently selecting SWAP gates and using batch updating, with a 38.1% average decrease in inserted SWAP gates, leading to a 12% reduction in hardware gate counting overhead.