{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T23:42:11Z","timestamp":1740181331262,"version":"3.37.3"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,10,30]],"date-time":"2020-10-30T00:00:00Z","timestamp":1604016000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,10,30]],"date-time":"2020-10-30T00:00:00Z","timestamp":1604016000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-AC36-08GO28308"],"award-info":[{"award-number":["DE-AC36-08GO28308"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation","award":["PHY-1653820"],"award-info":[{"award-number":["PHY-1653820"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Mach. Intell."],"published-print":{"date-parts":[[2020,12]]},"DOI":"10.1007\/s42484-020-00026-6","type":"journal-article","created":{"date-parts":[[2020,10,30]],"date-time":"2020-10-30T12:02:43Z","timestamp":1604059363000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["K-spin Hamiltonian for quantum-resolvable Markov decision processes"],"prefix":"10.1007","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9721-742X","authenticated-orcid":false,"given":"Eric B.","family":"Jones","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Graf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eliot","family":"Kapit","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wesley","family":"Jones","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,10,30]]},"reference":[{"issue":"3","key":"26_CR1","first-page":"031016","volume":"8","author":"T Albash","year":"2018","unstructured":"Albash T, Lidar DA (2018) Demonstration of a scaling advantage for a quantum annealer over simulated annealing. Phys Rev X 8(3):031016","journal-title":"Phys Rev X"},{"issue":"3","key":"26_CR2","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.physrep.2012.10.002","volume":"523","author":"V Bapst","year":"2013","unstructured":"Bapst V, Foini L, Krzakala F, Semerjian G, Zamponi F (2013) The quantum adiabatic algorithm applied to random optimization problems: the quantum spin glass perspective. Phys Rep 523(3):127\u2013205","journal-title":"Phys Rep"},{"issue":"10","key":"26_CR3","doi-asserted-by":"publisher","first-page":"3241","DOI":"10.1088\/0305-4470\/15\/10\/028","volume":"15","author":"F Barahona","year":"1982","unstructured":"Barahona F (1982) On the computational complexity of ising spin glass models. J Phys A Math Gen 15(10):3241","journal-title":"J Phys A Math Gen"},{"issue":"5","key":"26_CR4","doi-asserted-by":"publisher","first-page":"3457","DOI":"10.1103\/PhysRevA.52.3457","volume":"52","author":"A Barenco","year":"1995","unstructured":"Barenco A, Bennett CH, Cleve R, DiVincenzo DP, Margolus N, Shor P, Sleator T, Smolin JA, Weinfurter H (1995) Elementary gates for quantum computation. Phys Rev A 52(5):3457","journal-title":"Phys Rev A"},{"issue":"6","key":"26_CR5","first-page":"1","volume":"33","author":"AC Barry","year":"2000","unstructured":"Barry AC (2000) The ising model is np-complete. SIAM News 33(6):1\u20133","journal-title":"SIAM News"},{"key":"26_CR6","unstructured":"Boothby K, Bunyk P, Raymond J, Roy A (2019) Next-generation topology of d-wave quantum processors. Technical report, Technical report"},{"issue":"1-3","key":"26_CR7","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(01)00341-9","volume":"123","author":"E Boros","year":"2002","unstructured":"Boros E, Hammer PL (2002) Pseudo-boolean optimization. Discret Appl Math 123(1-3):155\u2013225","journal-title":"Discret Appl Math"},{"key":"26_CR8","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1038\/srep00400","volume":"2","author":"HJ Briegel","year":"2012","unstructured":"Briegel HJ, De las Cuevas G (2012) Projective simulation for artificial intelligence. Sci Rep 2:400","journal-title":"Sci Rep"},{"key":"26_CR9","unstructured":"Brockman G, Cheung V, Pettersson L, Schneider J, Schulman J, Tang J, Zaremba W (2016) Openai gym. arXiv:1606.01540"},{"key":"26_CR10","unstructured":"Dattani N (2019) Quadratization in discrete optimization and quantum mechanics. arXiv:1901.04405"},{"issue":"2","key":"26_CR11","doi-asserted-by":"publisher","first-page":"020601","DOI":"10.1103\/PhysRevLett.122.020601","volume":"122","author":"AGR Day","year":"2019","unstructured":"Day AGR, Bukov M, Weinberg P, Mehta P, Dries S (2019) Glassy phase of optimal quantum control. Phys Rev Lett 122(2):020601","journal-title":"Phys Rev Lett"},{"issue":"3","key":"26_CR12","first-page":"031015","volume":"6","author":"VS Denchev","year":"2016","unstructured":"Denchev VS, Boixo S, Isakov SV, Ding N, Babbush R, Smelyanskiy V, Martinis J, Neven H (2016) What is the computational value of finite-range tunneling?. Phys Rev X 6(3):031015","journal-title":"Phys Rev X"},{"issue":"2","key":"26_CR13","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1103\/PhysRevLett.45.79","volume":"45","author":"B Derrida","year":"1980","unstructured":"Derrida B (1980) Random-energy model: limit of a family of disordered models. Phys Rev Lett 45(2):79","journal-title":"Phys Rev Lett"},{"issue":"5","key":"26_CR14","doi-asserted-by":"publisher","first-page":"1207","DOI":"10.1109\/TSMCB.2008.925743","volume":"38","author":"D Dong","year":"2008","unstructured":"Dong D, Chen C, Li H, Tarn TJ (2008) Quantum reinforcement learning. IEEE Trans Sys Man Cybern Part B Cybern 38(5):1207\u20131220","journal-title":"IEEE Trans Sys Man Cybern Part B Cybern"},{"issue":"2","key":"26_CR15","doi-asserted-by":"publisher","first-page":"023006","DOI":"10.1088\/1367-2630\/17\/2\/023006","volume":"17","author":"V Dunjko","year":"2015","unstructured":"Dunjko V, Friis N, Hans JB (2015) Quantum-enhanced deliberation of learning agents using trapped ions. New J Phys 17(2):023006","journal-title":"New J Phys"},{"issue":"13","key":"26_CR16","doi-asserted-by":"publisher","first-page":"130501","DOI":"10.1103\/PhysRevLett.117.130501","volume":"117","author":"V Dunjko","year":"2016","unstructured":"Dunjko V, Taylor JM, Hans JB (2016) Quantum-enhanced machine learning. Phys Rev Lett 117(13):130501","journal-title":"Phys Rev Lett"},{"key":"26_CR17","doi-asserted-by":"crossref","unstructured":"Dunjko V, Taylor JM, Hans JB (2017) Advances in quantum reinforcement learning. In: IEEE international conference on systems, man, and cybernetics (SMC), pp 282\u2013287. IEEE","DOI":"10.1109\/SMC.2017.8122616"},{"issue":"2","key":"26_CR18","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0022-1236(83)90066-6","volume":"50","author":"EB Dynkin","year":"1983","unstructured":"Dynkin EB (1983) Markov processes as a tool in field theory. J Funct Anal 50(2):167\u2013187","journal-title":"J Funct Anal"},{"issue":"5","key":"26_CR19","doi-asserted-by":"publisher","first-page":"052334","DOI":"10.1103\/PhysRevA.86.052334","volume":"86","author":"E Farhi","year":"2012","unstructured":"Farhi E, Gosset D, Hen I, Sandvik AW, Shor P, Young AP, Francesco Z (2012) Performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs. Phys Rev A 86(5):052334","journal-title":"Phys Rev A"},{"key":"26_CR20","unstructured":"Farhi E, Goldstone J, Gutmann S (2014) A quantum approximate optimization algorithm. arXiv:1411.4028"},{"key":"26_CR21","doi-asserted-by":"crossref","unstructured":"Fix A, Gruber A, Boros E, Ramin Z (2011) A graph cut algorithm for higher-order markov random fields. In: International conference on computer vision, pp. 1020\u20131027. IEEE, p 2011","DOI":"10.1109\/ICCV.2011.6126347"},{"key":"26_CR22","doi-asserted-by":"crossref","unstructured":"Golovin N, Rahm E (2004) Reinforcement learning architecture for web recommendations. In: International conference on information technology: coding and computing, 2004. Proceedings. ITCC 2004. vol 1, pp 398\u2013402. IEEE","DOI":"10.1109\/ITCC.2004.1286487"},{"key":"26_CR23","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to parallel computation: p-completeness theory","author":"R Greenlaw","year":"1995","unstructured":"Greenlaw R, Hoover JH, Ruzzo WL, et al. (1995) Limits to parallel computation: p-completeness theory. Oxford University Press on Demand, Oxford"},{"key":"26_CR24","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/j.cpc.2015.02.015","volume":"192","author":"SV Isakov","year":"2015","unstructured":"Isakov SV, Zintchenko IN, R\u00f8nnow TF, Troyer M (2015) Optimised simulated annealing for ising spin glasses. Comput Phys Commun 192:265\u2013271","journal-title":"Comput Phys Commun"},{"key":"26_CR25","doi-asserted-by":"crossref","unstructured":"Jones EB, Kapit E, Chang CY, Biagioni D, Vaidhynathan D, Graf P, Jones W (2020) On the computational viability of quantum optimization for pmu placement. arXiv:2001.04489","DOI":"10.1109\/PESGM41954.2020.9281420"},{"issue":"5","key":"26_CR26","doi-asserted-by":"publisher","first-page":"5355","DOI":"10.1103\/PhysRevE.58.5355","volume":"58","author":"T Kadowaki","year":"1998","unstructured":"Kadowaki T, Nishimori H (1998) Quantum annealing in the transverse ising model. Phys Rev E 58(5):5355","journal-title":"Phys Rev E"},{"issue":"11","key":"26_CR27","doi-asserted-by":"publisher","first-page":"P11011","DOI":"10.1088\/1742-5468\/2005\/11\/P11011","volume":"2005","author":"HJ Kappen","year":"2005","unstructured":"Kappen HJ (2005) Path integrals and symmetry breaking for optimal control theory. J Stat Mech Theory Exp 2005(11):P11011","journal-title":"J Stat Mech Theory Exp"},{"issue":"2","key":"26_CR28","doi-asserted-by":"publisher","first-page":"1201","DOI":"10.1007\/s11128-012-0465-9","volume":"12","author":"P Kumar","year":"2013","unstructured":"Kumar P (2013) Direct implementation of an n-qubit controlled-unitary gate in a single step. Quantum Inf Process 12(2):1201\u20131223","journal-title":"Quantum Inf Process"},{"issue":"1","key":"26_CR29","doi-asserted-by":"publisher","first-page":"1609","DOI":"10.1038\/s41598-017-01711-6","volume":"7","author":"L Lamata","year":"2017","unstructured":"Lamata L (2017) Basic protocols in quantum reinforcement learning with superconducting circuits. Sci Rep 7(1):1609","journal-title":"Sci Rep"},{"issue":"7","key":"26_CR30","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s11128-019-2323-5","volume":"18","author":"A Lucas","year":"2019","unstructured":"Lucas A (2019) Hard combinatorial problems and minor embeddings on lattice graphs. Quantum Inf Process 18(7):203","journal-title":"Quantum Inf Process"},{"key":"26_CR31","doi-asserted-by":"publisher","first-page":"71","DOI":"10.3389\/fphy.2017.00071","volume":"5","author":"F Neukart","year":"2018","unstructured":"Neukart F, Dollen DV, Seidel C, Compostella G (2018) Quantum-enhanced reinforcement learning for finite-episode games with discrete state spaces. Front Phys 5:71","journal-title":"Front Phys"},{"key":"26_CR32","doi-asserted-by":"crossref","unstructured":"Nielsen MA, Chuang I (2002) Quantum computation and quantum information","DOI":"10.1119\/1.1463744"},{"issue":"3","key":"26_CR33","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1287\/moor.12.3.441","volume":"12","author":"CH Papadimitriou","year":"1987","unstructured":"Papadimitriou CH, Tsitsiklis JN (1987) The complexity of markov decision processes. Math Oper Res 12(3):441\u2013450","journal-title":"Math Oper Res"},{"issue":"3","key":"26_CR34","first-page":"031002","volume":"4","author":"GD Paparo","year":"2014","unstructured":"Paparo GD, Dunjko V, Makmal A, Martin-Delgado MA, Hans JB (2014) Quantum speedup for active learning agents. Phys Rev X 4(3):031002","journal-title":"Phys Rev X"},{"issue":"5","key":"26_CR35","doi-asserted-by":"publisher","first-page":"054435","DOI":"10.1103\/PhysRevB.100.054435","volume":"100","author":"P Patil","year":"2019","unstructured":"Patil P, Kourtis S, Chamon C, Mucciolo ER, Andrei ER (2019) Obstacles to quantum annealing in a planar embedding of xorsat. Phys Rev B 100(5):054435","journal-title":"Phys Rev B"},{"issue":"3","key":"26_CR36","doi-asserted-by":"publisher","first-page":"033123","DOI":"10.1103\/PhysRevResearch.1.033123","volume":"1","author":"SP Pedersen","year":"2019","unstructured":"Pedersen SP, Christensen KS, Nikolaj TZ (2019) Native three-body interaction in superconducting circuits. Phys Rev Res 1(3):033123","journal-title":"Phys Rev Res"},{"key":"26_CR37","doi-asserted-by":"publisher","DOI":"10.1201\/9780429503559","volume-title":"An introduction to quantum field theory","author":"ME Peskin","year":"2018","unstructured":"Peskin ME (2018) An introduction to quantum field theory. CRC Press, Boca Raton"},{"key":"26_CR38","first-page":"71","volume":"17","author":"IG Rosenberg","year":"1975","unstructured":"Rosenberg IG (1975) Reduction of bivalent maximization to the quadratic case. Cahiers du Centre d\u2019etudes de Recherche Operationnelle 17:71\u201374","journal-title":"Cahiers du Centre d\u2019etudes de Recherche Operationnelle"},{"issue":"6419","key":"26_CR39","doi-asserted-by":"publisher","first-page":"1140","DOI":"10.1126\/science.aar6404","volume":"362","author":"D Silver","year":"2018","unstructured":"Silver D, Hubert T, Schrittwieser J, Antonoglou I, Lai M, Guez A, Lanctot M, Sifre L, Kumaran D, Graepel T, et al. (2018) A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science 362(6419):1140\u20131144","journal-title":"Science"},{"key":"26_CR40","unstructured":"Stuart ED (1965) Dynamic programming and the calculus of variations. Technical report, RAND CORP SANTA MONICA CA"},{"key":"26_CR41","volume-title":"Reinforcement learning: an introduction","author":"RS Sutton","year":"2018","unstructured":"Sutton RS, Barto AG (2018) Reinforcement learning: an introduction. MIT Press, Cambridge"},{"issue":"2","key":"26_CR42","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1109\/37.126844","volume":"12","author":"RS Sutton","year":"1992","unstructured":"Sutton RS, Barto AG, Williams RJ (1992) Reinforcement learning is direct adaptive optimal control. IEEE Control Syst Mag 12(2):19\u201322","journal-title":"IEEE Control Syst Mag"},{"key":"26_CR43","unstructured":"D-Wave Systems Inc. (2018) Source code for neal.sampler. https:\/\/docs.ocean.dwavesys.com\/projects\/neal\/en\/latest\/_modules\/neal\/sampler.html#SimulatedAnnealingSampler.sample. Accessed: 2020-03-21"},{"issue":"Nov","key":"26_CR44","first-page":"3137","volume":"11","author":"E Theodorou","year":"2010","unstructured":"Theodorou E, Buchli J, Schaal S (2010) A generalized path integral control approach to reinforcement learning. J Mach Learn Res 11(Nov):3137\u20133181","journal-title":"J Mach Learn Res"},{"issue":"83","key":"26_CR45","first-page":"198","volume":"81","author":"R Yates","year":"2009","unstructured":"Yates R (2009) Fixed-point arithmetic: an introduction. Digital Signal Labs 81(83):198","journal-title":"Digital Signal Labs"},{"issue":"2","key":"26_CR46","doi-asserted-by":"publisher","first-page":"024201","DOI":"10.1103\/PhysRevB.91.024201","volume":"91","author":"I Zintchenko","year":"2015","unstructured":"Zintchenko I, Hastings MB, Troyer M (2015) From local to global ground states in ising spin glasses. Phys Rev B 91(2):024201","journal-title":"Phys Rev B"}],"container-title":["Quantum Machine Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-020-00026-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s42484-020-00026-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-020-00026-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,25]],"date-time":"2022-11-25T20:36:59Z","timestamp":1669408619000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s42484-020-00026-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,30]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["26"],"URL":"https:\/\/doi.org\/10.1007\/s42484-020-00026-6","relation":{},"ISSN":["2524-4906","2524-4914"],"issn-type":[{"type":"print","value":"2524-4906"},{"type":"electronic","value":"2524-4914"}],"subject":[],"published":{"date-parts":[[2020,10,30]]},"assertion":[{"value":"14 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 October 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Conflict of interest"}},{"value":"The views expressed in the article do not necessarily represent the views of the DOE or the U.S. Government. The U.S. Government retains and the publisher, by accepting the article for publication, acknowledges that the U.S. Government retains a nonexclusive, paid-up, irrevocable, worldwide license to publish or reproduce the published form of this work, or allow others to do so, for U.S. Government purposes.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclaimer"}},{"value":"The code that supports the findings of this study are available from the corresponding author upon reasonable request.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}],"article-number":"12"}}