6533b82ffe1ef96bd1295989

RESEARCH PRODUCT

Debates with Small Transparent Quantum Verifiers

Abuzer YakaryilmazA. C. Cem SayH. Gökalp Demirci

subject

Class (computer programming)Theoretical computer scienceComputer scienceProgramming languageString (computer science)0102 computer and information sciencescomputer.software_genre01 natural sciences010305 fluids & plasmasRegular language010201 computation theory & mathematicsQubit0103 physical sciencesQuantum finite automataQuantumcomputerZero errorQuantum computer

description

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.

yearjournalcountryeditionlanguage
2014-01-01
https://doi.org/10.1007/978-3-319-09698-8_29