标题： 量子计算中的相关测量：对复杂性景观的影响 显示英文标题

标题： Quantum Computation with Correlated Measurements: Implications for the Complexity Landscape

摘要： 2004年，Aaronson引入了复杂度类$\mathsf{PostBQP}$（$\mathsf{BQP}$带有后选择）并证明它等于$\mathsf{PP}$。 在本文中，我们定义了一个新的复杂度类，$\mathsf{CorrBQP}$，它是$\mathsf{BQP}$的一种修改，具有执行相关测量的能力，即在寄存器的划分上输出相同值的测量。 我们证明$\mathsf{CorrBQP}$完全等于$\mathsf{BPP}^{\mathsf{PP}}$，使其“略高于”$\mathsf{PP}$。 事实上，我们证明了其他形而上学的修改，如$\mathsf{BQP}$，例如$\mathsf{CBQP}$（即具有克隆任意量子态能力的$\mathsf{BQP}$），也等于$\mathsf{BPP}^{\mathsf{PP}}$。 此外，我们证明了 $\mathsf{CorrBQP}$对经典查询是自低的。 相比之下，如果它在量子查询下是自低的，计数层次结构 ($\mathsf{CH}$) 将会坍缩到 $\mathsf{BPP}^{\mathsf{PP}}$。 最后，我们引入了一个有理次数的变体，该变体下界给出了 $\mathsf{BPP}^{\mathsf{PP}}$的查询复杂度。 显示英文摘要

摘要： In 2004, Aaronson introduced the complexity class $\mathsf{PostBQP}$ ($\mathsf{BQP}$ with postselection) and showed that it is equal to $\mathsf{PP}$. In this paper, we define a new complexity class, $\mathsf{CorrBQP}$, a modification of $\mathsf{BQP}$ which has the power to perform correlated measurements, i.e. measurements that output the same value across a partition of registers. We show that $\mathsf{CorrBQP}$ is exactly equal to $\mathsf{BPP}^{\mathsf{PP}}$, placing it "just above" $\mathsf{PP}$. In fact, we show that other metaphysical modifications of $\mathsf{BQP}$, such as $\mathsf{CBQP}$ (i.e. $\mathsf{BQP}$ with the ability to clone arbitrary quantum states), are also equal to $\mathsf{BPP}^{\mathsf{PP}}$. Furthermore, we show that $\mathsf{CorrBQP}$ is self-low with respect to classical queries. In contrast, if it were self-low under quantum queries, the counting hierarchy ($\mathsf{CH}$) would collapse to $\mathsf{BPP}^{\mathsf{PP}}$. Finally, we introduce a variant of rational degree that lower-bounds the query complexity of $\mathsf{BPP}^{\mathsf{PP}}$.