一种多时间复杂度的量子编程语言

《ACM Transactions on Quantum Computing》：A Polytime Quantum Programming Language

量子编程语言foq及其子集pfoq的研究，通过限制递归深度和分支宽度，实现量子多项式时间计算的可编译表示，并提出基于ancoring-and-merging技术的编译算法，为量子复杂类fbqp提供编程语言层面的形式化刻画。

　　

摘要

随着量子计算作为一种有前景的计算范式逐渐兴起，量子编程语言为抽象编程与其硬件实现之间的衔接提供了工具。在某些情况下，受限的编程语言甚至可以为更高效的电路编译策略提供途径。

在这项工作中，我们介绍了foq，这是一种支持量子控制和递归的一阶量子编程语言。我们证明了其语法受限的子集pfoq在量子多项式时间计算中是完备且正确的。这是通过限制程序的递归深度和分支宽度来实现的，同时我们展示了这种语言仍然适用于各种有趣的应用场景，例如量子隐形传态和量子傅里叶变换。

pfoq是首个基于编程语言对量子复杂度类fbqp进行描述的工具，我们提供了一种保持语义的编译算法，使得任何pfoq程序都可以被编译成输入量子比特数量呈多项式增长的量子电路，并利用“锚定与合并”（anchoring-and-merging）技术来解决分支序列化问题。