License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.15
URN: urn:nbn:de:0030-drops-73995
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7399/
Go to the corresponding LIPIcs Volume Portal

Kindler, Guy ; O'Donnell, Ryan

Quantum Automata Cannot Detect Biased Coins, Even in the Limit

pdf-format:
LIPIcs-ICALP-2017-15.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{kindler_et_al:LIPIcs:2017:7399,
  author =	{Guy Kindler and Ryan O'Donnell},
  title =	{{Quantum Automata Cannot Detect Biased Coins, Even in the Limit}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{15:1--15:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7399},
  URN =		{urn:nbn:de:0030-drops-73995},
  doi =		{10.4230/LIPIcs.ICALP.2017.15},
  annote =	{Keywords: quantum automata}
}

Keywords: quantum automata
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI