论文标题
对称性在量子查询到通信模拟中的作用
The Role of Symmetry in Quantum Query-to-Communication Simulation
论文作者
论文摘要
Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function f : {-1,1}^n to {-1,1} and G in {AND_2, XOR_2}, the bounded-error quantum communication complexity of the composed function f o G equals O(Q(f) log n), where Q(f) denotes the bounded-error quantum query complexity of f.这是通过使用一轮O（log n）通信来实现每个查询的Alice来实现F的最佳量子查询算法。 这与经典环境形成鲜明对比的是，很容易证明r^{cc}（f o g）最多是2r（f），其中r^{cc}分别表示有界的 - 错误通信和查询复杂性。我们表明，量子设置中某些功能需要O（log n）开销，因此BCW模拟很紧。我们在这里注意到，在工作之前，尚未排除Q^{cc}（f o g）= o（q（f）），对于所有f，in {and_2，xor_2}中的所有g都没有被排除在外。更具体地说，我们显示以下内容。 - 我们表明，当f是对称的时，log n开销不是 *不需要 *，这是对设定偶数函数的Aaronson和Ambainis的概括（计算理论05）。 - 为了证明上述内容，我们设计了一个有效的嘈杂振幅扩增的分布式版本，该版本使我们能够在f为或函数时证明结果。 - 鉴于我们上面的第一个结果，也可能会询问即使F传递时，也可以避免BCW模拟中的log N开销，这是对称性的较弱的概念。我们通过证明一些传递函数仍然需要表明量子通信协议的误差概率即可任意接近1/2的错误概率，从而给出了强烈的负面答案。 - 除其他外，我们还提供了构造功能的一般配方，在界限通信模型中，BCW模拟中需要对数n开销。
Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function f : {-1,1}^n to {-1,1} and G in {AND_2, XOR_2}, the bounded-error quantum communication complexity of the composed function f o G equals O(Q(f) log n), where Q(f) denotes the bounded-error quantum query complexity of f. This is achieved by Alice running the optimal quantum query algorithm for f, using a round of O(log n) qubits of communication to implement each query. This is in contrast with the classical setting, where it is easy to show that R^{cc}(f o G) is at most 2R(f), where R^{cc} and R denote bounded-error communication and query complexity, respectively. We show that the O(log n) overhead is required for some functions in the quantum setting, and thus the BCW simulation is tight. We note here that prior to our work, the possibility of Q^{cc}(f o G) = O(Q(f)), for all f and all G in {AND_2, XOR_2}, had not been ruled out. More specifically, we show the following. - We show that the log n overhead is *not* required when f is symmetric, generalizing a result of Aaronson and Ambainis for the Set-Disjointness function (Theory of Computing'05). - In order to prove the above, we design an efficient distributed version of noisy amplitude amplification that allows us to prove the result when f is the OR function. - In view of our first result above, one may ask whether the log n overhead in the BCW simulation can be avoided even when f is transitive, which is a weaker notion of symmetry. We give a strong negative answer by showing that the log n overhead is still necessary for some transitive functions even when we allow the quantum communication protocol an error probability that can be arbitrarily close to 1/2. - We also give, among other things, a general recipe to construct functions for which the log n overhead is required in the BCW simulation in the bounded-error communication model.
