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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adleman, L.M., DeMarrais, J., Huang, M.D.A.: Quantum computability. SIAM Journal on Computing 26(5), 1524–1540 (1997)
Ambainis, A., Watrous, J.: Two–way finite automata with quantum and classical states. Theoretical Computer Science 287(1), 299–311 (2002)
Babai, L.: Trading group theory for randomness. In: STOC 1985, pp. 421–429 (1985)
Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. Journal of the ACM 28(1), 114–133 (1981)
Condon, A.: Computational Models of Games. MIT Press (1989)
Condon, A., Feigenbaum, J., Lund, C., Shor, P.: Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions (extended abstract). In: STOC 1993, pp. 305–314. ACM (1993)
Condon, A., Ladner, R.E.: Probabilistic game automata. Journal of Computer and System Sciences 36(3), 452–489 (1988)
Condon, A., Lipton, R.J.: On the complexity of space bounded interactive proofs (extended abstract). In: FOCS 1989, pp. 462–467 (1989)
Demirci, H.G., Say, A.C.C., Yakaryılmaz, A.: The complexity of debate checking. Theory of Computing Systems (2014), doi:10.1007/s00224-014-9547-7
Dwork, C., Stockmeyer, L.: Finite state verifiers I: The power of interaction. Journal of the ACM 39(4), 800–828 (1992)
Feige, U., Kilian, J.: Making games short (extended abstract). In: STOC 1997, pp. 506–516. ACM (1997)
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM Journal on Computing 18(1), 186–208 (1989)
Gutoski, G., Watrous, J.: Toward a general theory of quantum games. In: STOC 2007, pp. 565–574 (2007)
Kitaev, A.Y., Shen, A., Vyalyi, M.N.: Classical and Quantum Computation. American Mathematical Society (2002)
Ladner, R.E., Lipton, R.J., Stockmeyer, L.J.: Alternating pushdown automata. In: FOCS 1978, pp. 92–106 (1978)
Rabin, M.O.: Probabilistic automata. Information and Control 6, 230–243 (1963)
Yakaryılmaz, A.: Public-qubits versus private-coins. Tech. rep. (2012), ECCC:TR12-130
Yakaryılmaz, A.: Quantum alternation. In: Bulatov, A.A., Shur, A.M. (eds.) CSR 2013. LNCS, vol. 7913, pp. 334–346. Springer, Heidelberg (2013)
Yakaryılmaz, A., Say, A.C.C.: Succinctness of two-way probabilistic and quantum finite automata. Discrete Mathematics and Theoretical Computer Science 12(2), 19–40 (2010)
Yakaryılmaz, A., Say, A.C.C.: Unbounded-error quantum computation with small space bounds. Information and Computation 279(6), 873–892 (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Yakaryılmaz, A., Say, A.C.C., Demirci, H.G. (2014). Debates with Small Transparent Quantum Verifiers. In: Shur, A.M., Volkov, M.V. (eds) Developments in Language Theory. DLT 2014. Lecture Notes in Computer Science, vol 8633. Springer, Cham. https://doi.org/10.1007/978-3-319-09698-8_29
Download citation
DOI: https://doi.org/10.1007/978-3-319-09698-8_29
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09697-1
Online ISBN: 978-3-319-09698-8
eBook Packages: Computer ScienceComputer Science (R0)