The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
复制标题
DOI：
10.1145/3564246.3585248
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
F. G. Jeronimo;Pei Wu
中科院分区：
文献类型：
--
作者：
F. G. Jeronimo;Pei Wu
量子纠缠是量子力学的基本性质，是量子计算和信息的基本资源。尽管量子纠缠很重要，但它的威力和局限性还远未得到充分理解。在这里，我们通过计算复杂性的角度研究纠缠。这是通过研究具有多个非纠缠量子证明的 NP 类的量子推广，即所谓的 QMA(2) 及其变体来完成的。众所周知，QMA(2) 的复杂性与各种问题密切相关，例如确定状态是否纠缠以及几个经典优化问题。然而，确定 QMA(2) 的复杂度是一个长期存在的开放性问题，并且仅知道平凡的复杂度界限 ⊆ (2) ⊆ 。在这项工作中，我们研究了具有非负振幅的非纠缠量子证明的威力，我们将这一类表示为 QMA+(2)。在这种情况下，我们能够为（越来越）困难的问题设计证明验证协议，既使用对数大小的量子证明，又在区分“是”和“否”实例时具有恒定的概率差距。特别是，我们为小集扩展（SSE）、独特游戏（UG）和PCP验证设计了全局协议。结果，我们得到 NP ⊆ QMAlog+(2) 且间隙恒定。凭借新的常数间隙，我们能够将此结果“放大”到 QMA+(2)，通过建立 for 的更强的显式属性来获得完整的表征 QMA+(2)=NEXP 。我们相信我们的协议本身就是证明验证和属性测试的有趣示例。此外，我们的每个协议都有一个依赖于非负振幅的独立属性测试任务，如果将其推广，将允许将我们的结果转移到 QMA(2)。这些协议的一个关键新颖之处是以全局一致的方式操纵量子证明，产生恒定的间隙。以前的协议（仅适用于一般振幅）要么是局部的，具有极小的间隙，要么将量子证明视为需要多项式证明的经典概率分布。在这两种情况下，这些已知协议并不意味着 QMA(2) 上的非平凡界限。
Quantum entanglement is a fundamental property of quantum mechanics and it serves as a basic resource in quantum computation and information. Despite its importance, the power and limitations of quantum entanglement are far from being fully understood. Here, we study entanglement via the lens of computational complexity. This is done by studying quantum generalizations of the class NP with multiple unentangled quantum proofs, the so-called QMA(2) and its variants. The complexity of QMA(2) is known to be closely connected to a variety of problems such as deciding if a state is entangled and several classical optimization problems. However, determining the complexity of QMA(2) is a longstanding open problem, and only the trivial complexity bounds ⊆ (2) ⊆ are known. In this work, we study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote QMA+(2). In this setting, we are able to design proof verification protocols for (increasingly) hard problems both using logarithmic size quantum proofs and having a constant probability gap in distinguishing yes from no instances. In particular, we design global protocols for small set expansion (SSE), unique games (UG), and PCP verification. As a consequence, we obtain NP ⊆ QMAlog+(2) with a constant gap. By virtue of the new constant gap, we are able to “scale up” this result to QMA+(2), obtaining the full characterization QMA+(2)=NEXP by establishing stronger explicitness properties of the for . We believe that our protocols are interesting examples of proof verification and property testing in their own right. Moreover, each of our protocols has a single isolated property testing task relying on non-negative amplitudes which if generalized would allow transferring our results to QMA(2). One key novelty of these protocols is the manipulation of quantum proofs in a global and coherent way yielding constant gaps. Previous protocols (only available for general amplitudes) are either local having vanishingly small gaps or treating the quantum proofs as classical probability distributions requiring polynomially many proofs. In both cases, these known protocols do not imply non-trivial bounds on QMA(2).