• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information and computation >Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
【24h】

Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata

机译：具有半量子双向有限自动机建模的验证器的交互式证明系统的功能

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Interactive proof systems (IP) are very powerful - languages they can accept form exactly PSPACE. They represent also one of the very fundamental concepts of theoretical computing and a model of computation by interactions. One of the key players in IP is verifier. In the original model of IP whose power is that of PSPACE, the only restriction on verifiers is that they work in randomized polynomial time. Because of such key importance of IP, it is of large interest to find out how powerful will IP be when verifiers are more restricted. So far this was explored for the case that verifiers are two-way probabilistic finite automata (Dwork and Stockmeyer, 1990) and one-way quantum finite automata as well as two-way quantum finite automata (Nishimura and Yamakami, 2009). IP in which verifiers use public randomization is called Arthur-Merlin proof systems (AM). AM with verifiers modeled by Turing Machines augmented with a fixed-size quantum register (qAM) were studied also by Yakaryilmaz (2012). He proved, for example, that an NP-complete language L_(knapsack), representing the 0-1 knapsack problem, can be recognized by a qAM whose verifier is a two-way finite automaton working on quantum mixed states using superoperators. In this paper we explore the power of AM for the case that verifiers are two-way finite automata with quantum and classical states (2QCFA) - introduced by Ambainis and Watrous in 2002 - and the communications are classical. It is of interest to consider AM with such "semi-quantum" verifiers because they use only limited quantum resources. Our main result is that such Quantum Arthur-Merlin proof systems (QAM(2QCFA)) with polynomial expected running time are more powerful than the models in which the verifiers are two-way probabilistic finite automata (AM(2PFA)) with polynomial expected running time. Moreover, we prove that there is a language which can be recognized by an exponential expected running time QAM(2QCFA), but cannot be recognized by any AM(2PFA), and that the NP-complete language L_(knapsack) can also be recognized by a QAM(2QCFA) working only on quantum pure states using unitary operators.
机译：交互式证明系统（IP）非常强大-它们可以接受的语言恰好是PSPACE。它们还代表了理论计算的非常基本的概念之一，也是通过交互进行计算的模型。验证程序是IP中的关键角色之一。在IP的原始模型中，其功能是PSPACE的功能，对验证者的唯一限制是它们可以在随机多项式时间内工作。由于IP具有如此重要的意义，因此非常有必要了解验证者受到更多限制时IP的功能。到目前为止，已经针对验证者是双向概率有限自动机（Dwork和Stockmeyer，1990）和单向量子有限自动机以及双向量子有限自动机（Nishimura和Yamakami，2009）的情况进行了探索。验证者使用公共随机数的IP被称为Arthur-Merlin证明系统（AM）。 Yakaryilmaz（2012）也研究了带有Turing Machines验证器模型的AM，该验证器由固定大小的量子寄存器（qAM）增强。他证明，例如，表示0-1背包问题的NP完全语言L_（背包）可以被qAM识别，该qAM的验证者是使用超级算子在量子混合态上工作的双向有限自动机。在本文中，我们探讨了验证器是具有量子状态和经典状态的双向有限自动机（2QCFA）（由Ambainis和Watrous于2002年引入）的情况，并且通信是经典的，因此AM具有强大的功能。考虑将AM与此类“半量子”验证器一起使用，是因为它们仅使用有限的量子资源。我们的主要结果是，这种具有多项式期望运行时间的量子Arthur-Merlin证明系统（QAM（2QCFA））比其中检验器是具有多项式期望运行的双向概率有限自动机（AM（2PFA））的模型更强大。时间。此外，我们证明存在一种可以被指数预期运行时间QAM（2QCFA）识别但不能被任何AM（2PFA）识别的语言，并且还可以识别NP完全语言L_（背包）由仅使用using算子在量子纯态上工作的QAM（2QCFA）组成。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号