半量子自动机验证器的互动证明系统：PSPACE力量与理论计算模型

本文主要探讨了"具有半量子双向有限自动机建模的验证器的交互式证明系统"这一主题，发表在2015年的《信息与计算》(Information and Computation)第241期，197-214页。该研究论文由Shenggen Zhang、Daowen Qi和Jozef Gruska合作完成，分别来自中山大学计算机科学系、马萨里克大学信息学院以及葡萄牙里斯本理工大学电信学院的SQIG数学系。 交互式证明系统（Interactive Proof System, IPS）是理论计算机科学中的核心概念，它们在计算能力上表现出强大的特性，能够识别PSPACE语言，即那些可以在多项式空间内解决的问题集。这些系统通过验证者与证明者的交互来确定一个陈述的真实性。传统的交互式证明系统中，验证者通常是经典计算机，而本文的研究则引入了半量子的概念，将量子计算元素融入其中。 半量子双向有限自动机（Semi-Quantum Two-Way Finite Automata, SQ2FA）是本文的核心模型。这种自动机同时拥有量子和经典状态，允许在验证过程中利用量子计算的优势，如并行性和量子纠缠，这可能带来新的证明效率和复杂性界限。SQ2FA作为验证器参与交互式证明系统，其功能的增强可以提供对更复杂问题处理的能力，并可能扩展我们对量子计算在证明系统中的潜在应用的理解。 关键词包括量子计算、量子有限自动机、量子Arthur-Merlin证明系统以及具有量子和经典状态的双向有限自动机。研究者们在文章中探索了这种新型模型如何改变交互式证明系统的性能边界，以及它对理论计算机科学基础理论的影响。接收日期为2013年3月13日，全文于2015年2月7日在线发布。 这篇论文深入剖析了半量子双向有限自动机在构建高效、具有强大语言处理能力的交互式证明系统中的作用，展示了量子计算技术在理论和实际应用中的潜在突破，对于理解量子计算如何提升证明系统的效率和可信度具有重要意义。