-
量子计算在近十年取得了长足的进展. 随着量子调控技术达到前所未有的高度, 包括超导量子比特、光量子器件、原子系综等在内的量子实验平台都进入到了崭新的时代. 目前在特定计算任务上超越经典的量子计算优势也已经被报道. 其中一种可以有效运用可控量子器件的计算方案是采用绝热量子计算. 绝热量子计算中算法的选择与研究至关重要, 其将直接决定量子计算优势是否能够最大限度地被挖掘. 本综述主要介绍近期机器学习在绝热量子算法设计方面的应用, 并讲述该计算架构在3-SAT和Grover搜索等问题上的应用. 通过与未经机器学习优化设计的绝热量子算法对比, 研究表明机器学习方法的应用可以极大提高绝热量子算法的计算效率.Quantum computing has made dramatic progress in the last decade. The quantum platforms including superconducting qubits, photonic devices, and atomic ensembles, have all reached a new era, with unprecedented quantum control capability developed. Quantum computation advantage over classical computers has been reported on certain computation tasks. A promising computing protocol of using the computation power in these controllable quantum devices is implemented through quantum adiabatic computing, where quantum algorithm design plays an essential role in fully using the quantum advantage. Here in this paper, we review recent developments in using machine learning approach to design the quantum adiabatic algorithm. Its applications to 3-SAT problems, and also the Grover search problems are discussed.
[1] Benioff P 1980 J. Statistical Phys. 22 563Google Scholar
[2] Feynman R P 1982 Int. J. Theor. Phys. 21 133
[3] Deutsch D E 1989 Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 425 73Google Scholar
[4] Yao A C C 1993 Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science (IEEE) pp352−361
[5] Shor P W 1994 Proceedings 35th annual symposium on foundations of computer science (IEEE) pp124−134
[6] Ekert A, Jozsa R 1996 Rev. Mod. Phys. 68 733Google Scholar
[7] Gerjuoy E 2005 Am. J. Phys. 73 521Google Scholar
[8] Aumasson J P 2017 Computer Fraud & Security 2017 8
[9] Vandersypen L M, Steffen M, Breyta G, Yannoni C S, Sherwood M H, Chuang I L 2001 Nature 414 883Google Scholar
[10] Lu C Y, Browne D E, Yang T, Pan J W 2007 Phys. Rev. Lett. 99 250504Google Scholar
[11] Politi A, Matthews J C, O’brien J L 2009 Science 325 1221Google Scholar
[12] Monz T, Nigg D, Martinez E A, et al. 2016 Science 351 1068Google Scholar
[13] Ladd T D, Jelezko F, Laflamme R, Nakamura Y, Monroe C, O’Brien J L 2010 Nature 464 45Google Scholar
[14] Bernstein E, Vazirani U 1997 SIAM J. Comp. 26 1411Google Scholar
[15] Nielsen M A, Chuang I 2002 Quantum Computation and Quantum Information (Cambridge: Cambridge University Press)
[16] Shor P W 2003 J. ACM (JACM) 50 87Google Scholar
[17] Watrous J 2008 arXiv preprint arXiv: 0804.3401
[18] Simon D R 1997 SIAM J. Comp. 26 1474Google Scholar
[19] Hallgren S 2002 Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing pp653−658
[20] Grover L K 1997 Phys. Rev. Lett. 79 325Google Scholar
[21] Shao C, Li Y, Li H 2019 J. Syst. Sci. 32 375Google Scholar
[22] Farhi E, Goldstone J, Gutmann S, Sipser M 2000 arXiv preprint quant-ph/0001106
[23] Farhi E, Goldstone J, Gutmann S, Lapan J, Lundgren A, Preda D 2001 Science 292 472Google Scholar
[24] Zhang D J, Yu X D, Tong D 2014 Phys. Rev. A 90 042321Google Scholar
[25] Aharonov D, Van Dam W, Kempe J, Landau Z, Lloyd S, Regev O 2008 SIAM Rev. 50 755Google Scholar
[26] Yu H, Huang Y, Wu B 2018 Chin. Phys. Lett. 35 110303Google Scholar
[27] Dong D, Petersen I R 2010 IET Control Theory & Applications 4 2651
[28] Cirac J I, Zoller P 2012 Nat. Phys. 8 264Google Scholar
[29] Georgescu I M, Ashhab S, Nori F 2014 Rev. Mod. Phys. 86 153Google Scholar
[30] Gross C, Bloch I 2017 Science 357 995Google Scholar
[31] Rice J R 1976 In Advances in Computers (Vol. 15) (Elsevier) pp65–118
[32] Hutter F, Hoos H H, Leyton-Brown K, Stützle T 2009 Journal of Artificial Intelligence Research 36 267Google Scholar
[33] Wang L 2016 Phys. Rev. B 94 195105Google Scholar
[34] Carrasquilla J, Melko R G 2017 Nat. Phys. 13 431Google Scholar
[35] Van Nieuwenburg E P, Liu Y H, Huber S D 2017 Nat. Phys. 13 435Google Scholar
[36] Deng D L, Li X, Sarma S D 2017 Phys. Rev. X 7 021021
[37] Zhang P, Shen H, Zhai H 2018 Phys. Rev. Lett. 120 066401Google Scholar
[38] Gao X, Duan L M 2017 Nat. Commun. 8 1Google Scholar
[39] Huang Y, Moore J E 2017 arXiv preprint arXiv: 1701.06246
[40] Cai Z, Liu J 2018 Phys. Rev. B 97 035116Google Scholar
[41] Carleo G, Troyer M 2017 Science 355 602Google Scholar
[42] Day A G, Bukov M, Weinberg P, Mehta P, Sels D 2019 Phys. Rev. Lett. 122 020601Google Scholar
[43] Niu M Y, Boixo S, Smelyanskiy V N, Neven H 2019 npj Quantum Information 5 33Google Scholar
[44] Zhang X M, Wei Z, Asad R, Yang X C, Wang X 2019 npj Quantum Information 5 85Google Scholar
[45] Bukov M, Day A G, Sels D, Weinberg P, Polkovnikov A, Mehta P 2018 Phys. Rev. X 8 031086
[46] Aaronson S 2015 Nat. Phys. 11 291Google Scholar
[47] Albash T, Lidar D A 2018 Rev. Mod. Phys. 90 015002Google Scholar
[48] Tong D 2010 Phys. Rev. Lett. 104 120401Google Scholar
[49] Amin M H 2009 Phys. Rev. Lett. 102 220401Google Scholar
[50] Altshuler B, Krovi H, Roland J 2010 Proceedings of the National Academy of Sciences 107 12446Google Scholar
[51] Jörg T, Krzakala F, Semerjian G, Zamponi F 2010 Phys. Rev. Lett. 104 207206Google Scholar
[52] Dickson N G, Amin M 2011 Phys. Rev. Lett. 106 050502Google Scholar
[53] Hen I, Young A 2011 Phys. Rev. E 84 061152Google Scholar
[54] Bapst V, Foini L, Krzakala F, Semerjian G, Zamponi F 2013 Phys. Rep. 523 127Google Scholar
[55] Hauke P, Katzgraber H G, Lechner W, Nishimori H, Oliver W D 2020 Rep. Prog. Phys. 83 054401Google Scholar
[56] Santoro G E, Martoňák R, Tosatti E, Car R 2002 Science 295 2427Google Scholar
[57] Boixo S, Albash T, Spedalieri F M, Chancellor N, Lidar D A 2013 Nat. Commun. 4 1
[58] Sherrington D, Kirkpatrick S 1975 Phys. Rev. Lett. 35 1792Google Scholar
[59] Barahona F 1982 Journal of Physics A: Mathematical and General 15 3241Google Scholar
[60] Kirkpatrick T R, Thirumalai D 1987 Phys. Rev. B 36 5388Google Scholar
[61] Mézard M, Parisi G, Virasoro M A 1987 Spin Glass Theory and Beyond: An Introduction to the Replica Method and Its Applications (Vol. 9) (Singapore: World Scientific Publishing Company)
[62] Hartmann A K, Weigt M 2005 Phase Transitions in Combinatorial Optimization Problems (Vol. 67) (Wiley Online Library)
[63] Mezard M, Montanari A 2009 Information, Physics, and Computation (Oxford University Press)
[64] Karp R M 1972 In Complexity of Computer Computations (Berlin: Springer) pp85–103
[65] Lucas A 2014 Frontiers in Physics 2 5
[66] Roland J, Cerf N J 2002 Phys. Rev. A 65 042308Google Scholar
[67] Gendreau M, Potvin J Y, et al. 2010 Handbook of Metaheuristics (Vol. 2) (Berlin: Springer)
[68] Meletiou G, Tasoulis D, Vrahatis M N, et al. 2002 In IASTED 2002 Conference on Artificial Intelligence pp483–488
[69] Stekel A, Chkroun M, Azaria A 2018 arXiv: 1803.09237
[70] Yampolskiy R V 2010 International Journal of Bio-Inspired Computation 2 115Google Scholar
[71] Monaco J V, Vindiola M M 2017 In 2017 IEEE International Symposium on Circuits and Systems (ISCAS) pp1−4
[72] Borders W A, Pervaiz A Z, Fukami S, Camsari K Y, Ohno H, Datta S 2019 Nature 573 390Google Scholar
[73] Preskill J 2018 Quantum 2 79Google Scholar
[74] Dash A, Sarmah D, Behera B K, Panigrahi P K 2018 arXiv: 1805.10478
[75] Dridi R, Alghassi H 2017 Sci. Rep. 7 1Google Scholar
[76] Xu K, Xie T, Li Z, et al. 2017 Phys. Rev. Lett. 118 130504Google Scholar
[77] Jiang S, Britt K A, McCaskey A, Humble T, Kais S 2018 Sci. Rep. 8 17667Google Scholar
[78] Wang B, Hu F, Yao H, Wang C 2020 Sci. Rep. 10 1Google Scholar
[79] Peng X, Liao Z, Xu N, Qin G, Zhou X, Suter D, Du J 2008 Phys. Rev. Lett. 101 220405Google Scholar
[80] Bernstein E, Vazirani U 1993 ACM, New York 11
[81] Knill E, Laflamme R 2001 Inform. Proc. Lett. 79 173Google Scholar
[82] Freedman M H, Larsen M, Wang Z 2002 Commun. Math. Phys. 227 605Google Scholar
[83] Freedman M H, Kitaev A, Wang Z 2002 Commun. Math. Phys. 227 587Google Scholar
[84] Wocjan P, Zhang S 2006 arXiv preprint quant-ph/0606179
[85] Somma R D, Nagaj D, Kieferová M 2012 Phys. Rev. Lett. 109 050501Google Scholar
[86] Solomonoff R J 1985 Human Systems Management 5 149Google Scholar
[87] Bishop C M 2006 Pattern Recognition and Machine Learning (Berlin: Springer)
[88] Indurkhya N, Damerau F J 2010 Handbook of Natural Language Processing (Vol. 2) (Los Angeles: CRC Press)
[89] Sutton R S, Barto A G 2018 Reinforcement Learning: An Introduction (Cambridge: MIT Press)
[90] Rumelhart D E, Hinton G E, Williams R J 1986 Nature 323 533Google Scholar
[91] Alpaydin E 2020 Introduction to Machine Learning (Cambridge: MIT Press)
[92] Silver D, Huang A, Maddison C J, et al. 2016 Nature 529 484Google Scholar
[93] Silver D, Schrittwieser J, Simonyan K, et al. 2017 Nature 550 354Google Scholar
[94] Silver D, Hubert T, Schrittwieser J, et al. 2018 Science 362 1140Google Scholar
[95] Schrittwieser J, Antonoglou I, Hubert T, et al. 2020 Nature 588 604Google Scholar
[96] Wolpert D H, Macready W G 1997 IEEE Transactions on Evolutionary Computation 1 67Google Scholar
[97] Kerschke P, Hoos H H, Neumann F, Trautmann H 2019 Evolutionary Computation 27 3Google Scholar
[98] Lagoudakis M G, Littman M L 2000 ICML pp511–518
[99] Gomes C P, Selman B 2001 Artificial Intelligence 126 43Google Scholar
[100] Leyton-Brown K, Nudelman E, Shoham Y 2002 International Conference on Principles and Practice of Constraint Programming (Berlin: Springer) pp556−572
[101] Leyton-Brown K, Nudelman E, Andrew G, McFadden J, Shoham Y 2003 In IJCAI (Vol. 3) pp1542−1543
[102] Xu L, Hutter F, Hoos H H, Leyton-Brown K 2008 Journal of Artificial Intelligence Research 32 565Google Scholar
[103] Smith-Miles K A 2009 ACM Computing Surveys (CSUR) 41 1
[104] Kotthoff L, Gent I P, Miguel I 2012 Ai Communications 25 257Google Scholar
[105] Mısır M, Sebag M 2017 Artificial Intelligence 244 291Google Scholar
[106] Ansótegui C, Sellmann M, Tierney K 2009 International Conference on Principles and Practice of Constraint Programming (Springer) pp142−157
[107] Hutter F, Hoos H H, Leyton-Brown K 2011 International Conference on Learning and Intelligent Optimization (Berlin: Springer) pp507−523
[108] Fitzgerald T, Malitsky Y, O’Sullivan B, Tierney K 2014 Seventh Annual Symposium on Combinatorial Search
[109] López-Ibánez M, Dubois-Lacoste J, Cáceres L P, Birattari M, Stützle T 2016 Operations Research Perspectives 3 43Google Scholar
[110] Biedenkapp A, Bozkurt H F, Eimer T, Hutter F, Lindauer M 2020 Proceedings of the Twentyfourth European Conference on Artificial Intelligence (ECAI’20), Jun 2020
[111] Speck D, Biedenkapp A, Hutter F, Mattmüller R, Lindauer M 2020 arXiv preprint arXiv: 2006.08246
[112] Xu L, Hoos H, Leyton-Brown K 2010 Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 24)
[113] Biamonte J, Wittek P, Pancotti N, Rebentrost P, Wiebe N, Lloyd S 2017 Nature 549 195Google Scholar
[114] Harrow A W, Hassidim A, Lloyd S 2009 Phys. Rev. Lett. 103 150502Google Scholar
[115] Childs A M, Kothari R, Somma R D 2017 SIAM J. Comput. 46 1920Google Scholar
[116] Wiebe N, Braun D, Lloyd S 2012 Phys. Rev. Lett. 109 050505Google Scholar
[117] Rebentrost P, Schuld M, Wossnig L, Petruccione F, Lloyd S 2019 New J. Phys. 21 073023Google Scholar
[118] Brandao F G, Svore K M 2017 In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE) pp415−426
[119] Lloyd S, Mohseni M, Rebentrost P 2014 Nat. Phys. 10 631Google Scholar
[120] Lloyd S, Garnerone S, Zanardi P 2016 Nat. Commun. 7 1
[121] Rebentrost P, Mohseni M, Lloyd S 2014 Phys. Rev. Lett. 113 130503Google Scholar
[122] Giovannetti V, Lloyd S, Maccone L 2008 Phys. Rev. Lett. 100 160501Google Scholar
[123] Adachi S H, Henderson M P 2015 arXiv preprint arXiv: 1510.06356
[124] Denil M, De Freitas N 2011 In Neural Information Processing Systems (NIPS) Conf. on Deep Learning and Unsupervised Feature Learning Workshop (Vol. 5) (2011)
[125] Amin M H, Andriyash E, Rolfe J, Kulchytskyy B, Melko R 2018 Phys. Rev. X 8 021050
[126] Wiebe N, Kapoor A, Svore K M 2014 arXiv preprint arXiv: 1412.3489
[127] Farhi E, Goldstone J, Gutmann S 2014 arXiv preprint arXiv: 1411.4028
[128] Lloyd S 2018 arXiv preprint arXiv: 1812.11075
[129] Verdon G, Arrazola J M, Brádler K, Killoran N 2019 arXiv preprint arXiv: 1902.00409
[130] Borle A, Elfving V E, Lomonaco S J 2020 arXiv preprint arXiv: 2006.15438
[131] Farhi E, Harrow A W 2016 arXiv preprint arXiv: 1602.07674
[132] Willsch M, Willsch D, Jin F, De Raedt H, Michielsen K 2020 Quantum Information Processing 19 1Google Scholar
[133] Harrigan M P, Sung K J, Neeley M, et al. 2021 Nat. Phys. 17 332Google Scholar
[134] Hastings M B 2019 arXiv preprint arXiv: 1905.07047
[135] Peruzzo A, McClean J, Shadbolt P, Yung M H, Zhou X Q, Love P J, Aspuru-Guzik A, O’brien J L 2014 Nat. Commun. 5 1
[136] Cao Y, Romero J, Olson J P, et al. 2019 Chem. Rev. 119 10856Google Scholar
[137] O’Malley P J, Babbush R, Kivlichan I D, et al. 2016 Phys. Rev. X 6 031007
[138] Shen Y, Zhang X, Zhang S, Zhang J N, Yung M H, Kim K 2017 Phys. Rev. A 95 020501Google Scholar
[139] Kandala A, Mezzacapo A, Temme K, Takita M, Brink M, Chow J M, Gambetta J M 2017 Nature 549 242Google Scholar
[140] Hempel C, Maier C, Romero J, et al. 2018 Phys. Rev. X 8 031022
[141] Colless J I, Ramasesh V V, Dahlen D, et al. 2018 Phys. Rev. X 8 011021
[142] Kirk D E 2004 Optimal Control Theory: An Introduction (Courier Corporation)
[143] Sutton R S, Barto A G, Williams R J 1992 IEEE Control Systems Magazine 12 19
[144] Kaelbling L P, Littman M L, Moore A W 1996 J. Artificial Intell. Res. 4 237Google Scholar
[145] Wiseman H M, Mancini S, Wang J 2002 Phys. Rev. A 66 013807Google Scholar
[146] Guţă M, Kot lowski W 2010 New J. Phys. 12 123032Google Scholar
[147] Magesan E, Gambetta J M, Córcoles A D, Chow J M 2015 Phys. Rev. Lett. 114 200501Google Scholar
[148] Hentschel A, Sanders B C 2010 Phys. Rev. Lett. 104 063603Google Scholar
[149] Lovett N B, Crosnier C, Perarnau-Llobet M, Sanders B C 2013 Phys. Rev. Lett. 110 220501Google Scholar
[150] Tiersch M, Ganahl E, Briegel H J 2015 Sci. Rep. 5 1Google Scholar
[151] Banchi L, Pancotti N, Bose S 2015 arXiv preprint arXiv: 1509.04298
[152] Wigley P B, Everitt P J, van den Hengel A, et al. 2016 Scientific Reports 6 1Google Scholar
[153] August M, Ni X 2017 Phys. Rev. A 95 012335Google Scholar
[154] Palittapongarnpim P, Wittek P, Zahedinejad E, Vedaie S, Sanders B C 2017 Neurocomputing 268 116Google Scholar
[155] Yang X C, Yung M H, Wang X 2018 Phys. Rev. A 97 042324Google Scholar
[156] He R H, Wang R, Wu J, Nie S S, Zhang J H, Wang Z M 2020 arXiv preprint arXiv: 2012.00326
[157] Ma H, Dong D, Ding S X, Chen C 2020 arXiv preprint arXiv: 2012.15427
[158] Fösel T, Niu M Y, Marquardt F, Li L 2021 arXiv preprint arXiv: 2103.07585
[159] Sgroi P, Palma G M, Paternostro M 2021 Phys. Rev. Lett. 126 020601Google Scholar
[160] An Z, Song H J, He Q K, Zhou D 2021 Phys. Rev. A 103 012404Google Scholar
[161] Dong D 2021 arXiv preprint arXiv: 2101.07461
[162] Xu H, Li J, Liu L, Wang Y, Yuan H, Wang X 2019 npj Quant. Inform. 5 82Google Scholar
[163] Ding Y, Ban Y, Martín-Guerrero J D, Solano E, Casanova J, Chen X 2021 Phys. Rev. A 103 L040401Google Scholar
[164] Ai M Z, Ding Y, Ban Y, Martín-Guerrero J D, Casanova J, Cui J M, Huang Y F, Chen X, Li C F, Guo G C 2021 arXiv preprint arXiv: 2101.09020
[165] Khaneja N, Reiss T, Kehlet C, Schulte-Herbrüggen T, Glaser S J 2005 J. Magnetic Resonance 172 296Google Scholar
[166] Caneva T, Calarco T, Montangero S 2011 Phys. Rev. A 84 022326Google Scholar
[167] Guo S F, Chen F, Liu Q, Xue M, Chen J J, Cao J H, Mao T W, Tey M K, You L 2020 arXiv preprint arXiv: 2011.11987
[168] Landau L D 1932 Phys. Z. Sowjetunion 2 19
[169] Zener C 1932 Proceedings of the Royal Society of London (Series A) 137 696
[170] Morita S 2007 J. Phys. Soc. Japn. 76 104001Google Scholar
[171] Avron J, Fraas M, Graf G, Grech P 2010 Phys. Rev. A 82 040304Google Scholar
[172] Zeng L, Zhang J, Sarovar M 2016 J.Phys. A: Mathematical and Theoretical 49 165305Google Scholar
[173] Lin J, Lai Z Y, Li X 2020 Phys. Rev. A 101 052327Google Scholar
[174] Chen X, Lizuain I, Ruschhaupt A, Guéry-Odelin D, Muga J 2010 Phys. Rev. Lett. 105 123003Google Scholar
[175] Chen Y Q, Chen Y, Lee C K, Zhang S, Hsieh C Y 2020 arXiv preprint arXiv: 2004.02836
[176] Yang X, Liu R, Li J, Peng X 2020 Phys. Rev. A 102 012614Google Scholar
[177] [178] Rezakhani A, Kuo W J, Hamma A, Lidar D, Zanardi P 2009 Phys. Rev. Lett. 103 080502Google Scholar
[179] Rezakhani A, Pimachev A, Lidar D 2010 Phys. Rev. A 82 052305Google Scholar
[180] Farhi E, Goldstone J, Gosset D, Gutmann S, Meyer H B, Shor P 2009 arXiv preprint arXiv: 0909.4766
[181] McKiernan K A, Davis E, Alam M S, Rigetti C 2019 arXiv preprint arXiv: 1908.08054
[182] Zhang Y H, Zheng P L, Zhang Y, Deng D L 2020 Phys. Rev. Lett. 125 170501Google Scholar
[183] Ostaszewski M, Trenkwalder L M, Masarczyk W, Scerri E, Dunjko V 2021 arXiv preprint arXiv: 2103.16089
[184] Peng P, Huang X, Yin C, Joseph L, Ramanathan C, Cappellaro P 2021 arXiv preprint arXiv: 2102.13161
[185] Nautrup H P, Delfosse N, Dunjko V, Briegel H J, Friis N 2019 Quantum 3 215Google Scholar
[186] Bolens A, Heyl M 2020 arXiv preprint arXiv: 2006.16269
[187] Sweke R, Kesselring M S, van Nieuwenburg E P, Eisert J 2020 Machine Learning: Science and Technology 2 025005
-
图 1 强化学习辅助绝热量子算法设计的示意图[173]. 其中强化学习中的智能体(agent)根据绝热量子计算(AQC)输出的结果来获取奖励, 并根据深度神经网络近似表示的Q值表格来选择动作更新绝热量子算法
Fig. 1. Schematic diagram of the reinforcement learning approach for quantum adiabatic algorithm design[173]. The learning agent collects the reward according to the result obtained from adiabatic quantum computing (AQC) and produces an action to update the quantum adiabatic algorithm based on its Q table represented by a deep neural network.
图 2 强化学习辅助设计的绝热量子算法在Grover搜索问题上的表现[173]. 其中成功概率(success probability)是演化终态与目标态交叠的平方, 总的演化时间T与系统规模n的关系为
$ T = \sqrt{2^n}$ . 图中蓝色虚线表示的线性演化路径成功概率会随着系统尺寸增大不断降低. 红色实线和黑色虚线分别表示强化学习设计得到的演化路径和解析获得的非线性路径[66]的表现. 在选择的演化时间下, 两者的成功概率都能接近于1, 说明两者都具有平方的量子加速Fig. 2. Performance of reinforcement learning designed quantum adiabatic algorithm in success probability for Grover search problem[173]. The success probability is obtained by taking the square of wave-function overlap of the final evolved quantum state with the target state. The total adiabatic evolution time is chosen as
$ T = \sqrt{2^n}$ where n is the system size. The blue dashed line denotes the success probability of linear path which decreases as increasing the system size. The red solid line and black dashed line denote the performance of the reinforcement learning designed path and the nonlinear path[66], respectively. Given the choice of total evolution time, the success probability close to 1 by both implies that they both exhibit quadratic quantum speed up.图 3 强化学习在Grover搜索问题的绝热量子算法设计中的拓展性[173]. 其中绿线是线性路径的表现, 蓝线是将10 qubits系统中强化学习学到的路径推广到更大系统, 橘线是将在n qubits系统强化学习获得的路径推广到
$ n+1$ qubits系统Fig. 3. Transferability of reinforcement learning based quantum adiabatic algorithm design for Grover search problem[173]. The green line denotes the infidelity of linear path. The blue line denotes the infidelity of the path obtained by training the 10 qubits system. The orange line denotes the performance of applying the path learned from the n qubits system to the
$ n+1$ qubits system. -
[1] Benioff P 1980 J. Statistical Phys. 22 563Google Scholar
[2] Feynman R P 1982 Int. J. Theor. Phys. 21 133
[3] Deutsch D E 1989 Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 425 73Google Scholar
[4] Yao A C C 1993 Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science (IEEE) pp352−361
[5] Shor P W 1994 Proceedings 35th annual symposium on foundations of computer science (IEEE) pp124−134
[6] Ekert A, Jozsa R 1996 Rev. Mod. Phys. 68 733Google Scholar
[7] Gerjuoy E 2005 Am. J. Phys. 73 521Google Scholar
[8] Aumasson J P 2017 Computer Fraud & Security 2017 8
[9] Vandersypen L M, Steffen M, Breyta G, Yannoni C S, Sherwood M H, Chuang I L 2001 Nature 414 883Google Scholar
[10] Lu C Y, Browne D E, Yang T, Pan J W 2007 Phys. Rev. Lett. 99 250504Google Scholar
[11] Politi A, Matthews J C, O’brien J L 2009 Science 325 1221Google Scholar
[12] Monz T, Nigg D, Martinez E A, et al. 2016 Science 351 1068Google Scholar
[13] Ladd T D, Jelezko F, Laflamme R, Nakamura Y, Monroe C, O’Brien J L 2010 Nature 464 45Google Scholar
[14] Bernstein E, Vazirani U 1997 SIAM J. Comp. 26 1411Google Scholar
[15] Nielsen M A, Chuang I 2002 Quantum Computation and Quantum Information (Cambridge: Cambridge University Press)
[16] Shor P W 2003 J. ACM (JACM) 50 87Google Scholar
[17] Watrous J 2008 arXiv preprint arXiv: 0804.3401
[18] Simon D R 1997 SIAM J. Comp. 26 1474Google Scholar
[19] Hallgren S 2002 Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing pp653−658
[20] Grover L K 1997 Phys. Rev. Lett. 79 325Google Scholar
[21] Shao C, Li Y, Li H 2019 J. Syst. Sci. 32 375Google Scholar
[22] Farhi E, Goldstone J, Gutmann S, Sipser M 2000 arXiv preprint quant-ph/0001106
[23] Farhi E, Goldstone J, Gutmann S, Lapan J, Lundgren A, Preda D 2001 Science 292 472Google Scholar
[24] Zhang D J, Yu X D, Tong D 2014 Phys. Rev. A 90 042321Google Scholar
[25] Aharonov D, Van Dam W, Kempe J, Landau Z, Lloyd S, Regev O 2008 SIAM Rev. 50 755Google Scholar
[26] Yu H, Huang Y, Wu B 2018 Chin. Phys. Lett. 35 110303Google Scholar
[27] Dong D, Petersen I R 2010 IET Control Theory & Applications 4 2651
[28] Cirac J I, Zoller P 2012 Nat. Phys. 8 264Google Scholar
[29] Georgescu I M, Ashhab S, Nori F 2014 Rev. Mod. Phys. 86 153Google Scholar
[30] Gross C, Bloch I 2017 Science 357 995Google Scholar
[31] Rice J R 1976 In Advances in Computers (Vol. 15) (Elsevier) pp65–118
[32] Hutter F, Hoos H H, Leyton-Brown K, Stützle T 2009 Journal of Artificial Intelligence Research 36 267Google Scholar
[33] Wang L 2016 Phys. Rev. B 94 195105Google Scholar
[34] Carrasquilla J, Melko R G 2017 Nat. Phys. 13 431Google Scholar
[35] Van Nieuwenburg E P, Liu Y H, Huber S D 2017 Nat. Phys. 13 435Google Scholar
[36] Deng D L, Li X, Sarma S D 2017 Phys. Rev. X 7 021021
[37] Zhang P, Shen H, Zhai H 2018 Phys. Rev. Lett. 120 066401Google Scholar
[38] Gao X, Duan L M 2017 Nat. Commun. 8 1Google Scholar
[39] Huang Y, Moore J E 2017 arXiv preprint arXiv: 1701.06246
[40] Cai Z, Liu J 2018 Phys. Rev. B 97 035116Google Scholar
[41] Carleo G, Troyer M 2017 Science 355 602Google Scholar
[42] Day A G, Bukov M, Weinberg P, Mehta P, Sels D 2019 Phys. Rev. Lett. 122 020601Google Scholar
[43] Niu M Y, Boixo S, Smelyanskiy V N, Neven H 2019 npj Quantum Information 5 33Google Scholar
[44] Zhang X M, Wei Z, Asad R, Yang X C, Wang X 2019 npj Quantum Information 5 85Google Scholar
[45] Bukov M, Day A G, Sels D, Weinberg P, Polkovnikov A, Mehta P 2018 Phys. Rev. X 8 031086
[46] Aaronson S 2015 Nat. Phys. 11 291Google Scholar
[47] Albash T, Lidar D A 2018 Rev. Mod. Phys. 90 015002Google Scholar
[48] Tong D 2010 Phys. Rev. Lett. 104 120401Google Scholar
[49] Amin M H 2009 Phys. Rev. Lett. 102 220401Google Scholar
[50] Altshuler B, Krovi H, Roland J 2010 Proceedings of the National Academy of Sciences 107 12446Google Scholar
[51] Jörg T, Krzakala F, Semerjian G, Zamponi F 2010 Phys. Rev. Lett. 104 207206Google Scholar
[52] Dickson N G, Amin M 2011 Phys. Rev. Lett. 106 050502Google Scholar
[53] Hen I, Young A 2011 Phys. Rev. E 84 061152Google Scholar
[54] Bapst V, Foini L, Krzakala F, Semerjian G, Zamponi F 2013 Phys. Rep. 523 127Google Scholar
[55] Hauke P, Katzgraber H G, Lechner W, Nishimori H, Oliver W D 2020 Rep. Prog. Phys. 83 054401Google Scholar
[56] Santoro G E, Martoňák R, Tosatti E, Car R 2002 Science 295 2427Google Scholar
[57] Boixo S, Albash T, Spedalieri F M, Chancellor N, Lidar D A 2013 Nat. Commun. 4 1
[58] Sherrington D, Kirkpatrick S 1975 Phys. Rev. Lett. 35 1792Google Scholar
[59] Barahona F 1982 Journal of Physics A: Mathematical and General 15 3241Google Scholar
[60] Kirkpatrick T R, Thirumalai D 1987 Phys. Rev. B 36 5388Google Scholar
[61] Mézard M, Parisi G, Virasoro M A 1987 Spin Glass Theory and Beyond: An Introduction to the Replica Method and Its Applications (Vol. 9) (Singapore: World Scientific Publishing Company)
[62] Hartmann A K, Weigt M 2005 Phase Transitions in Combinatorial Optimization Problems (Vol. 67) (Wiley Online Library)
[63] Mezard M, Montanari A 2009 Information, Physics, and Computation (Oxford University Press)
[64] Karp R M 1972 In Complexity of Computer Computations (Berlin: Springer) pp85–103
[65] Lucas A 2014 Frontiers in Physics 2 5
[66] Roland J, Cerf N J 2002 Phys. Rev. A 65 042308Google Scholar
[67] Gendreau M, Potvin J Y, et al. 2010 Handbook of Metaheuristics (Vol. 2) (Berlin: Springer)
[68] Meletiou G, Tasoulis D, Vrahatis M N, et al. 2002 In IASTED 2002 Conference on Artificial Intelligence pp483–488
[69] Stekel A, Chkroun M, Azaria A 2018 arXiv: 1803.09237
[70] Yampolskiy R V 2010 International Journal of Bio-Inspired Computation 2 115Google Scholar
[71] Monaco J V, Vindiola M M 2017 In 2017 IEEE International Symposium on Circuits and Systems (ISCAS) pp1−4
[72] Borders W A, Pervaiz A Z, Fukami S, Camsari K Y, Ohno H, Datta S 2019 Nature 573 390Google Scholar
[73] Preskill J 2018 Quantum 2 79Google Scholar
[74] Dash A, Sarmah D, Behera B K, Panigrahi P K 2018 arXiv: 1805.10478
[75] Dridi R, Alghassi H 2017 Sci. Rep. 7 1Google Scholar
[76] Xu K, Xie T, Li Z, et al. 2017 Phys. Rev. Lett. 118 130504Google Scholar
[77] Jiang S, Britt K A, McCaskey A, Humble T, Kais S 2018 Sci. Rep. 8 17667Google Scholar
[78] Wang B, Hu F, Yao H, Wang C 2020 Sci. Rep. 10 1Google Scholar
[79] Peng X, Liao Z, Xu N, Qin G, Zhou X, Suter D, Du J 2008 Phys. Rev. Lett. 101 220405Google Scholar
[80] Bernstein E, Vazirani U 1993 ACM, New York 11
[81] Knill E, Laflamme R 2001 Inform. Proc. Lett. 79 173Google Scholar
[82] Freedman M H, Larsen M, Wang Z 2002 Commun. Math. Phys. 227 605Google Scholar
[83] Freedman M H, Kitaev A, Wang Z 2002 Commun. Math. Phys. 227 587Google Scholar
[84] Wocjan P, Zhang S 2006 arXiv preprint quant-ph/0606179
[85] Somma R D, Nagaj D, Kieferová M 2012 Phys. Rev. Lett. 109 050501Google Scholar
[86] Solomonoff R J 1985 Human Systems Management 5 149Google Scholar
[87] Bishop C M 2006 Pattern Recognition and Machine Learning (Berlin: Springer)
[88] Indurkhya N, Damerau F J 2010 Handbook of Natural Language Processing (Vol. 2) (Los Angeles: CRC Press)
[89] Sutton R S, Barto A G 2018 Reinforcement Learning: An Introduction (Cambridge: MIT Press)
[90] Rumelhart D E, Hinton G E, Williams R J 1986 Nature 323 533Google Scholar
[91] Alpaydin E 2020 Introduction to Machine Learning (Cambridge: MIT Press)
[92] Silver D, Huang A, Maddison C J, et al. 2016 Nature 529 484Google Scholar
[93] Silver D, Schrittwieser J, Simonyan K, et al. 2017 Nature 550 354Google Scholar
[94] Silver D, Hubert T, Schrittwieser J, et al. 2018 Science 362 1140Google Scholar
[95] Schrittwieser J, Antonoglou I, Hubert T, et al. 2020 Nature 588 604Google Scholar
[96] Wolpert D H, Macready W G 1997 IEEE Transactions on Evolutionary Computation 1 67Google Scholar
[97] Kerschke P, Hoos H H, Neumann F, Trautmann H 2019 Evolutionary Computation 27 3Google Scholar
[98] Lagoudakis M G, Littman M L 2000 ICML pp511–518
[99] Gomes C P, Selman B 2001 Artificial Intelligence 126 43Google Scholar
[100] Leyton-Brown K, Nudelman E, Shoham Y 2002 International Conference on Principles and Practice of Constraint Programming (Berlin: Springer) pp556−572
[101] Leyton-Brown K, Nudelman E, Andrew G, McFadden J, Shoham Y 2003 In IJCAI (Vol. 3) pp1542−1543
[102] Xu L, Hutter F, Hoos H H, Leyton-Brown K 2008 Journal of Artificial Intelligence Research 32 565Google Scholar
[103] Smith-Miles K A 2009 ACM Computing Surveys (CSUR) 41 1
[104] Kotthoff L, Gent I P, Miguel I 2012 Ai Communications 25 257Google Scholar
[105] Mısır M, Sebag M 2017 Artificial Intelligence 244 291Google Scholar
[106] Ansótegui C, Sellmann M, Tierney K 2009 International Conference on Principles and Practice of Constraint Programming (Springer) pp142−157
[107] Hutter F, Hoos H H, Leyton-Brown K 2011 International Conference on Learning and Intelligent Optimization (Berlin: Springer) pp507−523
[108] Fitzgerald T, Malitsky Y, O’Sullivan B, Tierney K 2014 Seventh Annual Symposium on Combinatorial Search
[109] López-Ibánez M, Dubois-Lacoste J, Cáceres L P, Birattari M, Stützle T 2016 Operations Research Perspectives 3 43Google Scholar
[110] Biedenkapp A, Bozkurt H F, Eimer T, Hutter F, Lindauer M 2020 Proceedings of the Twentyfourth European Conference on Artificial Intelligence (ECAI’20), Jun 2020
[111] Speck D, Biedenkapp A, Hutter F, Mattmüller R, Lindauer M 2020 arXiv preprint arXiv: 2006.08246
[112] Xu L, Hoos H, Leyton-Brown K 2010 Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 24)
[113] Biamonte J, Wittek P, Pancotti N, Rebentrost P, Wiebe N, Lloyd S 2017 Nature 549 195Google Scholar
[114] Harrow A W, Hassidim A, Lloyd S 2009 Phys. Rev. Lett. 103 150502Google Scholar
[115] Childs A M, Kothari R, Somma R D 2017 SIAM J. Comput. 46 1920Google Scholar
[116] Wiebe N, Braun D, Lloyd S 2012 Phys. Rev. Lett. 109 050505Google Scholar
[117] Rebentrost P, Schuld M, Wossnig L, Petruccione F, Lloyd S 2019 New J. Phys. 21 073023Google Scholar
[118] Brandao F G, Svore K M 2017 In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE) pp415−426
[119] Lloyd S, Mohseni M, Rebentrost P 2014 Nat. Phys. 10 631Google Scholar
[120] Lloyd S, Garnerone S, Zanardi P 2016 Nat. Commun. 7 1
[121] Rebentrost P, Mohseni M, Lloyd S 2014 Phys. Rev. Lett. 113 130503Google Scholar
[122] Giovannetti V, Lloyd S, Maccone L 2008 Phys. Rev. Lett. 100 160501Google Scholar
[123] Adachi S H, Henderson M P 2015 arXiv preprint arXiv: 1510.06356
[124] Denil M, De Freitas N 2011 In Neural Information Processing Systems (NIPS) Conf. on Deep Learning and Unsupervised Feature Learning Workshop (Vol. 5) (2011)
[125] Amin M H, Andriyash E, Rolfe J, Kulchytskyy B, Melko R 2018 Phys. Rev. X 8 021050
[126] Wiebe N, Kapoor A, Svore K M 2014 arXiv preprint arXiv: 1412.3489
[127] Farhi E, Goldstone J, Gutmann S 2014 arXiv preprint arXiv: 1411.4028
[128] Lloyd S 2018 arXiv preprint arXiv: 1812.11075
[129] Verdon G, Arrazola J M, Brádler K, Killoran N 2019 arXiv preprint arXiv: 1902.00409
[130] Borle A, Elfving V E, Lomonaco S J 2020 arXiv preprint arXiv: 2006.15438
[131] Farhi E, Harrow A W 2016 arXiv preprint arXiv: 1602.07674
[132] Willsch M, Willsch D, Jin F, De Raedt H, Michielsen K 2020 Quantum Information Processing 19 1Google Scholar
[133] Harrigan M P, Sung K J, Neeley M, et al. 2021 Nat. Phys. 17 332Google Scholar
[134] Hastings M B 2019 arXiv preprint arXiv: 1905.07047
[135] Peruzzo A, McClean J, Shadbolt P, Yung M H, Zhou X Q, Love P J, Aspuru-Guzik A, O’brien J L 2014 Nat. Commun. 5 1
[136] Cao Y, Romero J, Olson J P, et al. 2019 Chem. Rev. 119 10856Google Scholar
[137] O’Malley P J, Babbush R, Kivlichan I D, et al. 2016 Phys. Rev. X 6 031007
[138] Shen Y, Zhang X, Zhang S, Zhang J N, Yung M H, Kim K 2017 Phys. Rev. A 95 020501Google Scholar
[139] Kandala A, Mezzacapo A, Temme K, Takita M, Brink M, Chow J M, Gambetta J M 2017 Nature 549 242Google Scholar
[140] Hempel C, Maier C, Romero J, et al. 2018 Phys. Rev. X 8 031022
[141] Colless J I, Ramasesh V V, Dahlen D, et al. 2018 Phys. Rev. X 8 011021
[142] Kirk D E 2004 Optimal Control Theory: An Introduction (Courier Corporation)
[143] Sutton R S, Barto A G, Williams R J 1992 IEEE Control Systems Magazine 12 19
[144] Kaelbling L P, Littman M L, Moore A W 1996 J. Artificial Intell. Res. 4 237Google Scholar
[145] Wiseman H M, Mancini S, Wang J 2002 Phys. Rev. A 66 013807Google Scholar
[146] Guţă M, Kot lowski W 2010 New J. Phys. 12 123032Google Scholar
[147] Magesan E, Gambetta J M, Córcoles A D, Chow J M 2015 Phys. Rev. Lett. 114 200501Google Scholar
[148] Hentschel A, Sanders B C 2010 Phys. Rev. Lett. 104 063603Google Scholar
[149] Lovett N B, Crosnier C, Perarnau-Llobet M, Sanders B C 2013 Phys. Rev. Lett. 110 220501Google Scholar
[150] Tiersch M, Ganahl E, Briegel H J 2015 Sci. Rep. 5 1Google Scholar
[151] Banchi L, Pancotti N, Bose S 2015 arXiv preprint arXiv: 1509.04298
[152] Wigley P B, Everitt P J, van den Hengel A, et al. 2016 Scientific Reports 6 1Google Scholar
[153] August M, Ni X 2017 Phys. Rev. A 95 012335Google Scholar
[154] Palittapongarnpim P, Wittek P, Zahedinejad E, Vedaie S, Sanders B C 2017 Neurocomputing 268 116Google Scholar
[155] Yang X C, Yung M H, Wang X 2018 Phys. Rev. A 97 042324Google Scholar
[156] He R H, Wang R, Wu J, Nie S S, Zhang J H, Wang Z M 2020 arXiv preprint arXiv: 2012.00326
[157] Ma H, Dong D, Ding S X, Chen C 2020 arXiv preprint arXiv: 2012.15427
[158] Fösel T, Niu M Y, Marquardt F, Li L 2021 arXiv preprint arXiv: 2103.07585
[159] Sgroi P, Palma G M, Paternostro M 2021 Phys. Rev. Lett. 126 020601Google Scholar
[160] An Z, Song H J, He Q K, Zhou D 2021 Phys. Rev. A 103 012404Google Scholar
[161] Dong D 2021 arXiv preprint arXiv: 2101.07461
[162] Xu H, Li J, Liu L, Wang Y, Yuan H, Wang X 2019 npj Quant. Inform. 5 82Google Scholar
[163] Ding Y, Ban Y, Martín-Guerrero J D, Solano E, Casanova J, Chen X 2021 Phys. Rev. A 103 L040401Google Scholar
[164] Ai M Z, Ding Y, Ban Y, Martín-Guerrero J D, Casanova J, Cui J M, Huang Y F, Chen X, Li C F, Guo G C 2021 arXiv preprint arXiv: 2101.09020
[165] Khaneja N, Reiss T, Kehlet C, Schulte-Herbrüggen T, Glaser S J 2005 J. Magnetic Resonance 172 296Google Scholar
[166] Caneva T, Calarco T, Montangero S 2011 Phys. Rev. A 84 022326Google Scholar
[167] Guo S F, Chen F, Liu Q, Xue M, Chen J J, Cao J H, Mao T W, Tey M K, You L 2020 arXiv preprint arXiv: 2011.11987
[168] Landau L D 1932 Phys. Z. Sowjetunion 2 19
[169] Zener C 1932 Proceedings of the Royal Society of London (Series A) 137 696
[170] Morita S 2007 J. Phys. Soc. Japn. 76 104001Google Scholar
[171] Avron J, Fraas M, Graf G, Grech P 2010 Phys. Rev. A 82 040304Google Scholar
[172] Zeng L, Zhang J, Sarovar M 2016 J.Phys. A: Mathematical and Theoretical 49 165305Google Scholar
[173] Lin J, Lai Z Y, Li X 2020 Phys. Rev. A 101 052327Google Scholar
[174] Chen X, Lizuain I, Ruschhaupt A, Guéry-Odelin D, Muga J 2010 Phys. Rev. Lett. 105 123003Google Scholar
[175] Chen Y Q, Chen Y, Lee C K, Zhang S, Hsieh C Y 2020 arXiv preprint arXiv: 2004.02836
[176] Yang X, Liu R, Li J, Peng X 2020 Phys. Rev. A 102 012614Google Scholar
[177] [178] Rezakhani A, Kuo W J, Hamma A, Lidar D, Zanardi P 2009 Phys. Rev. Lett. 103 080502Google Scholar
[179] Rezakhani A, Pimachev A, Lidar D 2010 Phys. Rev. A 82 052305Google Scholar
[180] Farhi E, Goldstone J, Gosset D, Gutmann S, Meyer H B, Shor P 2009 arXiv preprint arXiv: 0909.4766
[181] McKiernan K A, Davis E, Alam M S, Rigetti C 2019 arXiv preprint arXiv: 1908.08054
[182] Zhang Y H, Zheng P L, Zhang Y, Deng D L 2020 Phys. Rev. Lett. 125 170501Google Scholar
[183] Ostaszewski M, Trenkwalder L M, Masarczyk W, Scerri E, Dunjko V 2021 arXiv preprint arXiv: 2103.16089
[184] Peng P, Huang X, Yin C, Joseph L, Ramanathan C, Cappellaro P 2021 arXiv preprint arXiv: 2102.13161
[185] Nautrup H P, Delfosse N, Dunjko V, Briegel H J, Friis N 2019 Quantum 3 215Google Scholar
[186] Bolens A, Heyl M 2020 arXiv preprint arXiv: 2006.16269
[187] Sweke R, Kesselring M S, van Nieuwenburg E P, Eisert J 2020 Machine Learning: Science and Technology 2 025005
计量
- 文章访问数: 7256
- PDF下载量: 315
- 被引次数: 0