{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T10:44:11Z","timestamp":1648809851149},"reference-count":9,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p> Deutsch's problem is the simplest and most frequently examined example of computational problem used to demonstrate the superiority of quantum computing over classical computing. Deutsch's quantum algorithm has been claimed to be faster than any classical ones solving the same problem, only to be discovered later that this was not the case. Various de-quantised solutions for Deutsch's quantum algorithm\u2014classical solutions which are as efficient as the quantum one\u2014have been proposed in the literature. These solutions are based on the possibility of classically simulating \"superpositions\", a key ingredient of quantum algorithms, in particular, Deutsch's algorithm. The de-quantisation proposed in this note is based on a classical simulation of the quantum measurement achieved with a model of observed system. As in some previous de-quantisations of Deutsch's quantum algorithm, the resulting de-quantised algorithm is deterministic. Finally, we classify observers (as finite state automata) that can solve the problem in terms of their \"observational power\". <\/jats:p>","DOI":"10.1142\/s0129054111007940","type":"journal-article","created":{"date-parts":[[2011,1,21]],"date-time":"2011-01-21T10:43:19Z","timestamp":1295606599000},"page":"191-201","source":"Crossref","is-referenced-by-count":0,"title":["AN OBSERVER-BASED DE-QUANTISATION OF DEUTSCH'S ALGORITHM"],"prefix":"10.1142","volume":"22","author":[{"given":"CRISTIAN S.","family":"CALUDE","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Auckland, New Zealand"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MATTEO","family":"CAVALIERE","sequence":"additional","affiliation":[{"name":"CNB - CSIC, Madrid, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"RADU","family":"MARDARE","sequence":"additional","affiliation":[{"name":"Microsoft Research-University of Trento, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/s12043-001-0130-9"},{"key":"rf4","first-page":"1","volume":"5","author":"Calude C. S.","journal-title":"International Journal of Quantum Information"},{"key":"rf5","volume-title":"Computing with Cells and Atoms","author":"Calude C. S.","year":"2001"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.4249\/scholarpedia.9335"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.03.036"},{"key":"rf13","doi-asserted-by":"crossref","first-page":"1769","DOI":"10.1098\/rsta.1998.0248","volume":"356","author":"Ekert A.","journal-title":"Philosophical Transactions of the Royal Society A"},{"key":"rf14","volume-title":"Quantum Computing","author":"Gruska J.","year":"1999"},{"key":"rf16","volume-title":"Quantum Computation and Quantum Information","author":"Nielsen M. A.","year":"2001"},{"key":"rf17","volume-title":"Formal Languages","author":"Salomaa A.","year":"1987"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054111007940","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:54:17Z","timestamp":1565139257000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054111007940"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":9,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1142\/S0129054111007940"],"URL":"https:\/\/doi.org\/10.1142\/s0129054111007940","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}