Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization
Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization
复制标题
DOI：
10.1145/2432622.2432625
复制
发表时间：
2013-02-01
影响因子：
2.5
通讯作者：
Montanaro, Ashley
中科院分区：
文献类型：
--
作者：
Harrow, Aram W.;Montanaro, Ashley
我们给出一种测试，它能够有效地区分\(n\)个量子系统的乘积态和远离乘积态的态。如果将其应用于与乘积态的最大重叠为\(1 - \epsilon\)的态\(\vert\psi\rangle\)，无论\(n\)或各个系统的局部维度如何，该测试通过的概率为\(1 - \Theta(\epsilon)\)。该测试使用\(\vert\psi\rangle\)的两个副本。我们将此测试的正确性作为关于去极化信道最大输出纯度稳定性的更一般结果的一个特殊情况进行证明。该测试的一个关键应用是在具有多个梅林（Merlins）的量子梅林 - 亚瑟（Merlin - Arthur）游戏中，在其中我们获得了几个先前被推测的结构结果，包括有效可靠性放大是可能的以及两个梅林可以模拟许多梅林这一事实：对于\(k\geq2\)，\(QMA(k)=QMA(2)\)。基于阿隆森（Aaronson）等人先前的一个结果，这意味着给定两个\(\widetilde{O}(\sqrt{n})\)个量子比特的无纠缠证明，存在一种有效的量子算法以恒定可靠性验证3 - SAT问题。我们还展示了具有对数大小证明的\(QMA(2)\)如何等同于大量问题，其中一些与量子信息相关（例如测试混合态的可分性）以及一些与量子力学没有明显联系的问题（例如计算三指标张量的单射张量范数）。因此，我们获得了许多近似难度结果，以及近似\(QMA(2)\)接受概率的方法的潜在算法应用。最后，我们的测试还可用于构建一种有效的测试，以确定一个幺正算符是否为张量积，这是经典线性测试的一种推广。
We give a test that can distinguish efficiently between product states of n quantum systems and states that are far from product. If applied to a state vertical bar psi) whose maximum overlap with a product state is 1 - epsilon, the test passes with probability 1 - Theta(epsilon), regardless of n or the local dimensions of the individual systems. The test uses two copies of |psi). We prove correctness of this test as a special case of a more general result regarding stability of maximum output purity of the depolarizing channel.A key application of the test is to quantum Merlin-Arthur games with multiple Merlins, where we obtain several structural results that had been previously conjectured, including the fact that efficient soundness amplification is possible and that two Merlins can simulate many Merlins: QMA(k) = QMA(2) for k >= 2. Building on a previous result of Aaronson et al., this implies that there is an efficient quantum algorithm to verify 3-SAT with constant soundness, given two unentangled proofs of (O) over tilde(root n) qubits. We also show how QMA(2) with log -sized proofs is equivalent to a large number of problems, some related to quantum information (such as testing separability of mixed states) as well as problems without any apparent connection to quantum mechanics (such as computing injective tensor norms of 3-index tensors). As a consequence, we obtain many hardness-of-approximation results, as well as potential algorithmic applications of methods for approximating QMA(2) acceptance probabilities.Finally, our test can also be used to construct an efficient test for determining whether a unitary operator is a tensor product, which is a generalization of classical linearity testing.