政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/55039
English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  Items with full text/Total items : 113822/144841 (79%)
Visitors : 51822488      Online Users : 517
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
    •  Adv. Search
    Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer Goto mobile version


    Please use this identifier to cite or link to this item: https://nccur.lib.nccu.edu.tw/handle/140.119/55039


    Title: 量子模擬: 量子隨機行走法則 與 量子退火式最佳化演算
    On Quantum Simulation: Quantum Random Walks and Quantum Adiabatic Optimization
    Authors: 張凱鈞
    Chang, Kai Chun
    Contributors: 林瑜琤
    Lin, Yu Cheng
    張凱鈞
    Chang, Kai Chun
    Keywords: 蒙地卡羅
    自旋玻璃
    Monte Carlo
    Ising
    spin glass
    Date: 2012
    Issue Date: 2012-10-30 15:22:22 (UTC+8)
    Abstract: 不同於一般電腦的數位位元資訊只有兩種可能數值0與1，量子電腦利用的是量子位元，係一個二維希爾伯特(Hilbert)空間中的單位向量，其表示方法為0與1的線性疊加態。量子模擬利用量子物理的基本線性疊加原理，來得到更有效率的方法處理計算科學的問題。本論文討論兩種量子演算法，量子隨機行走法則與量子退火最佳化演算法，在本論文中分成兩大部分，在第一部分中，我們研究在各種圖像中的量子隨機行走法則。研究隨機漫步有助於我們了解各種自然界中的隨機過程，如擴散作用與布朗運動。隨機漫步也已經被運用在許多的電腦演算法中，如搜尋演算法或者最佳化演算法。量子的隨機漫步係建立於量子力學的波函數，也是古典隨機漫步原理的延伸。但古典與量子隨機漫步卻有著非常不同的特性，比如量子隨機漫步傳播的速度大於古典的隨機漫步，且量子隨機漫步並不會像古典隨機漫步一樣會趨向穩定態。量子隨機漫步的時間演進係一由么正(unitary)算符所規範的么正過程，根據定義的不同，我們區分離散時間與連續時間兩種量子隨機漫步。在本論文中，我們研究與比較古典與量子的隨機漫步，分析在圖像以及無序環境上的模擬行走。第二部分，我們利用量子退火式演算解最佳化問題。退火係一材料從高溫控制降溫速度使其保持平衡態最後達成完美結晶結構的物理過程。與傳統的退火演算法利用熱擾動的方法不同，量子退火演算法利用的是量子擾動，使系統在其各種可能的解之間穿隧(tunneling)，以有效的達到最佳解。在本論文中，我們利用建立於路徑積分的蒙地卡羅(Monte Carlo)量子退火演算法，找出自旋玻璃的基態能量。我們以離散的虛數時間方法進行標準的量子蒙地卡羅以及連續的虛數時間方法進行路徑積分的蒙地卡羅，將這兩種量子方法與退火演算法結果的做分析比較。
    In standard classical digital computing, a unit of information takes only two possible values, say 0 or 1; In quantum computing, a unit of quantum information is a quantum bit or qubit, which is a unit vector in a two-dimensional Hilbert space, and is represented as a superposition of 0 and 1. Quantum simulation exploits the laws of quantum mechanics that involve the superposition principle to carry out computational tasks in a more efficient way than is possible with classical computers. This thesis is concerned with two quantum algorithms: quantum walks and quantum adiabatic optimization. This thesis is organized into two parts. In Part I, we study quantum walks on various graphs. Random walks are useful in understanding stochastic processes such as diffusion and Brownian motion. They have also been applied to many computational algorithms, such as search algorithms and algorithms for
    optimization problems. Quantum walks described by quantum mechanical wave functions are an extension of classical random walks. They have very different properties from classical random walks; for example, they do not in general converge toward a stationary distribution and potentially spread much faster. Quantum evolution is unitary; depending on the definition of unitary evolution operators, one distinguishes between discrete-time and continuous-time versions of quantum walks. We study these two versions of quantum walks. Quantum walks and classical random walks are compared in many examples, ranging from random walks on graphs to walks in disordered media. In Part II, we focus on optimization by quantum adiabatic algorithms (also known as quantum annealing algorithms). Annealing is a technique involving controlled cooling of a material to have perfect crystalline structures formed. Unlike classical simulated annealing in which thermal fluctuations are utilized for convergence in optimization problems, quantum annealing uses quantum fluctuations to explore the solution space via quantum tunneling, with the potential to hasten convergence to the best solution. In this thesis we implement quantum annealing based on path-integral quantum Monte Carlo (QMC) methods to find the ground states of Ising spin glasses. In particular, we investigate the effect of the discretization of imaginary time used in standard QMC methods and also perform continuous-time path integral Monte Carlo. We compare the results with those obtained by simulated annealing.
    Reference: [1] R. Feynman, Int. J. Th. Phys. 21, 467 (1982). 1, 7
    [2] P.W. Shor, SIAM J. Comp., 26, 1484 (1997); preliminary version in Proceed- ings of the 35th Ann. IEEE Symp. on the Foundations of Computer Science (FOCS), 124, (1994). 3
    [3] L. K. Grover, Phys. Rev. Lett., 79, 325 (1997). 3
    [4] H. Schmitz et al., Phys. Rev. Lett. 103, 090504 (2009); F. Z ̈ahringer et al.,
    Phys. Rev. Lett. 104, 100503 (2010). 7
    [5] M. Karski et al., Science 325, 174 (2009). 7
    [6] A. Peruzzo et al., Science 329, 1500 (2010). 7
    [7] G. S. Engel et al., Nature (London) 446, 782 (2007); M. Mohseni, P. Reben- trost, S. Lloyd, and A. Aspuru-Guzik, J. Chem. Phys. 129, 174106 (2008). 7, 87
    [8] Y. G. Sinai, Theor. Prob. and Appl. 27, 256 (1982). 13
    [9] P. Le Doussal, C. Monthus, and D. S. Fisher, Phys. Rev. E 59, 4795 (1999).
    14, 20, 23
    [10] R. D. Levine, Molecular Reaction Dynamics, Cambridge University Press (2005). 15
    [11] E. Weisstein, ”Jacobi-Anger Expansion.” MathWorld–A Wolfram Web Re- source. http://mathworld.wolfram.com/Jacobi-AngerExpansion.html 19
    [12] F. Iglo ́i and H. Rieger, Phys. Rev. E 58, 4238 (1998). 20, 22, 23
    [13] E. Lieb, T. Schultz and D. Mattis, Ann. Phys. (NY) 16, 407 (1961). 20
    [14] P. Jordan and E. Wigner, Z. Physik 47, 631 (1928). 20
    [15] I. Peschel, Phys. Rev. B 30, 6783 (1984). 22
    [16] J. Kempe, Contemporary Physics 44, 307 (2003).
    [17] E. Farhi and S. Gutmann, Phys. Rev. A 58, 915 (1998). 25, 33, 34
    [18] Y. Aharonov, L. Davidovich, and N. Zagury, Phys. Rev. A 48, 1687 (1993). 25
    [19] D. Aharonov, A. Ambainis, J. Kempe J and U. Vaziran, Proc. 33rd Annu. ACM Symp. on Theory of Computing (STOC) pp 50-59, New York, NY, USA, (2001); (arXiv:quant-ph/0012090). 26, 30
    [20] A. Ambainis, E. Bach, A. Nayak, A. Vishwanath and J. Watrous, Proc. 33rd Annu. ACM Symp. on Theory of Computing (STOC) pp 37-49, New York, NY, USA, (2001). 29
    [21] A. Nayak, A. Vishwanath, arXiv:quant-ph/0010117v1 (2000). 29
    [22] A. Ambainis, International Journal of Quantum Information 1, 507 (2003). 30
    [23] A. Ambainis, J. Kempe, and A. Rivosh, Proc. 16th ACM-SIAM SODA, pp 1099 (2005). 31
    [24] G. Leung, P. Knott, J. Bailey and V. Kendon, New J. Phys. 12, 123018 (2010). 31
    [25] See e.g. E. W. Weisstein, ”Random Walk–2-Dimensional.” MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/RandomWalk2-Dimensional.html 31
    [26] A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, D. A. Spiel- man, Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing ACM Press, New York, p. 59 (2003). 37
    [27] A. M. Childs, E. Farhi, and S. Gutmann, Quantum Information Processing 1, 35 (2002). 37
    [28] S. D. Berry, P. Bourke, J. B. Wang, Computer Physics Communications 182 2295 (2011). 39
    [29] E. Weisstein, ”Bessel Function of the First Kind.” From MathWorld.
    http://mathworld.wolfram.com/BesselFunctionoftheFirstKind.html
    44
    [30] See, e.g., J. J. Sakurai, Modern Quantum Mechanics, Chap. 4, Addison- Wesley Publishing Company (1994). 43
    [31] O. Mu ̈lken, A. Volta, and A. Blumen, Phys. Rev. A 72, 042334 (2005). 44
    [32] S. R. Broadbent and J. M. Hammersley, Proc. Cam. Phil. Soc. 53, 629
    (1957). 48
    [33] P. G. de Gennes, La Recherche 7, 919, 1976. 48
    [34] D. Stauffer and A. Aharony, Introduction to Percolation Theory, CRC Press, (1992). 49, 50, 52
    [35] B. Mandelbrot, Fractals: Form, Chance and Dimension, Freeman, (1977). 50
    [36] S. Alexander and R. Orbach J. Phys. Paris. Lett. 43, L635 (1982). 50, 52
    [37] S. Havlin and D. Ben-Avraham, Advances in Physics 51, 187 (2002). 50, 52
    [38] P. W. Anderson, Phys. Rev. 109, 1492 (1958). 51
    [39] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Science 220, 671 (1983). 57, 61
    [40] M. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller, J. Chem. Phys. 21, 1087 (1953). 61
    [41] K. Binder and A. P. Young, Rev. Mod. Phys. 58, 801 (1986). 57
    [42] D. H. Reich, B. Ellman, J. Yang, and T. F. Rosenbaum, G. Aeppli, and
    D. P. Belanger, Phys. Rev. B. 42, 4631 (1990). 58
    [43] S. Sachdev, Quantum Phase Transitions, Cambridge University Press,
    (2011). 59
    [44] J. Brooke, D. Bitko, T. F. Rosenbaum, G. Aeppli, Science 284, 779 (1999). 59, 68, 71
    [45] http://www.informatik.uni-koeln.de/spinglass 65
    [46] D. A. Huse and D. S. Fisher, Phys. Rev. Lett. 57, 2203 (1986). 66
    [47] P. Amara, D. Hsu and J. E. Straub, J. Phys. Chem. 97, 6715 (1993). 67
    [48] T. Kadowaki and H. Nishimori, Phys. Rev. E 58, 5355 (1998). 67, 69
    [49] E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, D. Preda, Science 292, 472 (2001). 67
    [50] J. J. Hopfield and D. W. Tank, Science 233, 625 (1986); T. Kadowaki, quant-ph/0205020; R. Martona ́k, G. E. Santoro, and E. Tosatti, Phys. Rev. E 70 057701 (2004). 68
    [51] M. Born, and V. Fock, Zeitschrift fu ̈r Physik A: Hadrons and Nuclei 51 165 (1928). 68
    [52] E. Farhi, J. Goldstone, and S. Gutmann, arXiv:quant-ph/0201031 (2002). 68
    [53] A. P. Young, S. Knysh, and V. N. Smelyanskiy, Phys. Rev. Lett. 101, 170503 (2008). 69
    [54] G. Santoro and E. Tosatti, J. Phys. A: Math. Gen. 39, R393 (2006). 69
    [55] G. Aeppli, and T. F. Rosenbaum, in Quantum Annealing and Related Opti- mization Methods, edited by A. Das and B. K. Chakrabarti, Lecture Notes in Physics No. 679, Springer-Verlag, Heidelberg, pp 159-169 (2005). 71
    [56] W. Wernsdorfer, Int. J. Nanotechnol. 7, 497 (2010); S. Carretta, W. Liviotti, N. Magnani, P. Santini, and G. S. Amoretti, Phys. Rev. Lett. 92, 207205 (2004). 71
    [57] M. W. Johnson et al, Nature 473, 194 (2011). 71
    [58] H. F. Trotter, Proc. Am. Math. Soc. 10, 545 (1959). 74, 76
    [59] M. Suzuki, Prog. Theor. Phys. 56, 1454 (1976). 75, 76
    [60] M. Aizenman, and B. Nachtergaele, Comm. Math. Phys., 164, 17 (1994). 81
    [61] H. G. Evertz, Advances in Physics 52, 1 (2003). 81
    [62] H. Rieger and N. Kawashima, Eur. Phys. J. B 9, 233 (1999). 81, 84
    [63] P. Pfeuty and R. Elliot, J. Phys. C 4, 2370 (1971). 84
    [64] M. S. L. du Croo de Jongh and J. M. J. van Leeuwen, Phys. Rev. B 57, 8494 (1998). 84
    [65] T. Kitagawa, M. S. Rudner, E. Berg, and E. Demler, Phys. Rev. A 82, 033429 (2010). 87
    Description: 碩士
    國立政治大學
    應用物理研究所
    99755008
    101
    Source URI: http://thesis.lib.nccu.edu.tw/record/#G0997550081
    Data Type: thesis
    Appears in Collections:[Graduate Institute of Applied Physics] Theses

    Files in This Item:

    File SizeFormat
    008101.pdf21316KbAdobe PDF2976View/Open


    All items in 政大典藏 are protected by copyright, with all rights reserved.


    社群 sharing

    著作權政策宣告 Copyright Announcement
    1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
    The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

    2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
    NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback