請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/97727完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 洪士灝 | zh_TW |
| dc.contributor.advisor | Shih-Hao Hung | en |
| dc.contributor.author | 楊卓敏 | zh_TW |
| dc.contributor.author | Chuo-Min Yang | en |
| dc.date.accessioned | 2025-07-16T16:04:10Z | - |
| 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] Quantum annealing: A new method for minimizing multidimensional functions. Chemical Physics Letters, 219(5):343–348, 1994.
[2] Aer - high performance quantum circuit simulation for qiskit. https://github.com/Qiskit/qiskit-aer, 2024. [3] G. Ausiello, A. Marchetti-Spaccamela, P. Crescenzi, G. Gambosi, M. Protasi, and V. Kann. Complexity and Approximation. Springer, 1999. [4] H. Bayraktar, A. Charara, D. Clark, S. Cohen, T. Costa, Y.-L. L. Fang, Y. Gao, J. Guan, J. Gunnels, A. Haidar, A. Hehn, M. Hohnerbach, M. Jones, T. Lubowe, D. Lyakh, S. Morino, P. Springer, S. Stanwyck, I. Terentyev, S. Varadhan, J. Wong, and T. Yamaguchi. 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] M. Chalupnik, H. Melo, Y. Alexeev, and A. Galda. Augmenting qaoa ansatz with multiparameter problem-independent layer. In 2022 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 97–103, 2022. [8] P. Chandarana, N. N. Hegade, K. Paul, F. Albarrán-Arriagada, E. Solano, A. del Campo, and X. Chen. Digitized-counterdiabatic quantum approximate optimization algorithm. Phys. Rev. Res., 4:013141, Feb 2022. [9] K.-C. Chen, X. Xu, F. Burt, C.-Y. Liu, S. Yu, and K. K. Leung. Noise-aware distributed quantum approximate optimization algorithm on near-term quantum hardware. In 2024 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 2, pages 144–149. IEEE, 2024. [10] E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm, 2014. [11] 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. [12] M. Fernández-Pendás, E. F. Combarro, S. Vallecorsa, J. Ranilla, and I. F. Rúa. A study of the performance of classical minimizers in the quantum approximate optimization algorithm. Journal of Computational and Applied Mathematics, 404:113388, 2022. [13] A. Galda, X. Liu, D. Lykov, Y. Alexeev, and I. Safro. Transferability of optimal qaoa parameters between random graphs, 2021. [14] L. K. Grover. A fast quantum mechanical algorithm for database search, 1996. [15] K. Gupta. Combinatorial optimization and application to DNA sequence analysis. Georgia Institute of Technology, 2008. [16] R. Herrman, P. C. Lotshaw, J. Ostrowski, T. S. Humble, and G. Siopsis. Multi-angle quantum approximate optimization algorithm, 2021. [17] C.-H. Hsu, C.-C. Wang, N.-W. Hsu, C.-H. Tu, and S.-H. Hung. Towards scalable quantum circuit simulation via rdma. RACS ’23, New York, NY, USA, 2023. Association for Computing Machinery. [18] N.-W. Hsu, C.-C. Wang, C.-H. Hsu, C.-H. Tu, and S.-H. Hung. Toward cost-effective quantum circuit simulation with performance tuning techniques. Connection Science, 36(1):2349541, 2024. [19] 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. [20] N. Jain, B. Coyle, E. Kashefi, and N. Kumar. Graph neural network initialisation of quantum approximate optimisation. Quantum, 6:861, Nov. 2022. [21] T. Jones, A. Brown, I. Bush, and S. C. Benjamin. Quest and high performance simulation of quantum computers. Scientific Reports, 9(1), July 2019. [22] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014. [23] Y.-C. Lin, C.-C. Wang, C.-H. Tu, and S.-H. Hung. Towards optimizations of quantum circuit simulation for solving max-cut problems with qaoa. In Proceedings of the 39th ACM/SIGAPP Symposium on Applied Computing, SAC’24. ACM, Apr. 2024. [24] R. Nagothanekar, D. Kharode, and S. Ghosh. Combinatorial optimization for travelling salesman and vehicle routing problem. In 2022 International Conference on Computing, Communication, Security and Intelligent Systems (IC3SIS), pages 1–5. IEEE, 2022. [25] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien. A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 5(1), jul 2014. [26] J. Preskill. Quantum computing in the nisq era and beyond. Quantum, 2, 01 2018. [27] S. J. Reddi, S. Kale, and S. Kumar. On the convergence of adam and beyond. arXiv preprint arXiv:1904.09237, 2019. [28] P. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–134, 1994. [29] D. R. Simon. On the power of quantum computation. SIAM Journal on Computing, 26(5):1474–1483, 1997. [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, 6(1):014003, 2020. [31] W. Tang, T. Tomesh, M. Suchara, J. Larson, and M. Martonosi. Cutqc: using small quantum computers for large quantum circuit evaluations. In Proceedings of the 26th ACM International conference on architectural support for programming languages and operating systems, pages 473–486, 2021. [32] C. Wang. An overview of spsa: recent development and applications. arXiv preprint arXiv:2012.06952, 2020. [33] Y. S. Weinstein, M. Pravia, E. Fortunato, S. Lloyd, and D. G. Cory. Implementation of the quantum fourier transform. Physical review letters, 86(9):1889, 2001. [34] J. Wurtz and P. J. Love. Counterdiabaticity and the quantum approximate optimization algorithm. Quantum, 6:635, jan 2022. [35] 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, page 443–454, New York, NY, USA, 2021. Association for Computing Machinery. [36] C. Zhang, H. Wang, Y. Li, Q. Liu, and Z. Chen. Uniq: A unified programming model for efficient quantum circuit simulation. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC). IEEE, November 2022. [37] L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Phys. Rev. X, 10:021067, Jun 2020. | - |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/97727 | - |
| dc.description.abstract | 本論文旨在解決量子近似最佳化演算法（Quantum Approximate Optimization Algorithm, QAOA）在傳統電腦上模擬的效能瓶頸。先前的研究已對Cost Layer進行優化，使得模擬的效能瓶頸轉移至Mixer Layer 並更加明顯。本論文的目的在於解決傳統電腦上模擬QAOA所面臨的這一新瓶頸。為此，本研究提出兩項核心技術：一是Cache Resident State Operation（CRSO），透過分割狀態向量以提升資料局部性與快取使用效率；二是導入「單指令多資料流」（SIMD）向量化，以加速CPU平台的算術運算效能。本研究的整合性方法取得了顯著的效能提升。評測結果顯示，在34個量子位元的模擬中，本模擬器在單一CPU節點上的執行速度相較於其他頂尖量子電路模擬器提升了最多27倍；在32個量子位元的模擬中，在單一GPU上的執行速度也提高了約13倍。此成果證明，結合考量硬體特性的演算法優化策略，能為複雜量子電路的模擬帶來顯著的效能優勢，並為相關領域的未來研究奠定穩固基礎。 | zh_TW |
| dc.description.abstract | This thesis tackles the remaining bottlenecks in classical Quantum Approximate Optimization Algorithm (QAOA) simulation, most notably in the mixer layer, by introducing two key techniques (1) Cache-Resident State Operation (CRSO), which partitions the state vector for better data locality and cache efficiency and (2) SIMD vectorization to accelerate CPU arithmetic. Together, these hardware-aware optimizations boost performance by up to 27x on a single-node CPU for 34-qubit circuits and 13x on a single GPU for 32-qubit circuits, laying a strong foundation for future high-performance quantum-circuit simulation research. | en |
| dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2025-07-16T16:04:10Z No. of bitstreams: 0 | en |
| dc.description.provenance | Made available in DSpace on 2025-07-16T16:04:10Z (GMT). No. of bitstreams: 0 | en |
| dc.description.tableofcontents | Verification Letter from the Oral Examination Committee i
Acknowledgements ii 摘要 iii Abstract iv Contents v List of Figures vii List of Tables viii Chapter 1 Introduction 1 Chapter 2 Background & Challenges 6 2.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.1 The Max-Cut Problem . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.2 Solving the Max-Cut problem with QAOA . . . . . . . . . . . . . . 8 2.1.3 Evaluating QAOA Solution Quality . . . . . . . . . . . . . . . . . 11 2.2 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.1 Challenges in Noisy Quantum Hardware . . . . . . . . . . . . . . . 12 2.2.2 Challenges of Quantum Circuit Simulations . . . . . . . . . . . . . 13 Chapter 3 Related Work 14 3.1 Improvements to QAOA algorithms . . . . . . . . . . . . . . . . . . 14 3.2 Quantum Circuit Simulation . . . . . . . . . . . . . . . . . . . . . . 15 Chapter 4 Methodology 18 4.1 Preliminary Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2 Cache-Resident State Operation . . . . . . . . . . . . . . . . . . . . 21 4.3 SIMD Vectorization for CPU Implementation . . . . . . . . . . . . . 24 Chapter 5 Evaluation 27 5.1 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . 28 5.3 SIMD Optimization on CPU-only platform . . . . . . . . . . . . . . 31 5.4 Performance Tuning . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Chapter 6 Conclusion 36 References 37 | - |
| dc.language.iso | en | - |
| dc.subject | 量子近似最佳化演算法 | zh_TW |
| dc.subject | 量子電路模擬 | zh_TW |
| dc.subject | 高效能計算 | zh_TW |
| dc.subject | Quantum Circuit Simulation | en |
| dc.subject | High Performance Computing | en |
| dc.subject | Quantum Approximate Optimization Algorithm | en |
| dc.title | 針對全狀態QAOA 電路模擬之混合層的效能導向最佳化研究 | zh_TW |
| dc.title | Performance-Driven Mixer Layer Optimization in Full-State QAOA Circuit Simulation | 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 | High Performance Computing,Quantum Approximate Optimization Algorithm,Quantum Circuit Simulation, | en |
| dc.relation.page | 41 | - |
| dc.identifier.doi | 10.6342/NTU202501429 | - |
| 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 | 1.29 MB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。