Please use this identifier to cite or link to this item: https://doi.org/10.1109/TIT.2013.2258372
Title: Efficient protocols for generating bipartite classical distributions and quantum states
Authors: Jain, R. 
Shi, Y.
Wei, Z. 
Zhang, S.
Keywords: Communication complexity
probability distribution generation
psd-rank
quantum correlation complexity
Issue Date: 2013
Citation: Jain, R., Shi, Y., Wei, Z., Zhang, S. (2013). Efficient protocols for generating bipartite classical distributions and quantum states. IEEE Transactions on Information Theory 59 (8) : 5171-5178. ScholarBank@NUS Repository. https://doi.org/10.1109/TIT.2013.2258372
Abstract: 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 of 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 et al. (SIAM J. Comput., 32 (6):1570-1585, 2003). © 2013 IEEE.
Source Title: IEEE Transactions on Information Theory
URI: http://scholarbank.nus.edu.sg/handle/10635/77850
ISSN: 00189448
DOI: 10.1109/TIT.2013.2258372
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

14
checked on Dec 12, 2018

WEB OF SCIENCETM
Citations

16
checked on Dec 12, 2018

Page view(s)

56
checked on Nov 24, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.