作為二元優化問題的質因數分解

Abstract

儘管Shor演算法藉由量子計算為質因數分解提供了一條新途徑，但對量子位元的數量和精度上的要求使該方法在不久的將來內難以實用化。在本論文中，我們將介紹三種與量子近似優化算法（QAOA）和量子退火——兩種有望在近期的量子設備上實現的優化算法——相容的整數分解方法。對於直接乘法方法和長乘法方法，我們將展示在最多29位元的質因數分解問題中所需的變量數量以及係數大小。對於次線性資源量子質因數分解（SQIF）算法，我們則將展示SQIF算法在先前研究的假設下的時間複雜度，並驗證這些假設以及SQIF算法有效性。

Although Shor’s algorithm provides a new avenue for integer factoring through quantum computation, the required qubit number and precision are too demanding for the the method to be practical in the near future. In this thesis, we will introduce three different integer factoring methods that are compatible with quantum approximate optimization algorithm (QAOA) and quantum annealing - two promising optimization algorithms that can be implemented on noisy quantum devices in the near term. For the direct multiplication method and the long multiplication method, we will show the variable usage as well as the magnitude of coefficients for problems up to 29-bit. For the sublinear-resource quantum integer factoring (SQIF) algorithm, we will show the time complexity of the SQIF algorithm in terms of problem integer N and approximation factor γ under the assumptions of previous works, and provide evidence against said assumptions and thus the effectiveness of the SQIF algorithm.