An application of quantum finite automata to interactive proof systems
An application of quantum finite automata to interactive proof systems
复制标题
DOI：
10.1016/j.jcss.2008.12.001
复制
发表时间：
2004-07
期刊：
影响因子：
--
通讯作者：
H. Nishimura;T. Yamakami
中科院分区：
文献类型：
--
作者：
H. Nishimura;T. Yamakami
量子有限自动机作为量子计算机在有限维量子存储空间中工作的自然模型，自20世纪90年代末引入以来，一直受到人们的广泛研究。本文寻求他们的直接应用交互式证明系统中，一个强大的量子证明器与量子自动机验证器通过一个共同的通信单元进行通信。我们的量子交互式证明系统并列Dwork-Stockmeyer的经典交互式证明系统，其验证者是双向概率有限自动机。我们通过研究量子自动机验证器的行为上的各种限制如何影响量子交互证明系统的能力来展示我们的系统的优点和缺点。
Quantum finite automata have been studied intensively since their introduction in late 1990s as a natural model of a quantum computer working 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 finite automata. We demonstrate strengths and weaknesses of our systems by studying how various restrictions on the behaviors of quantum-automaton verifiers affect the power of quantum interactive proof systems.