LIPIcs.ICALP.2017.15.pdf
- Filesize: 459 kB
- 8 pages
Document
Quantum Automata Cannot Detect Biased Coins, Even in the Limit
Authors
-
Part of:
Volume:
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-07-07
Cite As Get BibTex
Guy Kindler and Ryan O'Donnell. Quantum Automata Cannot Detect Biased Coins, Even in the Limit. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 15:1-15:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICALP.2017.15
Abstract
Aaronson and Drucker (2011) asked whether there exists a quantum finite automaton that can distinguish fair coin tosses from biased ones by spending significantly more time in accepting states, on average, given an infinite sequence of tosses. We answer this question negatively.
Subject Classification
Keywords
- quantum automata
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Scott Aaronson. The NEW ten most annoying questions in quantum computing, May 2014. URL: http://www.scottaaronson.com/blog/?p=1792.
-
Scott Aaronson and Andrew Drucker. Advice coins for classical and quantum computation. In Proceedings of the 38th Annual International Colloquium on Automata, Languages and Programming, pages 61-72, 2011.
-
Bernhard Baumgartner and Heide Narnhofer. The structures of state space concerning quantum dynamical semigroups. Reviews in Mathematical Physics, 24(2):1250001, 2012.
-
Raffaella Carbone and Yan Pautrat. Irreducible decompositions and stationary states of quantum channels. Technical Report 1507.08404, arXiv, 2015.
-
Martin Hellman and Thomas Cover. Learning with finite memory. Annals of Mathematical Statistics, 41:765-782, 1970.
- user1551. Continuity of the basis of the null space, March 2015. URL: http://math.stackexchange.com/a/1203782.
- Michael Wolf. Quantum channels &operations: guided tour, 2012. URL: http://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/MichaelWolf/QChannelLecture.pdf.