NISQ设备的量子电路调度策略优化研究

doi:10.3778/j.issn.1002-8331.2401-0224

计算机工程与应用 ›› 2024, Vol. 60 ›› Issue (22): 105-113.DOI: 10.3778/j.issn.1002-8331.2401-0224

NISQ设备的量子电路调度策略优化研究

李晖，卢凯，韩子傲，鞠明媚，刘述娟，杜左强

1.哈尔滨商业大学计算机与信息工程学院，哈尔滨 150028
2.黑龙江省电子商务与信息处理重点实验室，哈尔滨 150028

出版日期:2024-11-15 发布日期:2024-11-14

Optimization Research on Quantum Circuit Scheduling Strategies for NISQ Devices

LI Hui, LU Kai, HAN Zi’ao, JU Mingmei, LIU Shujuan, DU Zuoqiang

1.School of Computer and Information Engineering, Harbin University of Commerce, Harbin 150028, China
2.Heilongjiang Key Laboratory of Electronic Commerce and Information Processing, Harbin 150028, China

Online:2024-11-15 Published:2024-11-14

摘要/Abstract

摘要： 在嘈杂的中尺度量子（noisy intermediate-scale quantum，NISQ）时代，调度是量子电路编译的关键步骤。传统调度策略未充分利用量子计算的并行性，忽略了层内操作的潜在并行优化。因此，设计了两种优化策略：拓扑层级调度策略（topological layered scheduling strategy，TLSS）和层内冲突优化策略（layerwise conflict optimization strategy，LCOS）。TLSS利用贪心算法和拓扑排序原理，在层结构中分配量子门，以最大化并行执行量子门操作的数量。LCOS在层内插入SWAP门并最小化冲突以提高并行度，优化整体计算效率。实验结果表明，在涉及4至22量子比特、平面拓扑结构以及双量子比特的平均寿命为67?μs的特定环境下，TLSS与LCOS分别降低51.1%和53.2%的SWAP门数量，减少14.7%和15%的硬件门开销。由于量子电路的复杂性及层间时序关系的干扰，将两策略结合后SWAP门数量降低51.6%，硬件门开销减少14.8%。然而结果的适用性受到不同结构和硬件限制的影响。

关键词: 量子电路调度, 拓扑层级调度策略（TLSS）, 层内冲突优化策略（LCOS）, NISQ设备, 量子电路编译

Abstract: In the noisy intermediate-scale quantum (NISQ) era, scheduling plays a critical role in the compilation of quantum circuits. Traditional scheduling strategies fail to fully exploit the parallelism of quantum computing and overlook the potential parallel optimization within layers. To address this, two optimization strategies are designed：topological layered scheduling strategy (TLSS) and layerwise conflict optimization strategy (LCOS). TLSS utilizes greedy algorithms and topological sorting principles to allocate quantum gates within the layer structure, maximizing the parallel execution of quantum gate operations. LCOS inserts SWAP gates within layers to minimize conflicts and enhance parallelism, optimizing overall computational efficiency. Experimental results demonstrate that, in specific environments involving 4 to 22 qubits, planar topological structures, and an average lifespan of 67 μs for two qubits, TLSS and LCOS respectively reduce the number of SWAP gates by 51.1% and 53.2%, and decrease hardware gate overheads by 14.7% and 15%. Combining both strategies reduces the number of SWAP gates by 51.6% and hardware gate overheads by 14.8%, due to the complexity of quantum circuits and the interference in inter-layer temporal relationships. However, the applicability of the results is subject to different structure and hardware constraints.

Key words: quantum circuit scheduling, topological layered scheduling strategy (TLSS), layerwise conflict optimization strategy (LCOS), NISQ devices, quantum circuit compilation

李晖, 卢凯, 韩子傲, 鞠明媚, 刘述娟, 杜左强. NISQ设备的量子电路调度策略优化研究[J]. 计算机工程与应用, 2024, 60(22): 105-113.

LI Hui, LU Kai, HAN Zi’ao, JU Mingmei, LIU Shujuan, DU Zuoqiang. Optimization Research on Quantum Circuit Scheduling Strategies for NISQ Devices[J]. Computer Engineering and Applications, 2024, 60(22): 105-113.

参考文献

[1] ALVAREZ-RODRIGUEZ U, SANZ M, LAMATA L, et al. Quantum artificial life in an IBM quantum computer[J]. Scientific Reports, 2018, 8(1): 14793.
[2] MOTTA M, SUN C, TAN A T K, et al. Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution[J]. Nature Physics, 2020, 16(2): 205-210.
[3] GAMBETTA J. IBM’s roadmap for scaling quantum technology[J]. IBM Research Blog, 2020.
[4] PRESKILL J. Quantum computing in the NISQ era and beyond[J]. Quantum, 2018, 2: 79.
[5] CAMPAGNE-IBARCQ P, EICKBUSCH A, TOUZARD S, et al. Quantum error correction of a qubit encoded in grid states of an oscillator[J]. Nature, 2020, 584(7821): 368-372.
[6] GUERRESCHI G G, PARK J. Two-step approach to scheduling quantum circuits[J]. Quantum Science and Technology, 2018, 3(4): 045003.
[7] LAO L, VAN SOMEREN H, ASHRAF I, et al. Timing and resource-aware mapping of quantum circuits to superconducting processors[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2021, 40(2): 359-371.
[8] ALAM M, ASH-SAKI A, GHOSH S. Circuit compilation methodologies for quantum approximate optimization algorithm[C]//Proceedings of the 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture, 2020: 215-228.
[9] ALAM M, ASH-SAKI A, GHOSH S. An efficient circuit compilation flow for quantum approximate optimization algorithm[C]//Proceedings of the 2020 57th ACM/IEEE Design Automation Conference, 2020: 1-6.
[10] LI S, NGUYEN K D, CLARE Z, et al. Single-qubit gates matter for optimizing quantum circuit depth in qubit mapping[J]. arXiv:2308.00876, 2023.
[11] LI G, DING Y, XIE Y. Tackling the qubit mapping problem for NISQ-era quantum devices[C]//Proceedings of the 24th International Conference on Architectural Support for Programming Languages and Operating Systems, 2019: 1001-1014.
[12] LI S, ZHOU X, FENG Y. Qubit mapping based on subgraph isomorphism and filtered depth-limited search[J]. IEEE Transactions on Computers, 2020, 70(11): 1777-1788.
[13] ZHOU X, LI S, FENG Y. Quantum circuit transformation based on simulated annealing and heuristic search[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(12): 4683-4694.
[14] NIELSEN M A, CHUANG I L. Quantum computation and quantum information[M]. New York: Cambridge University Press, 2001.
[15] ZULEHNER A, PALER A, WILLE R. An efficient methodology for mapping quantum circuits to the IBM QX architectures[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 38(7): 1226-1236.
[16] CROSS A. The IBM Q experience and QISKit open-source quantum computing software[C]//APS March Meeting, 2018.
[17] LAO L, BROWNE D E. 2QAN: a quantum compiler for 2-local qubit Hamiltonian simulation algorithms[C]//Proceedings of the 49th Annual International Symposium on Computer Architecture, 2022: 351-365.

NISQ设备的量子电路调度策略优化研究

Optimization Research on Quantum Circuit Scheduling Strategies for NISQ Devices

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics