針對量子近似優化算法之電路模擬進行效能優化

Abstract

量子近似優化算法（QAOA）是一種應用於解決 NP-hard 組合最佳化問題的量子演算法，利用量子電腦的疊加與糾纏特性，能夠在多項式時間內獲得比傳統演算法更接近的解。然而，在 NISQ（Noise Intermediate-Scale Quantum Era）時代，量子電腦的解近似率受到噪聲和錯誤的影響而大幅降低。相比之下，量子電路模擬器不但能夠在現有的傳統電腦上執行，還能夠提供無噪聲且完整的解機率分佈，因此既容易取得而且在穩定性上優於現有的量子電腦。然而，現有的量子電路模擬器由於缺乏對 QAOA 的優化，模擬速度過於緩慢。為了解決這個問題，本論文通過分析 QAOA 解最大割問題（max-cut）的量子電路模擬，透過數學性質來壓縮整體運算量，並透過位元運算來減少計算負擔，最後進行多線程與 SIMD 指令的優化以提高計算平行度。在實驗結果中，優化後的模擬器能夠在 AMD Ryzen 7965WX 處理器上比經常被使用的 QuEST 模擬器快 19 倍，如此程度的優化能有效支持未來 QAOA 的應用發展。

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.