可擴展且可平行的 QAOA 模擬器，用於解決背包問題

Abstract

本論文旨在解決量子近似優化演算法（QAOA）在傳統電腦上模擬的效能瓶頸，我們針對背包問題開發了一套高效能平行模擬器。核心創新包含兩點：一、名為「依需求張量積」的電路模擬技術，可將無糾纏電路的複雜度從指數級降至線性級 (O(n)) ; 而對於更複雜的 Copula 混合器，也能帶來 n 倍的理論加速。二、我們提出一種「漸進式搜索」（Progressive Search）策略，透過二階段的由粗至精搜索，將參數優化效率提升超過 7 倍，同時對最終的解品質影響極小。 結合上述創新與多 GPU 平行化，本研究成功將模擬規模從過去的 10 個量子位元擴展至 100 個，並將數小時的計算縮短至數秒內，總體效能提升超過 400 倍。此外，本研究根據問題規模，為 Copula 與沙漏（Hourglass）兩種混合器的選擇提供了實用的效能與精度權衡建議。

This thesis addresses the performance bottlenecks in classical simulations of the Quantum Approximate Optimization Algorithm (QAOA) at depth p=1 by developing a high-performance, parallel simulator for the Knapsack Problem. Its core innovations are twofold: 1) A ”Tensor Product on Demand” circuit simulation technique that reduces complexity from exponential to linear (O(n)) for entangle-free circuits and provides an n-fold speedup for complex mixers. 2) A ”Progressive Search” strategy that improves parameter optimization efficiency by over 7x through a two-phase search while having a negligible impact on the final solution quality. Integrating these innovations with multi-GPU parallelization, our work successfully scales simulations from the previous 10-qubit limit to 100 qubits. This slashes computation times from hours to seconds, achieving an overall performance gain of over 400x. The research also provides practical guidance on the trade-offs between the Copula and Hourglass mixers, depending on problem scale, for balancing performance and accuracy.