Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
复制标题
生成二分经典分布和量子态的有效协议
DOI：
10.1137/1.9781611973105.108
复制
发表时间：
2013
影响因子：
2.5
通讯作者：
Shengyu Zhang
中科院分区：
文献类型：
--
作者：
Rahul Jain;Yaoyun Shi;Zhaohui Wei;Shengyu Zhang
我们研究生成二分经典分布或量子态的基本问题。通过设计高效的通信协议并证明其最优性，我们在优化、凸几何和信息论的基本度量之间建立了许多有趣的联系。
1) 为了生成一个经典分布\(P(x,y)\)，我们通过\(P\)的半正定秩（作为一个矩阵）紧密刻画了所需的最小量子通信量，半正定秩是菲奥里尼等人（《第44届美国计算机协会计算理论研讨会论文集》，第95 - 106页，2012年）在研究诸如旅行商问题等优化问题的扩展公式最小规模时最近提出的一种度量。这与之前通过\(P\)的非负秩对最优经典通信成本的刻画相呼应。该结果是通过研究更一般的二分量子态生成情况并为其设计一个最优协议而获得的。
2) 当允许一个近似误差\(\epsilon\)来生成一个分布\((X,Y)\sim P\)时，我们提出一个通信成本为\(O((C(X,Y)+1)/\epsilon)\)的经典协议，其中\(C(X,Y)\)是公共信息，这是怀纳（《IEEE信息论汇刊》，21(2):163 - 179，1975年）在信息论中引入的一种经过充分研究的度量。这也将非负秩和公共信息这两个不同领域中看似不相关的量联系起来。
3) 对于近似生成一个量子纯态\(\vert\psi\rangle\)，我们通过一个相应的近似秩完全刻画了最小成本，填补了安巴尼斯等人（《美国工业与应用数学学会计算杂志》，32(6):1570 - 1585，2003年）中可能存在的指数级差距。
We investigate the fundamental problem of generating bipartite classical distributions or quantum states. By designing efficient communication protocols and proving their optimality, we establish a number of intriguing connections to fundamental measures in optimization, convex geometry, and information theory. 1) To generate a classical distribution P(x,y), we tightly characterize the minimum amount of quantum communication needed by the psd-rank of P (as a matrix), a measure recently proposed by Fiorini et al. (Proc. 44th ACM Symp. Theory Comput., pp. 95-106, 2012) in studies of the minimum size of extended formulations of optimization problems such as TSP. This echos the previous characterization for the optimal classical communication cost by the nonnegative rank of P. The result is obtained via investigating the more general case of bipartite quantum state generation and designing an optimal protocol for it. 2) When an approximation ϵ is allowed to generate a distribution (X,Y)~P, we present a classical protocol of the communication cost O((C(X,Y)+1)/ϵ, where C(X,Y) is common information, a well-studied measure in information theory introduced by Wyner (IEEE Trans. Inf. Theory, 21 (2):163-179, 1975). This also links nonnegative rank and common information, two seemingly unrelated quantities in different fields. 3) For approximately generating a quantum pure state |ψ〉, we completely characterize the minimum cost by a corresponding approximate rank, closing a possibly exponential gap left in Ambainis etal. (SIAM J. Comput., 32 (6):1570-1585, 2003).