Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/91499Full metadata record
| ???org.dspace.app.webui.jsptag.ItemTag.dcfield??? | Value | Language |
|---|---|---|
| dc.contributor.advisor | 管希聖 | zh_TW |
| dc.contributor.advisor | Hsi-Sheng Goan | en |
| dc.contributor.author | 鍾皓宇 | zh_TW |
| dc.contributor.author | Hao-Yu Chung | en |
| dc.date.accessioned | 2024-01-28T16:16:34Z | - |
| dc.date.available | 2024-01-29 | - |
| dc.date.copyright | 2024-01-27 | - |
| dc.date.issued | 2023 | - |
| dc.date.submitted | 2023-08-02 | - |
| dc.identifier.citation | [1] B. Yan, Z. Tan, S. Wei, H. Jiang, W. Wang, H. Wang, L. Luo, Q. Duan, Y. Liu, W. Shi, et al., Factoring integers with sublinear resources on a superconducting quantum processor (2022), 2212.12372.
[2] C. P. Schnorr, Fast factoring integers by svp algorithms, corrected, Cryptology ePrint Archive, Paper 2021/933 (2021), https://eprint.iacr.org/2021/933, URL https://eprint.iacr.org/2021/933. [3] R. L. Rivest, A. Shamir, and L. Adleman, Communications of the ACM 21, 120 (1978), URL https://doi.org/10.1145/359340.359342. [4] C. Pomerance, in Algorithmic Number Theory (Cambridge University Press, 2008), vol. 44 of MSRI Publications, pp. 69–81. [5] C. Pomerance and P. Erd¨os, Notices of the AMS 43, 1473 (1996). [6] A. K. Lenstra, in Encyclopedia of Cryptography and Security (Springer US, 2011), pp. 611–618, URL https://doi.org/10.1007/978-1-4419-5906-5_455. [7] J. P. Buhler, H. W. Lenstra, and C. Pomerance, in Lecture Notes in Mathematics (Springer Berlin Heidelberg, 1993), pp. 50–94, URL https://doi.org/10.1007/bfb0091539. [8] P. Shor, in Proceedings 35th Annual Symposium on Foundations of Computer Science (IEEE Comput. Soc. Press, 1994), URL https://doi.org/10.1109/sfcs.1994.365700. [9] X. Peng, Z. Liao, N. Xu, G. Qin, X. Zhou, D. Suter, and J. Du, Physical Review Letters 101 (2008), URL https://doi.org/10.1103/physrevlett.101.220405. [10] E. R. Anschuetz, J. P. Olson, A. Aspuru-Guzik, and Y. Cao, Variational quantum factoring (2018), 1808.08927. [11] S. Pal, S. Moitra, V. S. Anjusha, A. Kumar, and T. S. Mahesh, Pramana 92 (2019), URL https://doi.org/10.1007/s12043-018-1684-0. [12] E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm (2014), 1411.4028. [13] T. Kato, Journal of the Physical Society of Japan 5, 435 (1950), URL https://doi.org/10.1143/jpsj.5.435. [14] C. McGeoch and P. Farr´e, D-Wave Technical Report Series, D-Wave Systems Inc. (2020). [15] P. d. Fermat, J. d. Billy, J. Wallis, P. Tannery, C. Henry, and C. d. Waard, Oeuvres de Fermat, vol. 2 (Gauthier-Villars, 1891). [16] J. D. Dixon, Mathematics of Computation 36, 255 (1981), URL https://doi.org/10.1090/s0025-5718-1981-0595059-1. [17] C. Pomerance, Computational Methods in Number Theory 0, 89 (1982), URL https://cir.nii.ac.jp/crid/1570009750725490304. [18] P. Stevenhagen, in Algorithmic Number Theory (Cambridge University Press, 2008), vol. 44 of MSRI Publications, pp. 83–100. [19] M. E. Briggs, An introduction to the general number field sieve (1998). [20] D. Beckman, A. N. Chari, S. Devabhaktuni, and J. Preskill, Physical Review A 54, 1034 (1996), URL https://doi.org/10.1103/physreva.54.1034. [21] D. Harvey and J. van der Hoeven, Annals of Mathematics 193 (2021), URL https://doi.org/10.4007/annals.2021.193.2.4. [22] G. Schaller and R. Sch¨utzhold, The role of symmetries in adiabatic quantum algorithms (2009), 0708.1882. [23] B. Wang, F. Hu, H. Yao, and C. Wang, Scientific Reports 10 (2020), URL https://doi.org/10.1038/s41598-020-62802-5. [24] S. Isakov, I. Zintchenko, T. Rønnow, and M. Troyer, Computer Physics Communications 192, 265 (2015), ISSN 0010-4655, URL https://www.sciencedirect.com/science/article/pii/S0010465515000727. [25] P. Q. Nguyen, in The LLL Algorithm (Springer Berlin Heidelberg, 2009), pp. 19–69, URL https://doi.org/10.1007/978-3-642-02295-1_2. [26] L. Babai, Combinatorica 6, 1 (1986), URL https://doi.org/10.1007/bf02579403. [27] N. Stephens-Davidowitz, 5.1 the closest vector problem - noahsd.com (2016), URL http://www.noahsd.com/mini_lattices/05__babai.pdf. [28] A. K. Lenstra, H. W. Lenstra, and L. Lov´asz, Mathematische Annalen 261, 515 (1982), URL https://doi.org/10.1007/bf01457454. [29] R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth, Advances in Computational Mathematics 5, 329 (1996), URL https://doi.org/10.1007/bf02124750. [30] L. Ducas, Lattices & factoring, The International Conference on Practice and Theory in Public Key Cryptography (2021), URL https://pkc.iacr.org/2021/files/ducas.pdf; Program available at: https://github.com/ lducas/SchnorrGate. | - |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/91499 | - |
| dc.description.abstract | 儘管Shor演算法藉由量子計算為質因數分解提供了一條新途徑，但對量子位元的數量和精度上的要求使該方法在不久的將來內難以實用化。在本論文中，我們將介紹三種與量子近似優化算法（QAOA）和量子退火——兩種有望在近期的量子設備上實現的優化算法——相容的整數分解方法。對於直接乘法方法和長乘法方法，我們將展示在最多29位元的質因數分解問題中所需的變量數量以及係數大小。對於次線性資源量子質因數分解（SQIF）算法，我們則將展示SQIF算法在先前研究的假設下的時間複雜度，並驗證這些假設以及SQIF算法有效性。 | zh_TW |
| dc.description.abstract | 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. | en |
| dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2024-01-28T16:16:34Z No. of bitstreams: 0 | en |
| dc.description.provenance | Made available in DSpace on 2024-01-28T16:16:34Z (GMT). No. of bitstreams: 0 | en |
| dc.description.tableofcontents | Acknowledgments I
摘要 II Abstract III List of Figures VII List of Tables IX 1 Introduction 1 2 Preliminaries 3 2.1 Quadratic Unconstrained Binary Optimization Problems 3 2.1.1 QUBO Formulation 3 2.1.2 Ising Formulation 4 2.1.3 Conversion between QUBO and Ising Formulations 4 2.2 Ising Solvers 5 2.2.1 Quantum Approximate Optimization Algorithm 5 2.2.2 Quantum Annealing 5 2.2.3 Simulated Annealing 6 2.3 Asymptotic Notations 7 2.4 Prime Numbers 7 3 Established Integer Factorization Methods 8 3.1 Basics of Integer Factoring 8 3.1.1 Difference of Squares: Fermat’s Factorization Method 8 3.1.2 Smooth Numbers: Dixon’s Factorization Method 9 3.2 Quadratic Sieve 10 3.3 General Number Field Sieve 12 3.4 Shor’s Algorithm 12 4 Ising Formulations by Multiplication 14 4.1 Direct Multiplication Method 15 4.2 Long Multiplication Method 16 4.2.1 Classical Preprocessing 17 4.3 Reducing Quartic Cost Functions to Quadratic Ones 18 4.4 Resource Requirement Comparison 20 4.4.1 Variable Usage 20 4.4.2 Magnitude of Coefficients 21 4.5 Numerical Results for Small Integers 22 5 Sublinear-Resource Quantum Integer Factoring Algorithm 28 5.1 Schnorr’s Integer Factoring Algorithm 29 5.1.1 Magnitude of the candidate smooth numbers |u − vN| 31 5.2 Babai’s Nearest Hyperplane Algorithm 32 5.2.1 Lenstra-Lenstra–Lov´asz Reduction 34 5.3 Ising Formulation 35 5.4 Approximation Requirement 36 5.4.1 Identical smoothness bounds for (u, v) and X = u − vN 37 5.4.2 Different smoothness bounds for (u, v) and X = u − vN 40 5.5 Numerical Results and Possible Design Flaw of the SQIF Algorithm 44 5.5.1 Replicability of previous works 45 5.5.2 Correspondence between diagonal elements and the candidate smooth numbers X = u − vN 46 5.5.3 Magnitude of candidate smooth numbers X = u − vN 48 6 Conclusions 55 A Derivation of equations 57 A.1 Derivation of Eq. (5.6) 57 A.2 Derivation of Eq. (5.32) from Eq. (5.31) 58 A.3 Derivation of Eq. (5.40) 58 A.4 Derivation of Eq. (5.43) 59 A.5 Derivation of Eq. (5.44) 60 B Difference to Schnorr’s Formulation 61 C Minimum Number of Fac-relation Pairs Required 62 D Lambert W Function 64 E Dickman Function 65 F Sieve of Eratosthenes 67 Bibliography 68 | - |
| dc.language.iso | en | - |
| dc.subject | 易辛表述 | zh_TW |
| dc.subject | 質因數分解 | zh_TW |
| dc.subject | 最近向量問題 | zh_TW |
| dc.subject | 二次無約束二進制優化 | zh_TW |
| dc.subject | Closest vector problem | en |
| dc.subject | Quadratic Unconstrained Binary Optimization (QUBO) | en |
| dc.subject | Ising formulation | en |
| dc.subject | Integer factorization | en |
| dc.title | 作為二元優化問題的質因數分解 | zh_TW |
| dc.title | Integer Factoring as Binary Optimization Problems | en |
| dc.type | Thesis | - |
| dc.date.schoolyear | 111-2 | - |
| dc.description.degree | 碩士 | - |
| dc.contributor.oralexamcommittee | 張慶瑞;洪士灝 | zh_TW |
| dc.contributor.oralexamcommittee | Ching-Ray Chang;Shih-Hao Hung | en |
| dc.subject.keyword | 易辛表述,質因數分解,最近向量問題,二次無約束二進制優化, | zh_TW |
| dc.subject.keyword | Ising formulation,Integer factorization,Closest vector problem,Quadratic Unconstrained Binary Optimization (QUBO), | en |
| dc.relation.page | 70 | - |
| dc.identifier.doi | 10.6342/NTU202302238 | - |
| dc.rights.note | 同意授權(全球公開) | - |
| dc.date.accepted | 2023-08-07 | - |
| dc.contributor.author-college | 理學院 | - |
| dc.contributor.author-dept | 物理學系 | - |
| dc.date.embargo-lift | 2028-07-31 | - |
| Appears in Collections: | 物理學系 | |
Files in This Item:
| File | Size | Format | |
|---|---|---|---|
| ntu-111-2.pdf Until 2028-07-31 | 1.83 MB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.