量子科技中心_量科网

这篇对话论文对即将开展的“基础交互式算法公理化”研究进行了前瞻与展望。现代算法概念在20世纪30至50年代得以明确，并于二十五年前被公理化为“顺序算法”或“经典算法”——该研究团队更倾向于称其为“基础算法”。这一公理化体系被用于证明：每个基础算法都存在行为等价的抽象状态机，同时还为逻辑学界所理解的丘奇-图灵论题提供了证明。自20世纪60年代以来，算法概念不断扩展——概率算法、量子算法等新兴范式推动了更具野心的“物理版丘奇-图灵论题”的提出。该工作着重辨析了这两版丘奇-图灵论题的本质差异，并论证了非确定性与概率算法如何被视为配备特定谕示器的基础算法。这一视角同样适用于量子电路算法及众多其他算法类别。