Robust Qubit Mapping Algorithm via Double-Source Optimal Routing on Large Quantum Circuits

Duostra surpasses IBM Qiskit, QMAP, t|ket>, and SABRE on mapping cost for most large quantum circuits, including Galois Field (GF), inst, classical EDA benchmark circuits, adder, and qugan.

“Regarding scalability, Duostra surpasses IBM Qiskit, QMAP, t | 𝑘𝑒𝑡 ⟩ , and SABRE on mapping cost for most large quantum circuits, including Galois Field (GF), inst, classical Electronic Design Automation (EDA) benchmark circuits [40], adder, and qugan.”

• cites [40] [40] Franc Brglez. A neutral netlist of 10 combinational benchmark circuits and a target translator in Fortran. In Proc. International Symposium on Circuits and Systems, 1985 , 1985. -Not checked yet

  Not checked in the free run.

For mid-size circuits such as the SABRE-large benchmark, Duostra improves mapping costs by 4.5%, 5.2%, 16.3%, 20.7%, and 25.7%, when compared to QMAP, TOQM, t|ket>, Qiskit, and SABRE, respectively.

“Besides, for mid-size circuits such as the SABRE-large benchmark, we improve the mapping costs by 4.5%, 5.2%, 16.3%, 20.7%, and 25.7%, when compared to QMAP, TOQM, t | 𝑘𝑒𝑡 ⟩ , Qiskit, and SABRE, respectively.”

• Also stated in: § 1 INTRODUCTION · p. 4 · hedged

  “The experimental results indicate that in the mid-size test cases within the SABRE-large test suite [28], our approach achieves an average cost improvement by 4.5%, 5.2%, 16.3%, 20.7%, and 25.7%, when compared to QMAP, TOQM, t | 𝑘𝑒𝑡 ⟩ , Qiskit, and SABRE, respectively.”

• cites [28] [28] Gushu Li, Yufei Ding, and Yuan Xie. Tackling the qubit mapping problem for NISQ-era quantum devices. In Proc. International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) , pages 1001-1014, 2019. - sourceNot checked yet

  Not checked in the free run.

On large circuits with more than 50 qubits, Duostra reduces mapping cost on average 21.75% over the virtual best results among QMAP, t|ket>, Qiskit and SABRE.

“on large circuits with more than 50 qubits, we can reduce the mapping cost on an average 21.75% over the virtual best results among QMAP, t | 𝑘𝑒𝑡 ⟩ , Qiskit and SABRE.”

The results for mid-size test cases within SABRE-large are generated within a runtime of 5 minutes.

“Additionally, those results are generated within a runtime of 5 minutes.”

Duostra can handle problem sizes up to 11,969-qubit QFT within 3 hours.

“Furthermore, our method can handle problem sizes up to 11,969-qubit QFT within 3 hours (with time complexity 𝑂 ( 𝑛 2 . 8 ) , where 𝑛 denotes the numbers of qubits).”

On benchmark circuit cm42a_207, Duostra renders a much balanced distribution of SWAP operations with standard deviation 35.26 and maximum number 112.

“On the other hand, Duostra renders a much balanced distribution of the SWAP operations. Its standard deviation is 35.26 and the maximum number is 112.”

Qiskit excelled for larger GF circuits.

“Qiskit excelled for larger GF circuits”

Different compared methods won at different benchmark sets.

“In general, due to the nature of the heuristic algorithms, different compared methods won at different benchmark sets”

TOQM failed to execute on the large-size circuits (TLE).

“For the method TOQM [38] included in the mid-size circuit experiments, it failed to execute on the large-size circuits (TLE).”

• cites [38] [38] Chi Zhang, Ari B Hayes, Longfei Qiu, Yuwei Jin, Yanhao Chen, and Eddy Z Zhang. Time-optimal qubit mapping. In Proc. ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) , pages 360-374, 2021. - sourceNot checked yet

  Not checked in the free run.

• AssumptionRests on an assumption: The Mapping Cost metric used to compare mapping algorithms accurately reflects the total execution time of a quantum circuit.

For large benchmarks whose numbers of qubits exceed 50, Duostra achieves on average 21.75% improvement over the virtual best results among QMAP, t|ket>, Qiskit and SABRE.

“The statistics show that we can achieve on the average 21.75% improvement over the best performance of the compared methods.”

• Also stated in: § 6 CONCLUSION · p. 22 · plain

  “For the large benchmarks whose numbers of qubits exceed 50, our framework can achieve on the average 21.75% improvements over the virtual best results among QMAP, t | 𝑘𝑒𝑡 ⟩ , Qiskit and SABRE.”

On extra-large QFT circuits, the runtime of the Shortest Path router is around two-thirds of that of Duostra.

“Conversely, the runtime of the Shortest Path router is around two-thirds of that of Duostra.”

QMAP performed better on qugan and some smaller ISCAS'85 benchmarks.

“QMAP performed better on qugan and some smaller ISCAS'85 benchmarks”

For mid-size circuits (SABRE benchmark), Duostra improves Mapping Costs by 4.5%, 5.2%, 16.3%, 20.7% and 25.7% compared to QMAP, TOQM, t|ket>, Qiskit and SABRE, respectively.

“For instance, for the mid-size circuits (i.e. SABRE benchmark), we improve the Mapping Costs by 4.5%, 5.2%, 16.3%, 20.7% and 25.7%, when compared to QMAP, TOQM, t | 𝑘𝑒𝑡 ⟩ , Qiskit and SABRE, respectively.”

Duostra SP estimation outperforms the other methods in most cases on large benchmarks.

“Duostra SP estimation outperforms the others in most cases.”

• AssumptionRests on an assumption: The Mapping Cost metric used to compare mapping algorithms accurately reflects the total execution time of a quantum circuit.
• AssumptionRests on an assumption: The extrapolated heavy-hexagon topologies up to 11,969 qubits are valid proxies for future large-scale quantum devices.

SABRE frequently produced the better results, particularly standing out for the QFT cases.

“SABRE frequently produced the better results, particularly standing out for the QFT cases”

On extra-large QFT circuits, the Mapping Cost associated with the Duostra router is consistently less than half of the cost generated by the Shortest Path router.

“As depicted in Fig. 12, the Mapping Cost associated with the Duostra router is consistently less than half of the cost generated by the Shortest Path router.”

For a double-qubit gate whose control bit is not adjacent to its target bit, the Duostra Algorithm can generate a SWAP sequence with minimum Mapping Cost.

“Given a double-qubit gate whose control bit is not adjacent to its target bit, Duostra Algorithm can generate a SWAP sequence with minimum Mapping Cost.”

The runtime of algorithms that calculate costs of all potential swapping candidates in each iteration when selecting a SWAP was very long.

“Although the above-mentioned algorithms claimed to achieve optimal mapping solutions, the runtime of these algorithms was very long due to the fact that they needed to calculate the costs of all the potential swapping candidates in each iteration when selecting a SWAP.”

• cites [37] [37] Haowei Deng, Yu Zhang, and Quanxi Li. Codar: A contextual duration-aware qubit mapping for various NISQ devices. In Proc. ACM/IEEE Design Automation Conference (DAC) , pages 1-6, 2020. - sourceNot checked yet

  Not checked in the free run.

• cites [38] [38] Chi Zhang, Ari B Hayes, Longfei Qiu, Yuwei Jin, Yanhao Chen, and Eddy Z Zhang. Time-optimal qubit mapping. In Proc. ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) , pages 360-374, 2021. - sourceNot checked yet

  Not checked in the free run.

• cites [39] [39] Lingling Lao, Hans Van Someren, Imran Ashraf, and Carmen G. Almudever. Timing and resource-aware mapping of quantum circuits to superconducting processors. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 41(2):359-371, February 2022. - sourceNot checked yet

  Not checked in the free run.

Once a vertex is pushed into the priority queue, its cost remains unchanged.

“Furthermore, once a vertex is pushed into the priority queue, its cost remains unchanged.”

Exact methods for qubit mapping, although optimal for small circuits, are inferior to heuristic methods in large circuits.

“However, these exact methods, although being able to achieve optimality for small circuits, are inferior to the heuristic methods in large circuits.”

• cites [9] [9] Marcos Yukio Siraichi, Vinícius Fernandes dos Santos, Caroline Collange, and Fernando Magno Quintão Pereira. Qubit allocation. In Proc. International Symposium on Code Generation and Optimization , pages 113-125, 2018. -Not checked yet

  Not checked in the free run.

• cites [33] [33] Bochen Tan and Jason Cong. Optimal layout synthesis for quantum computing. In Proceedings of the 39th International Conference on Computer-Aided Design (ICCAD) , pages 1-9, 2020. - sourceNot checked yet

  Not checked in the free run.

• cites [36] [36] Abtin Molavi, Amanda Xu, Martin Diges, Lauren Pick, Swamit Tannu, and Aws Albarghouthi. Qubit mapping and routing via MaxSAT. In 2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO) , pages 1078-1091, October 2022. - sourceNot checked yet

  Not checked in the free run.

These algorithms could only handle mapping problems up to 50 qubits.

“Consequently, they could only handle mapping problems up to 50 qubits, which is much smaller than the number of required qubits for achieving quantum advantage.”

• cites [37] [37] Haowei Deng, Yu Zhang, and Quanxi Li. Codar: A contextual duration-aware qubit mapping for various NISQ devices. In Proc. ACM/IEEE Design Automation Conference (DAC) , pages 1-6, 2020. - sourceNot checked yet

  Not checked in the free run.

• cites [38] [38] Chi Zhang, Ari B Hayes, Longfei Qiu, Yuwei Jin, Yanhao Chen, and Eddy Z Zhang. Time-optimal qubit mapping. In Proc. ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) , pages 360-374, 2021. - sourceNot checked yet

  Not checked in the free run.

• cites [39] [39] Lingling Lao, Hans Van Someren, Imran Ashraf, and Carmen G. Almudever. Timing and resource-aware mapping of quantum circuits to superconducting processors. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 41(2):359-371, February 2022. - sourceNot checked yet

  Not checked in the free run.

The time complexity of the overall method is O(n^2.8), where n denotes the number of qubits.

“Furthermore, our method can handle problem sizes up to 11,969-qubit QFT within 3 hours (with time complexity 𝑂 ( 𝑛 2 . 8 ) , where 𝑛 denotes the numbers of qubits).”

Directly choosing the shortest path as the routing path may cause collisions where the route conflicts with the swaps of another gate, forcing a pause in the swapping procedure and prolonging execution time.

“If we were to directly choose the shortest path as the routing path, collisions may occur where the route conflicts with the swaps of another gate. This situation would force us to pause the swapping procedure, leading to a prolongation of the execution time.”

Given the shortest path, the Duostra router is still needed to produce the local optimal result.

“Therefore, given the shortest path, we still need to rely on the Duostra router to produce the local optimal result.”

The time complexity of the Duostra algorithm is O(n log n), where n is the number of qubits in the quantum device.

“Additionally, we demonstrate that the time complexity of this algorithm is 𝑂 ( 𝑛 log 𝑛 ) , where 𝑛 represents the number of qubits in the quantum device.”

• Also stated in: § 1 INTRODUCTION · p. 4 · plain

  “an 𝑂 ( 𝑛 log 𝑛 ) Duostra router”

It is impossible for the initial placement strategy to ensure the overall optimality of the qubit mapping problem.

“Therefore, it is impossible for the initial placement strategy to ensure the overall optimality of the qubit mapping problem.”

Exhaustive enumeration of all possible execution sequences of gates is intractable even for relatively small-scale quantum circuits.

“However, this exhaustive enumeration proves to be an intractable task [9], even for relatively small-scale quantum circuits.”

• cites [9] [9] Marcos Yukio Siraichi, Vinícius Fernandes dos Santos, Caroline Collange, and Fernando Magno Quintão Pereira. Qubit allocation. In Proc. International Symposium on Code Generation and Optimization , pages 113-125, 2018. -Not checked yet

  Not checked in the free run.

The first edge where the two routing paths converge is the optimal solution e*, which has the smallest occupied time.

“Lemma 4.2 (Duostra Optimality). The first edge where the two routing paths converge is the solution 𝑒 ∗ , which has the smallest occupied time.”

• Also stated in: § Algorithm 2 Duostra (Dual-source Dijkstra) · p. 13 · plain

  “As a result, we can ensure that when the two search trees from 𝑠 0 and 𝑠 1 converge at a pair of adjacent physical qubits, they will indeed form the optimal routing path with the smallest occupied time.”

Duostra router can guarantee the optimal mapping solution for a given double-qubit gate.

“an 𝑂 ( 𝑛 log 𝑛 ) Duostra router that can guarantee the optimal mapping solution for a given double-qubit gate”

• Also stated in: § 3.2 Routing: Duostra (Dual-source Dijkstra) · p. 8 · plain

  “The algorithm outputs an optimal routing path and provides a SWAP sequence that efficiently brings the two involved qubits, of a double-qubit gate, adjacent to each other.”

Maintaining a low average node degree in superconducting quantum devices, typically less than three, is crucial to minimize frequency collisions and crosstalk errors.

“However, based on current knowledge, maintaining a low average node degree in superconducting quantum devices, typically less than three, is crucial to minimize frequency collisions and crosstalk errors [46].”

• cites [46] [46] Christopher Chamberland, Guanyu Zhu, Theodore J Yoder, Jared B Hertzberg, and Andrew W Cross. Topological and subsystem codes on low-degree graphs with flag qubits. Physical Review X , 10(1):011022, 2020. - sourceNot checked yet

  Not checked in the free run.

The top vertex in the priority queue, with the lowest cost, represents the earliest qubit that can be operated using a SWAP gate.

“As we define the cost of a seen vertex 𝑣 in the priority queue as the occupied time of the optimal routing path from 𝑣.𝑠𝑜𝑢𝑟𝑐𝑒 to 𝑣 , the top vertex in the priority queue, with the lowest cost, represents the earliest qubit that can be operated using a SWAP gate.”

The Duostra Router's incorporation of additional information, such as the occupied time, contributes to its ability to generate superior results compared to a simple approach like the Shortest Path router.

“This leads us to conclude that, when compared to a simple approach like the Shortest Path router, which merely inserts SWAP gates to solve the problem, the Duostra Router's incorporation of additional information, such as the occupied time, contributes to its ability to generate superior results.”

The experimental results on various sets of benchmarks demonstrate the superiority of the framework on the qubit mapping problems.

“The experimental results on various sets of benchmarks demonstrate the superiority of our framework on the qubit mapping problems.”

The Duostra router can efficiently generate optimal routing paths for SWAP insertions on double-qubit gates.

“Our framework encompasses an innovative Duostra router that can efficiently generate optimal routing paths for SWAP insertions on double-qubit gates”

Duostra outperforms the Shortest Path router considering both solution quality and efficiency as the circuit size increases.

“The trend line of Duostra consistently appears lower, indicating that Duostra outperforms its counterpart considering both solution quality and efficiency as the circuit size increases.”

Lemma 4.1: The seen set contains the unvisited vertex with the minimum occupied time.

“Lemma 4.1. The seen set contains the unvisited vertex with the minimum occupied time”

The Duostra Algorithm is designed with local optimality to balance mapping cost and program runtime for large circuits.

“We design the Duostra Algorithm by capitalizing on the property of local optimality in order to strike a balance between the mapping cost and the program runtime for large circuits.”

The occupied time of an unseen vertex is inevitably greater than the vertex with the smallest occupied time in the seen set.

“Therefore, since the occupied time of any seen vertex ( 𝑠 𝑎𝑟𝑏 .𝑜𝑐𝑝 ) is greater than or equal to the minimum occupied time of all the seen vertices, the occupied time of an unseen vertex will inevitably be greater than the vertex with the smallest occupied time in the seen set.”

The proposed qubit mapping framework is not limited to specific devices in the NISQ era.

“Our proposed qubit mapping framework is not limited to specific devices in NISQ era.”

The sub-optimal solution e- with the bigger occupied time must be found after the optimal solution e*.

“Because we only prolong the routing paths by selecting a vertex with the minimum occupied time, the sub-optimal solution 𝑒 -with the bigger occupied time must be found after the optimal solution 𝑒 ∗ .”