Physics – Quantum Physics
Scientific paper
2004-10-05
(journal version) Journal of Computer and System Sciences, Vol.75, pp.255-269, 2009
Physics
Quantum Physics
This is an extended version of the conference paper in the Proceedings of the 9th International Conference on Implementation a
Scientific paper
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.
Nishimura Harumichi
Yamakami Tomoyuki
No associations
LandOfFree
An Application of Quantum Finite Automata to Interactive Proof Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Application of Quantum Finite Automata to Interactive Proof Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Application of Quantum Finite Automata to Interactive Proof Systems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-103091