Efficient protocols for generating bipartite classical distributions and quantum states
Refereed conference paper presented and published in conference proceedings


Full Text

Times Cited

Other information
AbstractWe 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, Massar, Pokutta, Tiwary and de Wolf (Proceedings of the 44th ACM Symposium on Theory of Computing, pages 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 Transactions on Information 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, Schulman, Ta-Shma, Vazirani and Wigderson. Copyright © SIAM.
All Author(s) ListJain R., Shi Y., Wei Z., Zhang S.
Name of Conference24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
Start Date of Conference06/01/2013
End Date of Conference08/01/2013
Place of ConferenceNew Orleans, LA
Country/Region of ConferenceUnited States of America
Detailed descriptionorganized by Sanjeev Khanna,\n\nTo ORKTS: 1. The authors are listed alphabetically according to the convention of the community of theoretical compute
Year2013
Month4
Day16
Pages1503 - 1512
ISBN9781611972511
LanguagesEnglish-United Kingdom

Last updated on 2020-04-09 at 03:19