pfoq

一种表征量子多项式时间的编程语言

– 我们引入了一种量子编程语言，名为 foq ，其中包含一阶递归程序。foq 程序的输入包括一组排序的量子比特，即一列成对不同的量子比特索引。foq 程序可以将对应于一元酉算子的基本算子应用于其每个量子比特。所考虑的算子集已根据 [17] 进行选择，以形成一组通用门。 – 在证明终止 foq 程序是可逆的（定理 1）之后，我们将程序限制为一个严格子集，名为 pfoq ，多项式时间为 foq 。对 pfoq 程序的限制是可处理的（即可以在多项式时间内确定，参见定理 2），确保程序在任何输入时终止（引理 1），并防止程序出现任何指数爆炸（引理 2）。 – 我们证明，对于量子复杂度类 fbqp 而言，pfoq 程序计算的函数类是健全且完备的。fbqp 是有界误差量子多项式时间的函数扩展，称为 bqp [ 3 ]，这是一类决策问题，量子计算机可以在多项式时间内解决，错误概率最多为 1