請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/96213完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 李建模 | zh_TW |
| dc.contributor.advisor | Chien-Mo Li | en |
| dc.contributor.author | 樊明膀 | zh_TW |
| dc.contributor.author | Ming-Bang Fan | en |
| dc.date.accessioned | 2024-11-28T16:13:18Z | - |
| dc.date.available | 2025-10-01 | - |
| dc.date.copyright | 2024-11-28 | - |
| dc.date.issued | 2024 | - |
| dc.date.submitted | 2024-10-02 | - |
| dc.identifier.citation | [1] G. Li, Y. Ding, and Y. Xie, “Tackling the qubit mapping problem for nisq-era quantum devices,” in Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS’19, (New York, NY, USA), p. 1001–1014, Association for Computing Machinery, 2019.
[2] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis, “Mastering the game of go with deep neural networks and tree search,” Nature, vol. 529, pp. 484–489, Jan. 2016. [3] M. G. Pozzi, S. J. Herbert, A. Sengupta, and R. D. Mullins, “Using reinforcement learning to perform qubit routing in quantum compilers,” ACM Transactions on Quantum Computing, vol. 3, may 2022. [4] “Ibm quantum, https://quantum.ibm.com/,” 2024. [5] P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM review, vol. 41, no. 2, pp. 303–332, 1999. [6] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, et al., “Quantum supremacy using a programmable superconducting processor,” Nature, vol. 574, no. 7779, pp. 505–510, 2019. [7] K. Blekos, D. Brand, A. Ceschini, and et al., “A review on quantum approximate optimization algorithm and its variants,” Physics Reports, vol. 1068, pp. 1–66, 2024. [8] A. A. Clerk, M. H. Devoret, S. M. Girvin, F. Marquardt, and R. J. Schoelkopf, “Introduction to quantum noise, measurement, and amplification,” Reviews of Modern Physics, vol. 82, no. 2, p. 1155, 2010. [9] D. Qin, Y. Chen, and Y. Li, “Error statistics and scalability of quantum error mitigation formulas,” npj Quantum Information, vol. 9, p. 35, Apr 2023. [10] K.-Y. Chang and C.-Y. Lee, “Mapping nearest neighbor compliant quantum circuits onto a 2-d hexagonal architecture,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 41, no. 10, pp. 3373–3386, 2022 [11] A. Shafaei, M. Saeedi, and M. Pedram, “Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures,” in 2013 50th ACM/EDAC/IEEE Design Automation Conference (DAC), pp. 1–6, 2013. [12] R. Wille, A. Lye, and R. Drechsler, “Exact reordering of circuit lines for nearest neighbor quantum architectures,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 33, no. 12, pp. 1818–1831, 2014. [13] A. Kole, K. Datta, and I. Sengupta, “A heuristic for linear nearest neighbor realization of quantum circuits by swap gate insertion using n-gate lookahead,” IEEE Journal on Emerging and Selected Topics in Circuits and Systems, vol. 6, no. 1, pp. 62–72, 2016. [14] A. Bhattacharjee, C. Bandyopadhyay, R. Wille, and et al., “Improved look-ahead approaches for nearest neighbor synthesis of 1d quantum circuits,” in 2019 32nd International Conference on VLSI Design and 2019 18th International Conference on Embedded Systems (VLSID), pp. 203–208, 2019. [15] C.-C. Lin, S. Sur-Kolay, and N. Jha, “Paqcs: Physical design-aware fault-tolerant quantum circuit synthesis,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 23, no. 7, pp. 1221–1234, 2015 [16] W. Hattori and S. Yamashita, “Quantum circuit optimization by changing the gate order for 2d nearest neighbor architectures,” in Reversible Computation (J. Kari and I. Ulidowski, eds.), (Cham), pp. 228–243, Springer International Publishing, 2018. [17] J. Ding and S. Yamashita, “Exact synthesis of nearest neighbor compliant quantum circuits in 2-d architecture and its application to large-scale circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 39, no. 5, pp. 1045–1058, 2020. [18] A. Lye, R. Wille, and R. Drechsler, “Determining the minimal number of swap gates for multi-dimensional nearest neighbor quantum circuits,” in The 20th Asia and South Pacific Design Automation Conference, pp. 178–183, 2015. [19] P. Zhu, Z. Guan, and X. Cheng, “A dynamic look-ahead heuristic for the qubit mapping problem of nisq computers,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 39, no. 12, pp. 4721–4735, 2020. [20] R. Wille, L. Burgholzer, and A. Zulehner, “Mapping quantum circuits to ibm qx architectures using the minimal number of swap and h operations,” in 2019 56th ACM/IEEE Design Automation Conference (DAC), pp. 1–6, 2019. [21] K. Booth, M. Do, J. Beck, and et al., “Comparing and integrating constraint programming and temporal planning for quantum circuit compilation,” in Proceedings of the International Conference on Automated Planning and Scheduling, vol. 28, pp. 366–374, 2018. [22] D. Venturelli, M. Do, E. Rieffel, and J. Frank, “Temporal planning for compilation of quantum approximate optimization circuits,” in Scheduling and Planning Applications Workshop (SPARK), p. 58, 2017. [23] P. Murali, J. Baker, A. Javadi-Abhari, and et al., “Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers,” in Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’19, (New York, NY, USA), p. 1015–1029, Association for Computing Machinery, 2019. [24] A. Zulehner, A. Paler, and R. Wille, “An efficient methodology for mapping quantum circuits to the ibm qx architectures,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 38, no. 7, pp. 1226–1236, 2019. [25] S. Tannu and M. K. Qureshi, “Not all qubits are created equal: A case for variability-aware policies for nisq-era quantum computers,” in Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’19, (New York, NY, USA), p. 987–999, Association for Computing Machinery, 2019. [26] X. Zhou, Y. Feng, and S. Li, “A monte carlo tree search framework for quantum circuit transformation,” in 2020 IEEE/ACM International Conference On Computer Aided Design (ICCAD), pp. 1–7, 2020. [27] T. Itoko, R. Raymond, T. Imamichi, and et al., “Quantum circuit compilers using gate commutation rules,” in 2019 24th Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 1–6, 2019. [28] T. Itoko, R. Raymond, T. Imamichi, and A. Matsuo, “Optimization of quantum circuit mapping using gate transformation and commutation,” Integr. VLSI J., vol. 70, p. 43–50, jan 2020. [29] A. Cowtan, S. Dilkes, R. Duncan, A. Krajenbrink, W. Simmons, and S. Sivarajah, “On the Qubit Routing Problem,” in 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019) (W. van Dam and L. Mančinska, eds.), vol. 135 of Leibniz International Proceedings in Informatics (LIPIcs), (Dagstuhl, Germany), pp. 5:1–5:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. [30] S. Sivarajah, S. Dilkes, A. Cowtan, W. Simmons, A. Edgington, and R. Duncan, “t|ket⟩: a retargetable compiler for nisq devices,” Quantum Science and Technology, vol. 6, p. 014003, nov 2020. [31] C.-Y. Huang, C.-H. Lien, and W.-K. Mak, “Reinforcement learning and dear framework for solving the qubit mapping problem,” in 2022 IEEE/ACM International Conference On Computer Aided Design (ICCAD), pp. 1–9, 2022. [32] H. Fan, C. Guo, and W. Luk, “Optimizing quantum circuit placement via machine learning,” in Proceedings of the 59th ACM/IEEE Design Automation Conference, DAC ’22, (New York, NY, USA), p. 19–24, Association for Computing Machinery, 2022. [33] Y. Li, W. Liu, M. Li, and Y. Li, “Quantum circuit compilation for nearest-neighbor architecture based on reinforcement learning,” Quantum Information Processing, vol. 22, p. 295, Jul 2023. [34] A. Sinha, U. Azad, and H. Singh, “Qubit routing using graph neural network aided monte carlo tree search,” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, pp. 9935–9943, Jun. 2022. [35] R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction. Cambridge, MA, USA: A Bradford Book, 2018. [36] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. [37] A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross, B. R. Johnson, and J. M. Gambetta, “Quantum computing with Qiskit,” 2024. [38] R. Iten, R. Moyard, T. Metger, D. Sutter, and S. Woerner, “Exact and practical pattern matching for quantum circuit optimization,” ACM Transactions on Quantum Computing, vol. 3, jan 2022. [39] J. Kelly, R. Barends, B. Campbell, and et al., “Optimal quantum control using randomized benchmarking,” Phys. Rev. Lett., vol. 112, p. 240504, Jun 2014. [40] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis, “Human-level control through deep reinforcement learning,” Nature, vol. 518, pp. 529–533, Feb. 2015. [41] L. Kocsis and C. Szepesvári, “Bandit based monte-carlo planning,” in Machine Learning: ECML 2006 (J. Fürnkranz, T. Scheffer, and M. Spiliopoulou, eds.), (Berlin, Heidelberg), pp. 282–293, Springer Berlin Heidelberg, 2006. [42] R. W. Floyd, “Algorithm 97: Shortest path,” Commun. ACM, vol. 5, p. 345, jun 1962. [43] Y. Wu and Y. Tian, “Training agent for first-person shooter game with actor-critic curriculum learning,” in International Conference on Learning Representations, 2017. [44] Cirq Developers, “Cirq,” May 2024. [45] Qiskit contributors, “Qiskit: An open-source framework for quantum computing,” 2023. [46] L. K. Grover, “A fast quantum mechanical algorithm for database search,” 1996. [47] A. Y. Kitaev, “Quantum measurements and the abelian stabilizer problem,” 1995. [48] S. A. Cuccaro, T. G. Draper, S. A. Kutin, and D. P. Moulton, “A new quantum ripplecarry addition circuit,” 2004. [49] M. J. Bremner, A. Montanaro, and D. J. Shepherd, “Average-case complexity versus approximate simulation of commuting quantum computations,” Phys. Rev. Lett.,vol. 117, p. 080501, Aug 2016. [50] K. Markov, I. Patel, and J. Hayes, “Optimal synthesis of linear reversible circuits,” Quantum Information and Computation, vol. 8, no. 3&4, pp. 0282–0294, 2008. [51] S. Balauca and A. Arusoaie, “Efficient constructions for simulating multi controlled quantum gates,” in Computational Science – ICCS 2022 (D. Groen, C. de Mulatier, M. Paszynski, V. V. Krzhizhanovskaya, J. J. Dongarra, and P. M. A. Sloot, eds.), (Cham), pp. 179–194, Springer International Publishing, 2022. [52] A. Barenco, A. Ekert, K.-A. Suominen, and P. Törmä, “Approximate quantum fourier transform and decoherence,” Physical Review A, vol. 54, p. 139–146, July 1996. | - |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/96213 | - |
| dc.description.abstract | 本研究提出了 LAUREL，一個專為解決量子繞線難題而設計的框架，目標是同時減少量子電路的電路深度和閘門數量。LAUREL 引入了量子運算依賴圖來建模增強式學習（RL）的狀態，使得在等價的量子電路中探索不同的量子邏輯閘執行順序成為可能。
該框架創建了一個基於依賴圖的前瞻窗口，將依賴關係的意識融入增強式學習模型中。LAUREL還採用了`移動'的概念，並引入了鏈鎖機制來管理動作的組合和龐大的動作空間。 我們實施了一個雙重獎勵函數來解決稀疏獎勵問題，並刪除無效的移動。為了配合雙重獎勵函數，我們提出了一種新的雙重獎勵蒙地卡羅增強式學習公式，這使得蒙地卡羅增強式學習在量子繞線中的搜索更加高效。 我們在各種基準電路上進行了廣泛的實驗，包括真實的量子算法電路，結果證明 LAUREL在優化電路深度的同時，與最先進的方法相比，同時保持了有競爭力的閘門數量。該研究還通過消融分析驗證了考慮量子運算依賴關係的有效性，並展示了該框架在更大規模的實際量子電路和量子設備上的可擴展性。結果顯示，LAUREL 在某些量子電路中，和之前同類型增強式學習研究中的結果相比下，在量子電路深度的開銷減少 92.6%，量子邏輯閘數量的開銷減少 93.0%。 | zh_TW |
| dc.description.abstract | This study presents LAUREL, a framework specifically designed to address the challenges of qubit routing, with the dual objectives of reducing both circuit depth and gate number of quantum circuits. LAUREL incorporates a dependency graph to model reinforcement learning(RL) states and enables exploration of different gate execution orders in equivalence quantum circuits. The framework creates a dependency-graph based lookahead window to incorporate dependency awareness into the RL model. It also adapts the concept of move and introduces a chain lock mechanism to manage both the action composition and the vast action space. A dual reward function is implemented to solve sparse reward issues and prune ineffective moves. To correspond with the dual reward function, we propose a new dual reward MCTS RL formulation, which makes the MCTS RL search more efficient in qubit routing. Our extensive experiments performed on diverse benchmarks, including well-known quantum algorithm circuits, demonstrate LAUREL's superiority in optimizing circuit depth while maintaining competitive gate numbers compared to state-of-the-art methods. The study also validates the efficacy of dependency-aware routing through an ablation analysis and demonstrates the framework's scalability for larger real quantum circuits and quantum devices. The results demonstrate that LAUREL can reduce the depth overhead of previous RL work by up to 92.6% and decrease the gate number overhead by as much as 93.0% in certain quantum circuits. | en |
| dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2024-11-28T16:13:18Z No. of bitstreams: 0 | en |
| dc.description.provenance | Made available in DSpace on 2024-11-28T16:13:18Z (GMT). No. of bitstreams: 0 | en |
| dc.description.tableofcontents | Acknowledgements i
摘要 ii Abstract iii Contents v List of Figures viii List of Tables x Chapter 1 Introduction 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Proposed Technique . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Chapter 2 Background and Preliminaries 10 2.1 Quantum Circuit and Device . . . . . . . . . . . . . . . . . . . . . . 10 2.1.1 Logical Quantum Circuit (LQC) . . . . . . . . . . . . . . . . . . . 10 2.1.2 Physical Quantum Device (PQD) . . . . . . . . . . . . . . . . . . . 12 2.2 Dependency Graph (DG) . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3 Reinforcement Learning (RL) . . . . . . . . . . . . . . . . . . . . . 15 2.4 Monte Carlo Tree Search (MCTS) . . . . . . . . . . . . . . . . . . . 17 2.4.1 MCTS RL and QRoute . . . . . . . . . . . . . . . . . . . . . . . . 18 Chapter 3 Previous Works 20 3.1 Gate Number-driven Qubit Routing . . . . . . . . . . . . . . . . . . 20 3.2 Depth-driven Qubit Routing . . . . . . . . . . . . . . . . . . . . . . 21 Chapter 4 Flow Description of LAUREL 23 4.1 MCTS Actor and Environment Execution . . . . . . . . . . . . . . . 25 4.2 MCTS Four Stages in LAUREL . . . . . . . . . . . . . . . . . . . . 26 4.3 Composition of an Action in MCTS Actor . . . . . . . . . . . . . . . 29 Chapter 5 Details of LAUREL 31 5.1 The Qubit Routing Algorithm in LAUREL . . . . . . . . . . . . . . 32 5.2 Preprocessing for the Input and the MDP State . . . . . . . . . . . . 36 5.3 Lookahead Window for Dependency Graph . . . . . . . . . . . . . . 37 5.3.1 Global Lookahead Window (GLW) . . . . . . . . . . . . . . . . . . 39 5.3.2 Local Lookahead Window (LLW) . . . . . . . . . . . . . . . . . . 39 5.3.3 LLW Check . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.4 Chain Lock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.5 Dual Reward Function . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.6 Dual Reward MCTS RL . . . . . . . . . . . . . . . . . . . . . . . . 44 Chapter 6 Experimental Results 48 6.1 Experimental Setups . . . . . . . . . . . . . . . . . . . . . . . . . . 48 6.2 Experimental Results and Discussions . . . . . . . . . . . . . . . . . 51 6.3 Ablation Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Chapter 7 Discussion 58 7.1 TKET Result Discussion . . . . . . . . . . . . . . . . . . . . . . . . 58 7.2 Runtime Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Chapter 8 Conclusion 61 References 62 | - |
| dc.language.iso | en | - |
| dc.subject | 量子繞線 | zh_TW |
| dc.subject | 增強式學習 | zh_TW |
| dc.subject | 蒙地卡羅樹搜尋 | zh_TW |
| dc.subject | 量子邏輯相依性考量 | zh_TW |
| dc.subject | Quantum Logic Dependency Awareness | en |
| dc.subject | Qubit Routing | en |
| dc.subject | Monte Carlo Tree Search | en |
| dc.subject | Reinforcement Learning | en |
| dc.title | 基於蒙地卡羅樹搜尋增強式學習的邏輯考量量子繞線 | zh_TW |
| dc.title | LAUREL: Logic Dependency-Aware Qubit Routing via MCTS-Guided Reinforcement Learning | en |
| dc.type | Thesis | - |
| dc.date.schoolyear | 113-1 | - |
| dc.description.degree | 碩士 | - |
| dc.contributor.oralexamcommittee | 江介宏;李濬屹 | zh_TW |
| dc.contributor.oralexamcommittee | Jie-Hong Roland Jiang;Chun-Yi Lee | en |
| dc.subject.keyword | 量子繞線,蒙地卡羅樹搜尋,增強式學習,量子邏輯相依性考量, | zh_TW |
| dc.subject.keyword | Qubit Routing,Monte Carlo Tree Search,Reinforcement Learning,Quantum Logic Dependency Awareness, | en |
| dc.relation.page | 71 | - |
| dc.identifier.doi | 10.6342/NTU202404432 | - |
| dc.rights.note | 未授權 | - |
| dc.date.accepted | 2024-10-02 | - |
| dc.contributor.author-college | 電機資訊學院 | - |
| dc.contributor.author-dept | 電子工程學研究所 | - |
| 顯示於系所單位： | 電子工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-113-1.pdf 未授權公開取用 | 3.54 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。