請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/97780完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 洪士灝 | zh_TW |
| dc.contributor.advisor | Shih-hao Hung | en |
| dc.contributor.author | 邱信瑋 | zh_TW |
| dc.contributor.author | Shin-Wei Chiu | en |
| dc.date.accessioned | 2025-07-16T16:14:31Z | - |
| dc.date.available | 2025-07-17 | - |
| dc.date.copyright | 2025-07-16 | - |
| dc.date.issued | 2025 | - |
| dc.date.submitted | 2025-07-03 | - |
| dc.identifier.citation | [1] Qiskit aer: High‑performance quantum circuit simulation, 2024.
[2] G. Ausiello, A. Marchetti-Spaccamela, P. Crescenzi, G. Gambosi, M. Protasi, and V. Kann. Complexity and Approximation. Springer, 1999. [3] E. Bae and S. Lee. Recursive qaoa outperforms the original qaoa for the max‑cut problem on complete graphs. Quantum Information Processing, 23(3):78, 2024. [4] H. Bayraktar, A. Charara, and D. e. Clark. cuquantum sdk: A high‑performance library for accelerating quantum science, 2023. [5] E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26(5):1411–1473, 1997. [6] F. Black and R. Litterman. Global portfolio optimization. Financial Analysts Journal, 48(5):28–43, 1992. [7] A. Brady and S. van Frank. Layerwise learning for the quantum approximate optimization algorithm. In IEEE Quantum Week 2021, 2021. [8] S. Bravyi and N. Klco. Mitigating device noise in qaoa via adaptive circuit compilation. Physical Review Research, 2022. [9] K. Bui and M. Pham. Particle swarm optimisation of variational quantum circuits. Quantum Science and Technology, 2024. [10] D. Claudino, D. Lyakh, and A. McCaskey. Parallel quantum computing simulations via quantum accelerator platform virtualization. arXiv preprint, 2024. [11] D. Coppersmith. An approximate fourier transform useful in quantum factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 536–545. IEEE, 1994. [12] G. Crooks. Gradients of parameterized quantum gates using the parameter‑shift rule and gate decomposition. Physical Review A, 2019. [13] A. Doi and D. Takahashi. Quantum computing simulator on a heterogeneous hpc system. In Proceedings of HPC Asia 2019, pages 1–9, 2019. [14] Y. Dong, C. Ho, Y. Wang, L. Cincio, and P. Coles. Parameter transfer for quantum approximate optimization of weighted max‑cut. arXiv preprint, 2022. [15] D. Egger, J. Mareček, and S. Woerner. Warm‑starting quantum optimization. Quantum, 5:479, 2021. [16] E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm. arXiv preprint, 2014. [17] E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda. A quantum adiabatic evolution algorithm applied to random instances of an np‑complete problem. Science, 292(5516):472–475, 2001. [18] M. M. Flood. The traveling-salesman problem. Operations research, 4(1):61–75, 1956. [19] L. Grover. A fast quantum mechanical algorithm for database search, 1996. [20] G. Guerreschi and A. Matsuura. Accelerating variational quantum algorithms using machine learning. Quantum Science and Technology, 4(4):045012, 2019. [21] S. Hadfield, Z. Wang, B. O’Gorman, E. Rieffel, D. Santoro, and S. Pakin. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Quantum Science and Technology, 4(1):014004, 2019. [22] C. Hsu, C. Wang, N. Hsu, C. Tu, and S. Hung. Towards scalable quantum circuit simulation via rdma. In Proceedings of RACS ＇23, 2023. [23] S. Imamura, M. Yamazaki, T. Honda, A. Kasagi, A. Tabuchi, H. Nakao, N. Fukumoto, and K. Nakashima. mpiqulacs: A distributed quantum computer simulator for a64fx‑based cluster systems, 2022. [24] T. Jones, A. Brown, I. Bush, and S. Benjamin. Quest and high‑performance simulation of quantum computers. Scientific Reports, 9(1), 2019. [25] T. Kadowaki and H. Nishimori. Quantum annealing: A new method for minimizing multidimensional functions. Chemical Physics Letters, 219(5):343–348, 1994. [26] W. Lavrijsen, A. Tudor, J. Müller, C. Iancu, and W. de Jong. Classical optimizers for noisy intermediate‑scale quantum devices. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 267–277, 2020. [27] Y. Lin, C. Wang, C. Tu, and S. Hung. Towards optimizations of quantum circuit simulation for solving max‑cut problems with qaoa. In Proceedings of SAC＇24, 2024. [28] J. McClean, J. Romero, R. Babbush, and A. Aspuru‑Guzik. The theory of variational hybrid quantum‑classical algorithms. New Journal of Physics, 18(2):023023, 2016. [29] L. Mitchell and R. Shaydulin. Genetic‑algorithm assisted parameter optimisation for qaoa. In HPEC 2023, 2023. [30] C. Z. Mooney. Monte carlo simulation. Number 116. Sage, 1997. [31] T. O’Brien and B. Tarasinski. Noise‑adaptive variational quantum algorithms with reduced measurement requirements. npj Quantum Information, 2022. [32] A. Peruzzo, J. McClean, P. Shadbolt, M. Yung, X. Zhou, P. Love, A. Aspuru‑Guzik, and J. O’Brien. A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 5, 2014. [33] J. Preskill. Quantum computing in the nisq era and beyond. Quantum, 2:79, 2018. [34] C. Reeves. Genetic algorithms. Springer, 2003. [35] R. Shaydulin, A. F. Izmaylov, Y.-H. Chen, and S. Bianco. Parameter setting in quantum approximate optimization of weighted maxcut. Quantum Science and Technology, 7(2):025024, 2022. [36] R. Shaydulin, I. Safro, and J. Larson. Multistart methods for quantum approximate optimization. In 2019 IEEE High Performance Extreme Computing Conference (HPEC), pages 1–8, 2019. [37] P. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–134, 1994. [38] D. Simon. On the power of quantum computation. SIAM Journal on Computing, 26(5):1474–1483, 1997. [39] Y. Tsai, J. Jiang, and C. Jhang. Bit‑slicing the hilbert space: Scaling up accurate quantum circuit simulation to a new level. arXiv preprint, 2020. [40] P. J. Van Laarhoven, E. H. Aarts, P. J. van Laarhoven, and E. H. Aarts. Simulated annealing. Springer, 1987. [41] H. Wang, Y. Ding, J. Gu, Y. Lin, D. Pan, F. Chong, and S. Han. Quantumnas: Noise‑adaptive search for robust quantum circuits. In 2022 IEEE International Symposium on High‑Performance Computer Architecture (HPCA), pages 692–708, 2022. [42] C. Zhang, Z. Song, H. Wang, K. Rong, and J. Zhai. Hyquas: Hybrid partitioner‑based quantum circuit simulation system on gpu. In Proceedings of the ACM International Conference on Supercomputing, pages 443–454, 2021. [43] C. Zhang, H. Wang, Y. Li, Q. Liu, and Z. Chen. Uniq: A unified programming model for efficient quantum circuit simulation. In Proceedings of SC 2022, 2022. [44] L. Zhou, S. Wang, S. Choi, H. Pichler, and M. Lukin. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near‑term devices. Physical Review X, 10(2):021067, 2020. [45] S. Zhu, X. Luo, and Z. Sun. p‑swap: Efficient depth expansion for qaoa. Quantum, 7:1104, 2023. | - |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/97780 | - |
| dc.description.abstract | 本研究開發了一款資源高效的量子電路模擬器，專為在大規模組合優化問題上執行量子近似優化算法 (QAOA) 而設計。我們的核心貢獻在於整合了狀態向量轉置 (State Vector Transposition, SVT) 技術。這項技術透過在跨節點或跨裝置傳輸前執行本地端的量子位元（Qubit）重排，能有效集中傳輸所需的狀態向量區塊。此方法不僅顯著提升了傳輸效率，更有效減輕了模擬大型量子電路所固有的記憶體需求，大幅提升了模擬性能。這種方法有助於在多樣化的分散式計算平台（包括多節點 CPU 和多設備 GPU 架構）上實現高效的擴展。實驗驗證突顯了我們提出的模擬器卓越的性能。在大規模 QAOA 電路上的基準測試表明，與現有最先進的模擬器相比，我們的模擬器實現了顯著的加速，在GPU 平台上性能提升高達 1490 倍，在純 CPU 環境中提升 28 倍。此外，我們進行全面的可擴展性實驗證實了模擬器在分散式計算環境中保持接近最佳效率的能力。這種可擴展性使我們的工作成為模擬深度 QAOA 電路的寶貴工具，有效地彌合了當前經典計算資源的能力與量子算法研究日益增長的需求之間的差距，成功縮短了經典計算資源與量子算法研究需求之間的鴻溝。最後，我們亦針對 SVT 技術進行全面效能分析，確認其在 QAOA 模擬中的最佳化效益。 | zh_TW |
| dc.description.abstract | This study presents a resource-efficient quantum-circuit simulator purpose-built for running the Quantum Approximate Optimization Algorithm (QAOA) on large-scale combinatorial-optimization problems. Our key contribution is the integration of a State Vector Transposition (SVT) technique. By locally reordering qubits before inter-node or inter-device communication, SVT concentrates the state-vector blocks that actually need to be transferred, dramatically improving data-transfer efficiency while easing the memory footprint inherent to large-circuit simulation. The result is a substantial performance boost and seamless scalability across heterogeneous distributed platforms, including multi-node CPU clusters and multi-device GPU systems. Extensive experiments underscore the superior performance of the simulator. On large QAOA benchmarks, it outperforms state-of-the-art simulators by up to 1,490× on GPUs and 28× on CPUs. Scalability studies further show that the simulator maintains near-optimal parallel efficiency in distributed environments, making it a powerful tool for simulating deep QAOA circuits and closing the gap between classical computing capabilities and the rapidly growing demands of quantum-algorithm research. Finally, a thorough performance analysis confirms the optimization benefits of SVT within QAOA simulations. | en |
| dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2025-07-16T16:14:31Z No. of bitstreams: 0 | en |
| dc.description.provenance | Made available in DSpace on 2025-07-16T16:14:31Z (GMT). No. of bitstreams: 0 | en |
| dc.description.tableofcontents | Verification Letter from the Oral Examination Committee . . . . . . . . . . . . . i
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii 摘要 . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . iii Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi List of Figures . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . viii List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 1 Chapter 2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1 Quantum Approximate Optimization Algorithm . . . . . . . . . . . . . . . . . 5 2.2 Combinatorial Optimization Problems . . . . . . . . . . . . . . . . . . . . . 7 2.3 Using QAOA to solve Max-Cut Problem . . . . . . . . . . . . . . . . . . . . . 8 2.4 State Vector Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Chapter 3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.1 Algorithmic Advances in QAOA . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 Classical Parameter‑Search and Co‑Processing . . . . . . . . . . . . . . . . 13 3.3 Noise‑Aware and Hybrid Variants . . . . . . . . . . . . . . . . . . . . . . 13 3.4 Quantum Circuit Simulators for QAOA . . . . . . . . . . . . . . . . . . . . 14 3.5 Cluster‑Level Optimisations for Large‑Scale QAOA . . . . . . . . . . . . . . 15 Chapter 4 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.1 Quantum Approximate Optimization Algorithm Preliminaries . . . . . . . . . . 16 4.2 State Vector Transposition . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2.1 Global Qubit Swap with Local MSB . . . . . . . . . . . . . . . . . . . . . 19 4.2.2 Case 2: Global Qubit Swap with Non-Local MSB . . . . . . . . . . . . . . . 23 Chapter 5 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.1 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.3 Scalability Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.4 State Vector Transposition Analysis . . . . . . . . . . . . . . . . . . . . 41 5.5 Buffer Tuning for State Vector Transposition . . . . . . . . . . . . . . . . 44 Chapter 6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 | - |
| dc.language.iso | en | - |
| dc.subject | 量子近似演算法 | zh_TW |
| dc.subject | 平行計算 | zh_TW |
| dc.subject | 量子計算 | zh_TW |
| dc.subject | 組合優化問題 | zh_TW |
| dc.subject | 量子模擬 | zh_TW |
| dc.subject | 效能分析 | zh_TW |
| dc.subject | Performance analysis | en |
| dc.subject | Quantum approximate optimization algorithm (QAOA) | en |
| dc.subject | Quantum computing | en |
| dc.subject | Quantum circuit simulation | en |
| dc.subject | Combinatorial optimization problem | en |
| dc.subject | Parallel programming | en |
| dc.title | 利用計算叢集優化 QAOA 的大規模模擬 | zh_TW |
| dc.title | Optimizing Large-Scale QAOA Simulation using Computing Clusters | en |
| dc.type | Thesis | - |
| dc.date.schoolyear | 113-2 | - |
| dc.description.degree | 碩士 | - |
| dc.contributor.oralexamcommittee | 江介宏;涂嘉恒 | zh_TW |
| dc.contributor.oralexamcommittee | Jie-Hong Roland Jiang;Chia-Heng Tu | en |
| dc.subject.keyword | 量子近似演算法,量子計算,量子模擬,組合優化問題,平行計算,效能分析, | zh_TW |
| dc.subject.keyword | Quantum approximate optimization algorithm (QAOA),Quantum computing,Quantum circuit simulation,Combinatorial optimization problem,Parallel programming,Performance analysis, | en |
| dc.relation.page | 53 | - |
| dc.identifier.doi | 10.6342/NTU202501430 | - |
| dc.rights.note | 同意授權(全球公開) | - |
| dc.date.accepted | 2025-07-04 | - |
| dc.contributor.author-college | 電機資訊學院 | - |
| dc.contributor.author-dept | 資訊工程學系 | - |
| dc.date.embargo-lift | 2025-07-17 | - |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-113-2.pdf | 2.83 MB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。