Loading...
|
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: | [應用物理研究所 ] 學位論文
|
Files in This Item:
| File |
Size | Format | |
|---|
| 008101.pdf | 21316Kb | Adobe PDF2 | 975 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
