On the power of quantum proofs
On the power of quantum proofs
复制标题
DOI：
10.1109/ccc.2004.1313849
复制
发表时间：
2004-06
期刊：
影响因子：
--
通讯作者：
R. Raz;Amir Shpilka
中科院分区：
文献类型：
--
作者：
R. Raz;Amir Shpilka
我们研究了量子计算的两个模型：黑箱模型和通信复杂性模型中量子证明的能力，或者更准确地说，量子Merlin-Arthur(QMA)协议的能力。我们的主要结果是针对通信复杂性模型得到的。对于该模型，我们确定了QMA协议的一个完全承诺问题，即线性子空间距离问题。这个问题是几何性质的：每个玩家得到R/sup m/的一个线性子空间，并考虑该子空间中单位向量的球面。它们的目标是，如果两个球体之间的距离非常小(例如，小于0.1/SPL Midpoint//SPL Radic/2)，则输出1；如果距离非常大(例如，大于0.9/SPL Midpoint//SPL Radic/2)，则输出0。证明了：1.该问题的QMA通信复杂度为O(Logm)。2.该问题的(经典)MA通信复杂性为/SPL Omega/(m/sup/SPL EPSi//)(对于某些/SPL EPSi/>；0)。3.该问题的(标准)量子通信复杂性为/SPL Omega/(/SPL Radic/m)。具体地说，这给出了QMA通信复杂性和MA通信复杂性之间的指数分离。对于黑盒模型，我们给出了几个观察结果。首先，我们观察到块敏感度方法和证明查询数目下界的多项式方法都可以扩展到QMA协议。利用这些方法，我们得到了函数QMA黑盒复杂度的下界。特别地，我们得到了随机函数的QMA黑盒复杂度的/SPL Omega/(N)的紧下界，以及NOR(X/sub1/，…，X/subn/)的QMA黑盒查询复杂度的/SPL Omega/(/SPL Radic/N)的紧下界。特别是，这表明，任何试图给出语言类Co-NP的简短量子证明的尝试都必须超越黑箱论点。我们还观察到，对于任意布尔函数G(X/sub1/，…，X/subn/)，如果对G和7-都有QMA黑盒协议对黑盒进行至多T次查询，则对G存在对黑盒进行0(T/sup 6/)查询的经典确定性黑盒协议。特别地，这表明在黑盒模型QMA/SPL CAP/Co-QMA=P中，我们观察到任何(全部或部分)布尔函数G(X/SUB 1/，…，X/SUB n/)具有长度为N的证明的QMA黑盒协议，该协议仅对黑盒进行0(/SPL Radic/N)查询。最后，我们观察到一个非常简单的证明，证明了QMA黑盒复杂性和(经典)MA黑盒复杂性之间的指数分离(对于Promise问题)。
We study the power of quantum proofs, or more precisely, the power of quantum Merlin-Arthur (QMA) protocols, in two well studied models of quantum computation: the black box model and the communication complexity model. Our main results are obtained for the communication complexity model. For this model, we identify a complete promise problem for QMA protocols, the linear sub-spaces distance problem. The problem is of geometrical nature: each player gets a linear subspace of R/sup m/ and considers the sphere of unit vectors in that subspace. Their goal is to output 1 if the distance between the two spheres is very small (say, smaller than 0.1 /spl middot/ /spl radic/2) and 0 if the distance is very large (say, larger than 0.9 /spl middot/ /spl radic/2). We show that: 1. The QMA communication complexity of the problem is O(logm). 2. The (classical) MA communication complexity of the problem is /spl Omega/(m/sup /spl epsi//) (for some /spl epsi/ > 0). 3. The (standard) quantum communication complexity of the problem is /spl Omega/(/spl radic/m). In particular, this gives an exponential separation between QMA communication complexity and MA communication complexity. For the black box model we give several observations. First, we observe that the block sensitivity method, as well as the polynomial method for proving lower bounds for the number of queries, can both be extended to QMA protocols. We use these methods to obtain lower bounds for the QMA black box complexity of functions. In particular, we obtain a tight lower bound of /spl Omega/(N) for the QMA black box complexity of a random function, and a tight lower bound of /spl Omega/(/spl radic/N) for the QMA black box query complexity of NOR(X/sub 1/,..., X/sub n/). In particular, this shows that any attempt to give short quantum proofs for the class of languages Co - NP have to go beyond black box arguments. We also observe that for any Boolean function G(X/sub 1/,..., X/sub n/), if for both G and 7minus;G there are QMA black box protocols that make at most T queries to the black box, then there is a classical deterministic black box protocol for G that makes 0(T/sup 6/) queries to the black box. In particular, this shows that in the black box model QMA /spl cap/ Co - QMA = P. On the positive side, we observe that any (total or partial) Boolean function G(X/sub 1/,..., X/sub n/) has a QMA black box protocol with proofs of length N that makes only 0(/spl radic/N) queries to the black box. Finally, we observe a very simple proof for the exponential separation (for promise problems) between QMA black box complexity and (classical) MA black box complexity (first obtained by Watrous).