An Application of Quantum Finite Automata to Interactive Proof Systems
arXiv:quant-ph/0410040 · doi:10.1016/j.jcss.2008.12.001
Abstract
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.
This is an extended version of the conference paper in the Proceedings of the 9th International Conference on Implementation and Application of Automata, Lecture Notes in Computer Science, Springer-Verlag, Kingston, Canada, July 22-24, 2004
References in corpus (2)
Cited by in corpus (10)
- Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
- One-Way Reversible and Quantum Finite Automata with Advice
- On hybrid models of quantum finite automata
- Interactive Proofs with Quantum Finite Automata
- Quantum finite automata: survey, status and research directions
- Constant-Space Quantum Interactive Proofs Against Multiple Provers
- Turing-equivalent automata using a fixed-size quantum memory
- Constant-Space, Constant-Randomness Verifiers with Arbitrarily Small Error
- A Quantum Finite Automata Approach to Modeling the Chemical Reactions
- Some observations on two-way finite automata with quantum and classical states