Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR04-110 | 24th November 2004 00:00

An Application of Quantum Finite Automata to Interactive Proof Systems



Quantum finite automata have been studied intensively since
their introduction in late 1990s as a natural model of a
quantum computer with finite-dimensional quantum memory space.
This paper seeks their direct application
to interactive proof systems in which a mighty quantum prover
communicates with a quantum-automaton verifier
through a common communication cell. Our quantum interactive
proof systems are juxtaposed to Dwork-Stockmeyer's classical
interactive proof systems whose verifiers are two-way
probabilistic automata. We demonstrate strengths and weaknesses
of our systems and further study how various restrictions
on the behaviors of quantum-automaton verifiers affect the power
of quantum interactive proof systems.

ISSN 1433-8092 | Imprint