An Application of Quantum Finite Automata to Interactive Proof Systems
<|reference_start|>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.<|reference_end|>
@article{nishimura2004an,
    title={An Application of Quantum Finite Automata to Interactive Proof Systems},
    author={Harumichi Nishimura and Tomoyuki Yamakami},
    journal={Journal of Computer and System Sciences, Vol.75, pp.255-269, 2009},
    year={2004},
    doi={10.1016/j.jcss.2008.12.001},
    archivePrefix={arXiv},
    eprint={quant-ph/0410040},
    primaryClass={quant-ph cs.CC}
}