@inproceedings{67507e2a810f4a019bdc459b6dacf37c,
title = "Debates with small transparent quantum verifiers",
abstract = "We study a model where two opposing provers debate over the membership status of a given string in a language, trying to convince a weak verifier whose coins are visible to all. We show that the incorporation of just two qubits to an otherwise classical constant-space verifier raises the class of debatable languages from at most NP to the collection of all Turing-decidable languages (recursive languages). When the verifier is further constrained to make the correct decision with probability 1, the corresponding class goes up from the regular languages up to at least E.",
keywords = "Arthur-Merlin games, debate systems, probabilistic finite automata, quantum computing, quantum finite automata, zero-error",
author = "Abuzer YakaryIlmaz and Say, \{A. C.Cem\} and Demirci, \{H. G{\"o}kalp\}",
year = "2014",
doi = "10.1007/978-3-319-09698-8\_29",
language = "English",
isbn = "9783319096971",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "327--338",
booktitle = "Developments in Language Theory - 18th International Conference, DLT 2014, Proceedings",
address = "Germany",
note = "18th International Conference on Developments in Language Theory, DLT 2014 ; Conference date: 26-08-2014 Through 29-08-2014",
}