Paper Info
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. We also show that the quantum model outperforms its classical counterpart when restricted to run in polynomial time, and demonstrate some non-context-free languages which have such short debates with quantum verifiers.
Year
DOI
Venue
2014
10.1142/S0129054116400104
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Keywords
DocType
Volume
Quantum finite automata, quantum computing, probabilistic finite automata, Arthur-Merlin games, debate systems, zero-error
Journal
27
Issue
ISSN
Citations 
2
0129-0541
0
PageRank 
References 
Authors
0.34
8
3
Name
Order
Citations
PageRank
Abuzer Yakaryilmaz116825.31
A. C. Cem Say219326.13
H. Gökalp Demirci383.31