机构名称：
¥ 2.0
我们引入纠缠量子多项式层次 QEPH ，作为一类可通过相互纠缠的交替量子证明进行有效验证的问题。我们证明 QEPH 会坍缩至第二层。事实上，我们表明多项式数量的交替会坍缩为仅仅两个。因此，QEPH = QRG ( 1 ) ，即具有一轮量子裁判游戏的问题类，已知包含在 PSPACE 中。这与包含 QMA (2) 的非纠缠量子多项式层次 QPH 形成对比。我们还引入了 DistributionQCPH ，它是量子经典多项式层次 QCPH 的泛化，其中证明者发送字符串（而不是字符串）上的概率分布。我们证明 DistributionQCPH = QCPH ，表明只有量子叠加（而非经典概率）才能增加这些层次结构的计算能力。为了证明这一等式，我们推广了 Lipton 和 Young (1994) 的一个博弈论结果，该结果指出，在不失一般性的情况下，证明者可以在多项式大小的支持上发送均匀分布。我们还证明了多项式层次的类似结果，即 DistributionPH = PH 。最后，我们证明 PH 和 QCPH 包含在 QPH 中，解决了 Gharibian 等人 (2022) 的一个未决问题。
纠缠量子多项式层级崩塌
主要关键词
相关文件推荐
