×
Das, Arnab; Chakrabarti, Bikas K.

Colloquium: Quantum annealing and analog quantum computation. (English) Zbl 1205.81058

Rev. Mod. Phys. 80, No. 3, 1061-1081 (2008).
Summary: The recent success in quantum annealing, i.e., optimization of the cost or energy functions of complex systems utilizing quantum fluctuations is reviewed here. The concept is introduced in successive steps through studying the mapping of such computationally hard problems to classical spin-glass problems, quantum spin-glass problems arising with the introduction of quantum fluctuations, and the annealing behavior of the systems as these fluctuations are reduced slowly to zero. This provides a general framework for realizing analog quantum computation.

Cited in 32 Documents

MSC:

81P68 Quantum computation
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Aeppli, G., in: Quantum Annealing and Related Optimization Methods (2005)
[2] DOI: 10.1137/S0097539705447323 · Zbl 1134.81009 · doi:10.1137/S0097539705447323
[3] DOI: 10.1088/0305-4470/29/23/006 · Zbl 0937.82505 · doi:10.1088/0305-4470/29/23/006
[4] DOI: 10.1021/j100127a023 · doi:10.1021/j100127a023
[5] DOI: 10.1016/0304-4149(89)90040-9 · Zbl 0683.90067 · doi:10.1016/0304-4149(89)90040-9
[6] Apolloni, B., in: Stochastic Processes, Physics and Geometry (1990)
[7] DOI: 10.1088/0305-4470/15/10/028 · doi:10.1088/0305-4470/15/10/028
[8] DOI: 10.1103/PhysRevE.71.066707 · doi:10.1103/PhysRevE.71.066707
[9] Battaglia, D. A., in: Quantum Annealing and Related Optimization Methods (2005)
[10] DOI: 10.1017/S0305004100034095 · doi:10.1017/S0305004100034095
[11] Bhatt, R. N., in: Spin Glasses and Random Fields (1998)
[12] DOI: 10.1103/RevModPhys.58.801 · doi:10.1103/RevModPhys.58.801
[13] DOI: 10.1088/0022-3719/17/18/004 · doi:10.1088/0022-3719/17/18/004
[14] DOI: 10.1126/science.284.5415.779 · doi:10.1126/science.284.5415.779
[15] DOI: 10.1038/35098037 · doi:10.1038/35098037
[16] DOI: 10.1103/PhysRevLett.96.136801 · doi:10.1103/PhysRevLett.96.136801
[17] DOI: 10.1103/PhysRevB.24.4062 · doi:10.1103/PhysRevB.24.4062
[18] Chakrabarti, B. K., in: Quantum Ising Phases and Transitions in Transverse Ising Models (1996) · Zbl 0872.60090
[19] Chakraborti, A., Eur. Phys. J. B 16 pp 667– (2000) ISSN: http://id.crossref.org/issn/1434-6028 · doi:10.1007/PL00011064
[20] DOI: 10.1103/PhysRevA.70.022314 · doi:10.1103/PhysRevA.70.022314
[21] , in: Quantum Annealing and Related Optimization Methods (2005) · Zbl 1130.81020
[22] DOI: 10.1103/PhysRevE.72.026701 · doi:10.1103/PhysRevE.72.026701
[23] DOI: 10.1103/PhysRevB.74.144423 · doi:10.1103/PhysRevB.74.144423
[24] Dotsenko, V., in: Introduction to the Replica Theory of Disordered Statistical Systems (2001) · Zbl 0999.82001 · doi:10.1017/CBO9780511524592
[25] DOI: 10.1088/0305-4608/5/5/017 · doi:10.1088/0305-4608/5/5/017
[26] DOI: 10.1103/RevModPhys.68.733 · doi:10.1103/RevModPhys.68.733
[27] DOI: 10.1126/science.1057726 · Zbl 1226.81046 · doi:10.1126/science.1057726
[28] DOI: 10.1103/PhysRevA.57.2403 · doi:10.1103/PhysRevA.57.2403
[29] DOI: 10.1016/0009-2614(94)00117-0 · doi:10.1016/0009-2614(94)00117-0
[30] DOI: 10.1103/PhysRevLett.56.1601 · doi:10.1103/PhysRevLett.56.1601
[31] DOI: 10.1103/PhysRevLett.53.1244 · doi:10.1103/PhysRevLett.53.1244
[32] Fu, Y., J. Phys. A 19 pp 1620– (1986) ISSN: http://id.crossref.org/issn/0305-4470
[33] DOI: 10.1103/RevModPhys.74.347 · Zbl 1205.94004 · doi:10.1103/RevModPhys.74.347
[34] Garey, M. R., in: Computers and Intractability: Guide to the Theory of NP-Completeness (1979) · Zbl 0411.68039
[35] DOI: 10.1088/0305-4470/39/27/001 · Zbl 1148.82307 · doi:10.1088/0305-4470/39/27/001
[36] Geman, S., IEEE Trans. Pattern Anal. Mach. Intell. 6 pp 721– (1984) ISSN: http://id.crossref.org/issn/0162-8828 · Zbl 0573.62030 · doi:10.1109/TPAMI.1984.4767596
[37] DOI: 10.1103/PhysRevLett.64.2467 · Zbl 1050.82559 · doi:10.1103/PhysRevLett.64.2467
[38] DOI: 10.1103/PhysRevLett.79.325 · doi:10.1103/PhysRevLett.79.325
[39] DOI: 10.1103/PhysRevLett.72.4137 · doi:10.1103/PhysRevLett.72.4137
[40] Hartmann, A., in: Optimization in Physics (2002) · Zbl 1003.82002
[41] Hatano, N., in: Quantum Annealing and Related Optimization Methods (2005)
[42] DOI: 10.1103/PhysRevLett.57.2203 · doi:10.1103/PhysRevLett.57.2203
[43] Inoue, J.-I., in: Quantum Annealing and Related Optimization Methods (2005)
[44] DOI: 10.1088/0022-3719/18/33/013 · doi:10.1088/0022-3719/18/33/013
[45] DOI: 10.1007/BF01453764 · doi:10.1007/BF01453764
[46] DOI: 10.1103/PhysRevE.58.5355 · doi:10.1103/PhysRevE.58.5355
[47] DOI: 10.1088/0305-4470/9/8/029 · Zbl 0333.57005 · doi:10.1088/0305-4470/9/8/029
[48] DOI: 10.1103/PhysRevB.66.054432 · doi:10.1103/PhysRevB.66.054432
[49] DOI: 10.1126/science.220.4598.671 · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[50] DOI: 10.1103/PhysRevLett.87.197204 · doi:10.1103/PhysRevLett.87.197204
[51] DOI: 10.1088/0305-4470/30/4/001 · Zbl 1001.82551 · doi:10.1088/0305-4470/30/4/001
[52] Marinari, E., Phys. Rev. Lett. 82 pp 5176– (1998) ISSN: http://id.crossref.org/issn/0031-9007 · doi:10.1103/PhysRevLett.82.5176
[53] DOI: 10.1103/PhysRevB.66.094203 · doi:10.1103/PhysRevB.66.094203
[54] DOI: 10.1103/PhysRevE.70.057701 · doi:10.1103/PhysRevE.70.057701
[55] Mezard, M., in: Spin Glass Theory and Beyond (1987)
[56] DOI: 10.1103/PhysRevLett.70.3147 · doi:10.1103/PhysRevLett.70.3147
[57] DOI: 10.1103/PhysRevLett.99.070502 · doi:10.1103/PhysRevLett.99.070502
[58] DOI: 10.1038/22055 · Zbl 1369.68244 · doi:10.1038/22055
[59] DOI: 10.1103/PhysRevLett.81.4252 · doi:10.1103/PhysRevLett.81.4252
[60] DOI: 10.1143/JPSJ.76.104001 · doi:10.1143/JPSJ.76.104001
[61] DOI: 10.1088/0305-4470/39/45/004 · Zbl 1105.81017 · doi:10.1088/0305-4470/39/45/004
[62] DOI: 10.1143/JPSJ.76.064002 · Zbl 1223.82044 · doi:10.1143/JPSJ.76.064002
[63] DOI: 10.1103/PhysRevB.76.174303 · doi:10.1103/PhysRevB.76.174303
[64] Nielsen, M. A., in: Quantum Computation and Quantum Information (2000)
[65] Nishimori, H., in: Statistical Physics of Spin Glasses and Information Processing: An Introduction (2001) · Zbl 1103.82002 · doi:10.1093/acprof:oso/9780198509417.001.0001
[66] Papadimitriou, C. H., in: Combinatorial Optimization: Algorithm and Complexity (1998) · Zbl 0944.90066
[67] DOI: 10.1088/0305-4470/13/3/042 · doi:10.1088/0305-4470/13/3/042
[68] DOI: 10.1103/PhysRevLett.76.1188 · Zbl 0945.90612 · doi:10.1103/PhysRevLett.76.1188
[69] DOI: 10.1103/PhysRevB.39.11828 · doi:10.1103/PhysRevB.39.11828
[70] Rieger, H., in: Quantum Annealing and Related Optimization Methods (2005)
[71] Roland, J., Phys. Rev. A 65 pp 042308– (2001) ISSN: http://id.crossref.org/issn/1050-2947 · doi:10.1103/PhysRevA.65.042308
[72] DOI: 10.1088/1742-5468/2007/05/P05008 · doi:10.1088/1742-5468/2007/05/P05008
[73] Sachdev, S., in: Quantum Phase Transitions (1999) · Zbl 1233.82003
[74] DOI: 10.1126/science.1068774 · doi:10.1126/science.1068774
[75] DOI: 10.1088/0305-4470/39/36/R01 · Zbl 1130.49037 · doi:10.1088/0305-4470/39/36/R01
[76] DOI: 10.1038/nphys706 · doi:10.1038/nphys706
[77] DOI: 10.1007/s11128-004-7712-7 · doi:10.1007/s11128-004-7712-7
[78] Sarjala, M., J. Stat. Mech.: Theory Exp. 2006 pp PO– (2006) ISSN: http://id.crossref.org/issn/1742-5468
[79] DOI: 10.1103/PhysRevA.69.053616 · doi:10.1103/PhysRevA.69.053616
[80] DOI: 10.1103/PhysRevLett.100.077204 · doi:10.1103/PhysRevLett.100.077204
[81] DOI: 10.1103/PhysRevLett.35.1792 · doi:10.1103/PhysRevLett.35.1792
[82] DOI: 10.1103/PhysRevLett.97.137204 · doi:10.1103/PhysRevLett.97.137204
[83] DOI: 10.1038/nature06050 · doi:10.1038/nature06050
[84] DOI: 10.1103/PhysRevLett.99.030603 · Zbl 1229.82016 · doi:10.1103/PhysRevLett.99.030603
[85] DOI: 10.1103/PhysRevE.75.051112 · doi:10.1103/PhysRevE.75.051112
[86] Suzuki, S., J. Phys. Soc. Jpn. 74 pp 1649– (2005) ISSN: http://id.crossref.org/issn/0031-9015 · doi:10.1143/JPSJ.74.1649
[87] Suzuki, S., in: Quantum Annealing and Related Optimization Methods (2005)
[88] DOI: 10.1103/PhysRevLett.90.067903 · doi:10.1103/PhysRevLett.90.067903
[89] DOI: 10.1103/PhysRevB.72.014303 · doi:10.1103/PhysRevB.72.014303
[90] Thirumalai, D., J. Phys. A 22 pp 2339– (1989) ISSN: http://id.crossref.org/issn/0305-4470 · doi:10.1088/0305-4470/22/16/023
[91] DOI: 10.1103/PhysRevLett.71.1919 · doi:10.1103/PhysRevLett.71.1919
[92] DOI: 10.1103/PhysRevLett.67.2076 · doi:10.1103/PhysRevLett.67.2076
[93] DOI: 10.1103/PhysRevLett.70.4011 · doi:10.1103/PhysRevLett.70.4011
[94] DOI: 10.1038/317505a0 · doi:10.1038/317505a0
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.