Quantum Information Complexity
Quantum Information Complexity
复制标题
DOI：
10.1145/2746539.2746613
复制
发表时间：
2015-06
期刊：
影响因子：
--
通讯作者：
D. Touchette
中科院分区：
文献类型：
--
作者：
D. Touchette
我们定义了量子协议的信息代价的新概念，以及二分量子任务的量子信息复杂性的概念。这些是二部经典任务的类似量的完全量子推广，这些任务最近得到了许多应用，特别是在证明通信复杂性下界和直和定理方面。找到这样一个信息复杂性的量子概括是Braverman(STOEC‘12)最近提出的公开问题之一。以前已经尝试为量子协议定义这样的量，考虑到特定的应用；我们的概念在许多方面与这些不同。首先，它直接提供了量子通信成本的下限，与底层协议的轮数无关。其次，我们给出了量子信息复杂性的运算解释：我们证明了它恰好等于给定输入的二部任务的摊余量子通信复杂性。这将Braverman和Rao(FOCS‘11)的一个结果推广到量子协议。在证明这一结果的过程中，我们甚至加强了有界圆情形下的经典结果，并证明了量子信息代价和复杂性的重要结构性质。我们证明了利用这个定义可以得到第一个关于有界圆量子通信复杂性的广义直和定理。以前的直接和结果要么适用于某些特定的函数类，要么适用于一般的单轮协议，从而导致量子通信的复杂性。我们还讨论了新量的潜在应用，以获得量子通信复杂性的下界。
We define a new notion of information cost for quantum protocols, and a corresponding notion of quantum information complexity for bipartite quantum tasks. These are the fully quantum generalizations of the analogous quantities for bipartite classical tasks that have found many applications recently, in particular for proving communication complexity lower bounds and direct sum theorems. Finding such a quantum generalization of information complexity was one of the open problems recently raised by Braverman (STOC'12). Previous attempts have been made to define such a quantity for quantum protocols, with particular applications in mind; our notion differs from these in many respects. First, it directly provides a lower bound on the quantum communication cost, independent of the number of rounds of the underlying protocol. Secondly, we provide an operational interpretation for quantum information complexity: we show that it is exactly equal to the amortized quantum communication complexity of a bipartite task on a given input. This generalizes a result of Braverman and Rao (FOCS'11) to quantum protocols. Along the way to prove this result, we even strengthens the classical result in a bounded round scenario, and also prove important structural properties of quantum information cost and complexity. We prove that using this definition leads to the first general direct sum theorem for bounded round quantum communication complexity. Previous direct sum results in quantum communication complexity either held for some particular classes of functions, or were general but only held for single-round protocols. We also discuss potential applications of the new quantities to obtain lower bounds on quantum communication complexity.