Multipartite quantum correlation and communication complexities

DOI10.1007/S00037-016-0126-YzbMATH Open1371.68089arXiv1405.6015OpenAlexW1696453256MaRDI QIDQ2012182FDOQ2012182

Penghui Yao, Zhaohui Wei, Rahul Jain, Shengyu Zhang

Publication date: 28 July 2017

Published in: Computational Complexity (Search for Journal in Brave)

Abstract: The concepts of quantum correlation complexity and quantum communication complexity were recently proposed to quantify the minimum amount of resources needed in generating bipartite classical or quantum states in the single-shot setting. The former is the minimum size of the initially shared state $sigma$ on which local operations by the two parties (without communication) can generate the target state $ho$, and the latter is the minimum amount of communication needed when initially sharing nothing. In this paper, we generalize these two concepts to multipartite cases, for both exact and approximate state generation. Our results are summarized as follows. (1) For multipartite pure states, the correlation complexity can be completely characterized by local ranks of sybsystems. (2) We extend the notion of PSD-rank of matrices to that of tensors, and use it to bound the quantum correlation complexity for generating multipartite classical distributions. (3) For generating multipartite mixed quantum states, communication complexity is not always equal to correlation complexity (as opposed to bipartite case). But they differ by at most a factor of 2. Generating a multipartite mixed quantum state has the same communication complexity as generating its optimal purification. But for correlation complexity of these two tasks can be different (though still related by less than a factor of 2). (4) To generate a bipartite classical distribution $P(x,y)$ approximately, the quantum communication complexity is completely characterized by the approximate PSD-rank of $P$. The quantum correlation complexity of approximately generating multipartite pure states is bounded by approximate local ranks.

Full work available at URL: https://arxiv.org/abs/1405.6015

zbMATH Keywords

quantum communication complexitymultipartite systemPSD-rankquantum correlation complexity

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Expressing combinatorial optimization problems by linear programs
• Quantum Computation and Quantum Information
• Exponential lower bounds for polytopes in combinatorial optimization
• Quantum strategic game theory
• The Communication Complexity of Correlation
• Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
• The Quantum Communication Complexity of Sampling

Cited In (10)

• QUANTUM COMMUNICATION COMPLEXITY PROTOCOLS BASED ON HIGHER-DIMENSIONAL ENTANGLED SYSTEMS
• Entanglement, CP-maps and quantum communications
• Experimental multipartner quantum communication complexity employing just one qubit
• Quantum Multiparty Communication Complexity and Circuit Lower Bounds
• Algorithms and Computation
• Quantum Correlations in Multipartite Quantum Systems
• Mixed states in one spatial dimension: Decompositions and correspondence with nonnegative matrices
• Multi-party Quantum Communication Complexity with Routed Messages
• Partial correlations in multipartite quantum systems
• Binding complexity and multiparty entanglement

This page was built for publication: Multipartite quantum correlation and communication complexities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2012182)