請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/78760
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 管希聖(Hsi-Sheng Goan) | |
dc.contributor.author | Huang-Jeng Chao | en |
dc.contributor.author | 趙黃正 | zh_TW |
dc.date.accessioned | 2021-07-11T15:17:25Z | - |
dc.date.available | 2021-07-23 | |
dc.date.copyright | 2019-07-23 | |
dc.date.issued | 2019 | |
dc.date.submitted | 2019-07-19 | |
dc.identifier.citation | [1] R. H. Myers and R. H. Myers, Classical and modern regression with applications, vol. 2 (Duxbury press Belmont, CA, 1990).
[2] J. A. Suykens and J. Vandewalle, Neural processing letters 9, 293 (1999). [3] P. Resnick and H. R. Varian, Communications of the ACM 40, 56 (1997). [4] G. Strang, The American Mathematical Monthly 100, 848 (1993). [5] J. R. Shewchuk et al., An introduction to the conjugate gradient method without the agonizing pain (1994). [6] A. W. Harrow, A. Hassidim, and S. Lloyd, Physical review letters 103, 150502 (2009). [7] D. Dervovic, M. Herbster, P. Mountney, S. Severini, N. Usher, and L. Wossnig, arXiv preprint arXiv:1802.08227 (2018). [8] D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders, Communications in Mathematical Physics 270, 359 (2007). [9] A. M. Childs and R. Kothari, arXiv preprint arXiv:0908.4398 (2009). [10] L. Wossnig, Z. Zhao, and A. Prakash, Physical review letters 120, 050502 (2018). [11] H. W. Chung, Ph.D. thesis, Massachusetts Institute of Technology (2014). [12] M. A. Nielsen and I. Chuang, Quantum computation and quantum information (2002). [13] E. Alpaydin, Introduction to machine learning (MIT press, 2009). [14] C. K. Li and D. C. Pelejo, International Journal of Quantum Information 12, 1450002 (2014). [15] C.-K. Li, R. Roberts, and X. Yin, International Journal of Quantum Information 11, 1350015 (2013). [16] J. J. Vartiainen, M. M ott onen, and M. M. Salomaa, Physical review letters 92, 177902 (2004). [17] M.-J. Hu, Z.-Y. Zhou, X.-M. Hu, C.-F. Li, G.-C. Guo, and Y.-S. Zhang, npj Quantum Information 4, 63 (2018). [18] K. H. Rosen and K. Krithivasan, Discrete mathematics and its applications: with combinatorics and graph theory (Tata McGraw-Hill Education, 2012). [19] M. Mottonen, J. J. Vartiainen, V. Bergholm, and M. M. Salomaa, Physical review letters 93, 130502 (2004). [20] M. Mottonen and J. J. Vartiainen, arXiv preprint quant-ph/0504100 (2005). [21] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms (MIT press, 2009). [22] R. Cleve, Collected Papers on Quantum Computation and Quantum Information Theory pp. 103{127 (2000). [23] D. S. Touretzky, M. C. Mozer, and M. E. Hasselmo, Advances in Neural Information Processing Systems 8: Proceedings of the 1995 Conference, vol. 8 (Mit Press, 1996). [24] S. Nayak, Journal of Global Research in Computer Science 2, 50 (2011). [25] D. Wang, O. Higgott, and S. Brierley, Physical review letters 122, 140504 (2019). [26] M. Schuld, A. Bocharov, K. Svore, and N. Wiebe, arXiv preprint arXiv:1804.00633 (2018). [27] J. A. Suykens and J. Vandewalle, in IJCNN (1999), vol. 99, p. 900. [28] S. Lloyd, Science pp. 1073{1078 (1996). [29] S. Dutta, A. Suau, S. Dutta, S. Roy, B. K. Behera, and P. K. Panigrahi, arXiv preprint arXiv:1811.01726 (2018). [30] Y. Cao, A. Daskin, S. Frankel, and S. Kais, Molecular Physics 110, 1675 (2012). [31] Y. Zheng, C. Song, M.-C. Chen, B. Xia, W. Liu, Q. Guo, L. Zhang, D. Xu, H. Deng, K. Huang, et al., Physical review letters 118, 210504 (2017). [32] S. Barz, I. Kassal, M. Ringbauer, Y. O. Lipp, B. Dakic, A. Aspuru-Guzik, and P. Walther, arXiv preprint arXiv:1302.1210 (2013). [33] I. Kerenidis and A. Prakash, ITCS2017 (Dagstuhl, 2017) 67, 1 (2017). | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/78760 | - |
dc.description.abstract | 自1994年Peter Shor提出量子演算法可有效解決質因數分解問題後,衝擊現代密碼學之安全性,量子演算法也開始大量被研究。而在解聯立方程式的問題中,古典電腦需要多項式時間才能解決。在2009年,有學者提出該問題的量子版本有對數時間內的量子演算法(HHL algorithm),而2018年也有其改良版本問世(WZP algorithm)。這個發明可以應用在機器學習演算法,如線性回歸、支援向量機等等。本篇論文探討如何有效率地在實際量子電腦上執行任何聯立方程式量子演算法,包含HHL及WZP兩種,以及古典資訊必須轉換為量子資訊的演算法,並利用IBM公司提供的量子計算模擬器執行。模擬的結果顯示,使用三個精準位元來解二元一次聯立方程式,即可達到99%以上的精準度。這個關鍵在於我的電路設計可以在不影響複雜度的情況下大幅提升準確性。此外,我也在IBM的實體量子電腦執行該演算法。 | zh_TW |
dc.description.abstract | Quantum algorithms have attracted much attention since the quantum factoring algorithm proposed by Shor in 1994 which promised to factor large semiprime integer, threating current cryptographic or encryption systems. For solving the problem of a system of linear equations, it takes polynomial time on classical computer. However, a quantum algorithm known as the HHL algorithm published in 2009 showed that it takes only logarithmic time to solve the quantum version of the problem for sparse matrices. Furthermore, the improved version, the so-called WZP algorithm published in 2018 generalize the problem to the dense matrices. These breakthroughs can be applied to machine learning algorithms, such as linear regression, support vector machine, etc. In this thesis, we discuss how to efficiently execute quantum linear system algorithms, including the HHL algorithm, and the WZP algorithm, on quantum simulators and a practical quantum computer provided by IBM. We also show how to transform the classical information to quantum state that can be manipulated in quantumn computer. The simulation result for solving a two variable system of linear equations shows that using three accuracy qubits, the state delity can be 99%. The key point is that we can greatly increase the accuracy under the same complexity condition. Besides, we implement the algorithm on a real IBMQ quantum computer processor. | en |
dc.description.provenance | Made available in DSpace on 2021-07-11T15:17:25Z (GMT). No. of bitstreams: 1 ntu-108-R06222051-1.pdf: 2894002 bytes, checksum: 96503aca9f94ec925f84d1e68a26aa27 (MD5) Previous issue date: 2019 | en |
dc.description.tableofcontents | Acknowledgments I
摘要II Abstract III List of Figures VI List of Tables VIII 1 Introduction 1 2 Quantum computation and machine learning 4 2.1 Quantum computer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1.1 Quantum bit . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1.2 Quantum gates . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.3 Realization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Quantum circuit design . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3 Time complexity theory . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4 Machine learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4.1 Brief history . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4.2 Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4.3 Linear regression . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.4.4 Support vector machine . . . . . . . . . . . . . . . . . . . . . 23 3 Method 28 3.1 Initial state preparation . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2 Unitary gate preparation . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.2.1 Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.2.2 Universal gate decomposition algorithm . . . . . . . . . . . . . 34 3.3 Harrow-Hassidim-Lloyd algorithm . . . . . . . . . . . . . . . . . . . . 35 3.3.1 Preceding operations . . . . . . . . . . . . . . . . . . . . . . . 35 3.3.2 Quantum Hamiltonian simulation . . . . . . . . . . . . . . . . 36 3.3.3 Quantum phase estimation . . . . . . . . . . . . . . . . . . . . 37 3.3.4 Controlled reciprocal rotation . . . . . . . . . . . . . . . . . . 39 3.3.5 HHL Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.4 Wossnig-Zhao-Prakash algorithm . . . . . . . . . . . . . . . . . . . . 42 3.4.1 Matrix factorization . . . . . . . . . . . . . . . . . . . . . . . 42 3.4.2 Orthogonal projection . . . . . . . . . . . . . . . . . . . . . . 44 3.4.3 Quantum singular value estimation . . . . . . . . . . . . . . . 45 3.4.4 WZP algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4 Result and Discussion 50 4.1 Quantum simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.2 Simulation of the HHL algorithm . . . . . . . . . . . . . . . . . . . . 51 4.3 Simulation of the WZP algorithm . . . . . . . . . . . . . . . . . . . . 52 4.4 Implementation on a real quantum computer . . . . . . . . . . . . . . 55 4.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5 Conclusion 61 Bibliography 62 A Proof of the matrix factorizations 65 B Proof of the eigenvalues of W 68 | |
dc.language.iso | en | |
dc.title | 實現任意聯立方程式之量子演算法及其在機器學習上之應用 | zh_TW |
dc.title | Implement quantum algorithm for solving general system of
linear equations and its applications to machine learning | en |
dc.type | Thesis | |
dc.date.schoolyear | 107-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 林俊達(Guin-Dar Lin),江介宏(Jie-Hong Jiang) | |
dc.subject.keyword | 量子電腦,量子演算法,機器學習,量子模擬器,量子電路設計, | zh_TW |
dc.subject.keyword | Quantum computer,Quantum algorithm,Machine learning,Quantum simulator,Quantum circuit design, | en |
dc.relation.page | 69 | |
dc.identifier.doi | 10.6342/NTU201901638 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2019-07-19 | |
dc.contributor.author-college | 理學院 | zh_TW |
dc.contributor.author-dept | 物理學研究所 | zh_TW |
顯示於系所單位: | 物理學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-108-R06222051-1.pdf 目前未授權公開取用 | 2.83 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。