Debates with Small Transparent Quantum Verifiers

Autor:	Abuzer Yakaryilmaz, A. C. Cem Say, H. Gökalp Demirci
Rok vydání:	2016
Předmět:	010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Computer Science (miscellaneous) 020201 artificial intelligence & image processing 0102 computer and information sciences 02 engineering and technology 01 natural sciences
Zdroj:	International Journal of Foundations of Computer Science. 27:283-300
ISSN:	1793-6373 0129-0541
DOI:	10.1142/s0129054116400104
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::05d187bc1fde6c8fff814122f812a624 https://doi.org/10.1142/s0129054116400104 Zobrazit plný text záznamu