請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/94388完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 洪士灝 | zh_TW |
| dc.contributor.advisor | Shih-Hao Hung | en |
| dc.contributor.author | 林祐丞 | zh_TW |
| dc.contributor.author | Yu-Cheng Lin | en |
| dc.date.accessioned | 2024-08-15T17:13:16Z | - |
| dc.date.available | 2024-08-16 | - |
| dc.date.copyright | 2024-08-15 | - |
| dc.date.issued | 2024 | - |
| dc.date.submitted | 2024-08-07 | - |
| dc.identifier.citation | Quantum annealing: A new method for minimizing multidimensional functions. Chemical Physics Letters, 219(5):343–348, 1994.
M. Alam, A. Ash-Saki, and S. Ghosh. Circuit compilation methodologies for quan tum approximate optimization algorithm. In 2020 53rd Annual IEEE/ACM Interna tional Symposium on Microarchitecture (MICRO), pages 215–228, 2020. M. Alam, A. Ash-Saki, and S. Ghosh. Design-space exploration of quantum approx imate optimization algorithm under noise. In 2020 IEEE Custom Integrated Circuits Conference (CICC), pages 1–4, 2020. M. Alam, A. Ash-Saki, J. Li, A. Chattopadhyay, and S. Ghosh. Noise resilient com pilation policies for quantum approximate optimization algorithm. In 2020 IEEE/ACM International Conference On Computer Aided Design (ICCAD), pages 1–7, 2020. M. Alam, A. A. Saki, and S. Ghosh. An efficient circuit compilation flow for quan tum approximate optimization algorithm. In 2020 57th ACM/IEEE Design Automa tion Conference (DAC), pages 1–6, 2020. G. Ausiello, A. Marchetti-Spaccamela, P. Crescenzi, G. Gambosi, M. Protasi, and V. Kann. Complexity and Approximation. Springer, 1999. E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal on Com puting, 26(5):1411–1473, 1997. F. Black and R. Litterman. Global portfolio optimization. Financial analysts journal, 48(5):28–43, 1992. X. Bonet-Monroig, H. Wang, D. Vermetten, B. Senjean, C. Moussa, T. Bäck, V. Dun jko, and T. E. O’Brien. Performance comparison of optimization methods on varia tional quantum algorithms. Phys. Rev. A, 107:032407, Mar 2023. 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. 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. Cirq Developers. Cirq, 2024. G. E. Crooks. Performance of the quantum approximate optimization algorithm on the maximum cut problem, 2018. E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algo rithm, 2014. E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda. A quan tum adiabatic evolution algorithm applied to random instances of an np-complete problem. Science, 292(5516):472–475, 2001. 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. M. M. Flood. The traveling-salesman problem. Operations research, 4(1):61–75, 1956. F. G. Fuchs, K. O. Lye, H. Møll Nilsen, A. J. Stasik, and G. Sartor. Constraint preserving mixers for the quantum approximate optimization algorithm. Algorithms, 15(6), 2022. A. Galda, X. Liu, D. Lykov, Y. Alexeev, and I. Safro. Transferability of optimal qaoa parameters between random graphs, 2021. V. Gheorghiu. Quantum++: A modern c++ quantum computing library. PLOS ONE, 13(12):e0208073, dec 2018. M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115–1145, nov 1995. L. K. Grover. A fast quantum mechanical algorithm for database search, 1996. S. Hadfield, Z. Wang, B. O＇Gorman, E. G. Rieffel, D. Venturelli, and R. Biswas. From the quantum approximate optimization algorithm to a quantum alternating op erator ansatz. Algorithms, 12(2), 2019. A. Hashim, R. Rines, V. Omole, R. K. Naik, J. M. Kreikebaum, D. I. Santiago, F. T. Chong, I. Siddiqi, and P. Gokhale. Optimized swap networks with equivalent circuit averaging for qaoa. Phys. Rev. Res., 4:033028, Jul 2022. R. Herrman, P. C. Lotshaw, J. Ostrowski, T. S. Humble, and G. Siopsis. Multi-angle quantum approximate optimization algorithm, 2021. J. Hirvonen, J. Rybicki, S. Schmid, and J. Suomela. Large cuts with local algorithms on triangle-free graphs, 2014. N. Jain, B. Coyle, E. Kashefi, and N. Kumar. Graph neural network initialisation of quantum approximate optimisation. Quantum, 6:861, Nov. 2022. T. Jones, A. Brown, I. Bush, and S. C. Benjamin. QuEST and high performance simulation of quantum computers. Scientific Reports, 9(1), jul 2019. H. Koike. Optimization of simulation of quantum circuits as an undirected graphical model. Master’s thesis, National Taiwan University, Mar. 2023. P. C. Lotshaw, T. S. Humble, R. Herrman, J. Ostrowski, and G. Siopsis. Empirical performance bounds for quantum approximate optimization. Quantum Information Processing, 20(12), nov 2021. R. Majumdar, D. Madan, D. Bhoumik, D. Vinayagamurthy, S. Raghunathan, and S. Sur-Kolay. Optimizing ansatz design in qaoa for max-cut, 2021. J. Marshall, F. Wudarski, S. Hadfield, and T. Hogg. Characterizing local noise in QAOA circuits. IOP SciNotes, 1(2):025208, aug 2020. G. B. Mbeng, R. Fazio, and G. Santoro. Quantum annealing: a journey through digitalization, control, and hybrid quantum variational schemes, 2019. C. Z. Mooney. Monte carlo simulation. Number 116. Sage, 1997. W. Mula, N. Kurz, and D. Lemire. Faster population counts using AVX2 instructions. CoRR, abs/1611.07612, 2016. G. Pagano, A. Bapat, P. Becker, K. S. Collins, A. De, P. W. Hess, H. B. Kaplan, A. Kyprianidis, W. L. Tan, C. Baldwin, L. T. Brady, A. Deshpande, F. Liu, S. Jordan, A. V. Gorshkov, and C. Monroe. Quantum approximate optimization of the long range ising model with a trapped-ion quantum simulator. Proceedings of the National Academy of Sciences, 117(41):25396–25401, oct 2020. 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. C. Reeves. Genetic algorithms. Springer, 2003. P. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–134, 1994. D. R. Simon. On the power of quantum computation. SIAM Journal on Computing, 26(5):1474–1483, 1997. M. Smelyanskiy, N. P. D. Sawaya, and A. Aspuru-Guzik. qhipster: The quantum high performance software testing environment, 2016. D. S. Steiger, T. Häner, and M. Troyer. ProjectQ: an open source software framework for quantum computing. Quantum, 2:49, jan 2018. R. Sweke, F. Wilde, J. Meyer, M. Schuld, P. K. Faehrmann, B. Meynard-Piganeau, and J. Eisert. Stochastic gradient descent for hybrid quantum-classical optimization. Quantum, 4:314, aug 2020. The cuQuantum development team. Nvidia cuquantum sdk, 2023. P. J. Van Laarhoven, E. H. Aarts, P. J. van Laarhoven, and E. H. Aarts. Simulated annealing. Springer, 1987. Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel. Quantum approximate optimization algorithm for MaxCut: A fermionic view. Physical Review A, 97(2), feb 2018. J. Wurtz and P. Love. Maxcut quantum approximate optimization algorithm perfor mance guarantees for p > 1. Phys. Rev. A, 103:042612, Apr 2021. J. Wurtz and P. J. Love. Counterdiabaticity and the quantum approximate optimiza tion algorithm. Quantum, 6:635, jan 2022. 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. L. Zhu, H. L. Tang, G. S. Barron, F. A. Calderon-Vargas, N. J. Mayhall, E. Barnes, and S. E. Economou. An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer, 2022. | - |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/94388 | - |
| dc.description.abstract | 量子近似優化算法（QAOA）是一種應用於解決 NP-hard 組合最佳化問題的量子演算法，利用量子電腦的疊加與糾纏特性，能夠在多項式時間內獲得比傳統演算法更接近的解。然而，在 NISQ（Noise Intermediate-Scale Quantum Era）時代，量子電腦的解近似率受到噪聲和錯誤的影響而大幅降低。相比之下，量子電路模擬器不但能夠在現有的傳統電腦上執行，還能夠提供無噪聲且完整的解機率分佈，因此既容易取得而且在穩定性上優於現有的量子電腦。然而，現有的量子電路模擬器由於缺乏對 QAOA 的優化，模擬速度過於緩慢。為了解決這個問題，本論文通過分析 QAOA 解最大割問題（max-cut）的量子電路模擬，透過數學性質來壓縮整體運算量，並透過位元運算來減少計算負擔，最後進行多線程與 SIMD 指令的優化以提高計算平行度。在實驗結果中，優化後的模擬器能夠在 AMD Ryzen 7965WX 處理器上比經常被使用的 QuEST 模擬器快 19 倍，如此程度的優化能有效支持未來 QAOA 的應用發展。 | zh_TW |
| dc.description.abstract | Quantum approximate optimization algorithm (QAOA) is one of the popular quantum algorithms that are used to solve combinatorial optimization problems via approximations. QAOA is able to be evaluated on both physical and virtual quantum computers simulated by classical computers, with virtual ones being favored for their noise-free feature and availability. Nevertheless, performing QAOA on virtual quantum computers suffers from a slow simulation speed for solving combinatorial optimization problems which require large-scale quantum circuit simulation (QCS). In this thesis, we propose techniques to accelerate QCS for QAOA using mathematical optimizations to compress quantum operations, incorporating efficient bitwise operations to further lower the computational complexity, and leveraging different levels of parallelisms from modern multi-core processors, with a study case to show the effectiveness on solving max-cut problems. The experimental results reveal substantial performance improvements, surpassing commonly-used simulator, QuEST, by a factor of 19 on a virtual quantum computer running on a 24-core, 48-thread AMD Ryzen 9 7965WX processor. We believe that this work opens up new possibilities for accelerating various QAOA applications. | en |
| dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2024-08-15T17:13:16Z No. of bitstreams: 0 | en |
| dc.description.provenance | Made available in DSpace on 2024-08-15T17:13:16Z (GMT). No. of bitstreams: 0 | en |
| dc.description.tableofcontents | Acknowledgements i
摘要 ii Abstract iii Contents v List of Figures vii List of Tables viii Chapter 1 Introduction 1 Chapter 2 Background and Related Work 5 2.1 Quadratic Unconstrained Binary Optimization (QUBO) and Ising Model 5 2.2 The Max-Cut Problem 6 2.3 Solving QUBO Problem with QAOA 8 2.3.1 Formal Description 9 2.3.2 Circuit Simulation for QAOA 11 2.3.3 Initial Layer 12 2.3.4 Cost Layer 12 2.3.5 Mixer Layer 13 2.4 Related Work 13 2.4.1 Algorithm Improvement 13 2.4.2 Approximation Quality Analysis 14 2.4.3 Noise and Error Analysis 14 2.4.4 Quantum Circuit Simulators 15 2.4.5 Differences in this Work 15 Chapter 3 Methodology 17 3.1 The QAOA Simulation 17 3.2 Mathematical Optimizations 19 3.2.1 Rotation Compression 20 3.2.2 Launch Control 22 3.3 Unweighted Graph Optimization 22 3.4 Parallel Optimization 24 Chapter 4 Evaluation 26 4.1 Experimental Setup 26 4.2 Multicore Processor 28 4.3 Manycore Processor 30 4.4 Approximation Result Quality 32 Chapter 5 Conclusion 34 References 35 | - |
| 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 | AVX instructions | en |
| dc.subject | QAOA | en |
| dc.subject | MaxCut | en |
| dc.subject | Parallel Programming | en |
| dc.subject | Optimization | en |
| dc.subject | GPU | en |
| dc.title | 針對量子近似優化算法之電路模擬進行效能優化 | zh_TW |
| dc.title | Performance Optimization of Full-State Quantum Circuit Simulation for Quantum Approximate Optimization Algorithms | en |
| dc.type | Thesis | - |
| dc.date.schoolyear | 112-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 | QAOA,MaxCut,Parallel Programming,Optimization,GPU,AVX instructions, | en |
| dc.relation.page | 40 | - |
| dc.identifier.doi | 10.6342/NTU202403662 | - |
| dc.rights.note | 同意授權(限校園內公開) | - |
| dc.date.accepted | 2024-08-10 | - |
| dc.contributor.author-college | 電機資訊學院 | - |
| dc.contributor.author-dept | 資訊工程學系 | - |
| dc.date.embargo-lift | 2029-08-07 | - |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-112-2.pdf 未授權公開取用 | 637.91 kB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。