{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,25]],"date-time":"2024-03-25T16:47:53Z","timestamp":1711385273298},"reference-count":68,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Open Syst. Inf. Dyn."],"published-print":{"date-parts":[[2009,3]]},"abstract":"<jats:p>We review the basics of classical algorithmic complexity theory and two of its quantum extensions that have been prompted by the foreseeable existence of quantum computing devices. In particular, we will examine the relations between these extensions and the von Neumann entropy rate of generic quantum information sources of ergodic type.<\/jats:p>","DOI":"10.1142\/s1230161209000025","type":"journal-article","created":{"date-parts":[[2009,3,31]],"date-time":"2009-03-31T03:27:43Z","timestamp":1238470063000},"page":"1-28","source":"Crossref","is-referenced-by-count":4,"title":["Quantum Algorithmic Complexities and Entropy"],"prefix":"10.1142","volume":"16","author":[{"given":"Fabio","family":"Benatti","sequence":"first","affiliation":[{"name":"Dipartimento di Fisica Teorica, Universit\u00e0 di Trieste, 34014 Trieste, Italy"},{"name":"Istituto Nazionale di Fisica Nucleare, Sezione di Trieste, 34014 Trieste, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,1,25]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293639"},{"key":"rf2","series-title":"Springer Tracts in Mod. Phys","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-44678-8_1","volume-title":"Quantum Information: An Introduction to Basic Theoretical Concepts and Experiments","volume":"173","author":"Alber G.","year":"2001"},{"key":"rf3","first-page":"287","volume":"75","author":"Alekseev V. M.","journal-title":"Phys. Rep."},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198504009.001.0001"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-006-0027-z"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1142\/5528"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511535048"},{"key":"rf8","first-page":"22","volume":"241","author":"Bennett C. H.","journal-title":"Sci. Amer."},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02084158"},{"key":"rf10","first-page":"88","volume":"257","author":"Bennett C. H.","journal-title":"Sci. Amer."},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.54.3824"},{"key":"rf13","first-page":"38","volume":"253","author":"Bennett C. H.","journal-title":"Sci. Amer."},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300921"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1765"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-003-0318-3"},{"key":"rf17","volume-title":"Chained Typical Subspaces \u2014 a Quantum Version of Breiman's Theorem","author":"Bjelakovi\u0107 I."},{"key":"rf18","volume-title":"Ergodic Theory and Information","author":"Billingsley P.","year":"1965"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04209-0"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02520-8"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-09089-3"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1002\/3527603093"},{"key":"rf23","first-page":"127","volume":"2","author":"Brudno A. A.","journal-title":"Trans. Moscow Math. Soc."},{"key":"rf24","volume-title":"Lectures on Quantum Information","author":"Bruss D.","year":"2007"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04978-5"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1142\/9781860948169"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321363"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1145\/321892.321894"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1142\/0531"},{"key":"rf30","volume-title":"The Limits of Mathematics","author":"Chaitin G. J.","year":"1998"},{"key":"rf31","volume-title":"Algorithmic Information Theory","author":"Chaitin G. J.","year":"1988"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-6927-5"},{"key":"rf33","doi-asserted-by":"publisher","DOI":"10.1002\/0471200611"},{"key":"rf34","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1098\/rspa.1985.0070","volume":"400","author":"Deutsch D.","journal-title":"Proc. R. Soc. Lond."},{"key":"rf35","volume-title":"A Short Course in Quantum Information Theory: an Approach from Theoretical Physics","author":"Diosi L.","year":"2007"},{"key":"rf36","volume-title":"Feynman Lectures on Computation","author":"Feynman R. P.","year":"1995"},{"key":"rf37","volume":"34","author":"G\u00e1cs P.","journal-title":"J. Phys. A: Math. Gen"},{"key":"rf40","volume-title":"Quantum Computing","author":"Gruska J.","year":"1999"},{"key":"rf41","volume-title":"Feynman and Computation","author":"Hey A. J. P.","year":"1999"},{"key":"rf42","doi-asserted-by":"publisher","DOI":"10.1007\/BF02100287"},{"key":"rf43","doi-asserted-by":"publisher","DOI":"10.1006\/jfan.1994.1125"},{"key":"rf44","doi-asserted-by":"crossref","first-page":"359","DOI":"10.26421\/QIC3.4-5","volume":"3","author":"Kaltchenko A.","journal-title":"Quantum Information and Computation"},{"key":"rf45","volume-title":"An Introduction to Quantum Computing","author":"Kaye P.","year":"2007"},{"key":"rf46","series-title":"Lecture Notes, Universitat Erlangen-Nurnberg","volume-title":"Wahrsheinlichkeittheorie","author":"Keller G.","year":"2003"},{"key":"rf47","first-page":"861","volume":"119","author":"Kolmogorov A. N.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"rf48","first-page":"754","volume":"124","author":"Kolmogorov A. N.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"rf49","first-page":"4","volume":"1","author":"Kolmogorov A. N.","journal-title":"Problems of Information Transmission"},{"key":"rf50","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1968.1054210"},{"key":"rf51","first-page":"183","volume":"3","author":"Landauer R.","journal-title":"IBM J. Research"},{"key":"rf52","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511755361"},{"key":"rf53","doi-asserted-by":"crossref","volume-title":"Algorithmic Complexity of Quantum States","author":"Mora C. E.","DOI":"10.1142\/S0219749906002043"},{"key":"rf54","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.95.200503"},{"key":"rf55","doi-asserted-by":"crossref","volume-title":"Quantum Kolmogorov complexity and its applications","author":"Mora C. E.","DOI":"10.1142\/S0219749907003171"},{"key":"rf56","volume-title":"Strongly Universal Quantum Turing Machines and Invariance of Kol-mogorov Complexity","author":"Miiller M."},{"key":"rf57","volume-title":"Quantum Information and Quantum Computation","author":"Nielsen M. A.","year":"2000"},{"key":"rf58","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-57997-4"},{"key":"rf59","doi-asserted-by":"publisher","DOI":"10.1109\/ITW.2006.1633845"},{"key":"rf60","volume-title":"The Ergodic Theory of Disrcete Sample Paths","author":"Shields P. C.","year":"1996"},{"key":"rf61","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.51.2738"},{"key":"rf62","volume-title":"Entropy, Complexity and Computation","author":"Schumacher B."},{"key":"rf63","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(64)90223-2"},{"key":"rf64","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(64)90131-7"},{"key":"rf65","doi-asserted-by":"publisher","DOI":"10.1070\/RM1990v045n01ABEH002321"},{"key":"rf66","doi-asserted-by":"crossref","first-page":"2464","DOI":"10.1109\/18.945258","volume":"47","author":"Vitanyi P.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"rf67","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"rf68","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-5775-2"},{"key":"rf69","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.50.221"},{"key":"rf70","doi-asserted-by":"crossref","first-page":"807","DOI":"10.1017\/S0143385700007653","volume":"13","author":"White H.","journal-title":"Erg. Th. Dyn. Sys."},{"key":"rf71","doi-asserted-by":"publisher","DOI":"10.1070\/RM1970v025n06ABEH001269"}],"container-title":["Open Systems &amp; Information Dynamics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1230161209000025","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,3]],"date-time":"2021-10-03T19:55:52Z","timestamp":1633290952000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1230161209000025"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3]]},"references-count":68,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2012,1,25]]},"published-print":{"date-parts":[[2009,3]]}},"alternative-id":["10.1142\/S1230161209000025"],"URL":"https:\/\/doi.org\/10.1142\/s1230161209000025","relation":{},"ISSN":["1230-1612","1793-7191"],"issn-type":[{"value":"1230-1612","type":"print"},{"value":"1793-7191","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,3]]}}}