Multipartite quantum correlation and communication complexities

DOI10.1007/S00037-016-0126-YMaRDI QIDQ2012182zbMATH OpenOpenAlexFDO

Authors Rahul Jain, Penghui Yao, Shengyu Zhang, Zhaohui Wei

Publication date 28 July 2017

Published in Computational Complexity (Search for Journal in Brave)

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)

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.

Recommendations

• Efficient protocols for generating bipartite classical distributions and quantum states
• Tensor Norms and the Classical Communication Complexity of Nonlocal Quantum Measurement
• Simulating quantum correlations with finite communication
• Communication complexity reduction from globally uncorrelated states
• Quantum entanglement and communication complexity

Cites work

• scientific article; zbMATH DE number 1263236 (Why is no real title available?)
• scientific article; zbMATH DE number 4197419 (Why is no real title available?)
• Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
• Exponential lower bounds for polytopes in combinatorial optimization
• Expressing combinatorial optimization problems by linear programs
• Quantum computation and quantum information. 10th anniversary edition
• Quantum strategic game theory
• The Communication Complexity of Correlation
• The Quantum Communication Complexity of Sampling

Cited in

(12)

• QUANTUM COMMUNICATION COMPLEXITY PROTOCOLS BASED ON HIGHER-DIMENSIONAL ENTANGLED SYSTEMS
• Experimental multipartner quantum communication complexity employing just one qubit
• Entanglement, CP-maps and quantum communications
• Quantum Multiparty Communication Complexity and Circuit Lower Bounds
• Mixed states in one spatial dimension: decompositions and correspondence with nonnegative matrices
• Algorithms and Computation
• Bipartite matrix-valued tensor product correlations that are not finitely representable
• Quantum Correlations in Multipartite Quantum Systems
• Efficient protocols for generating bipartite classical distributions and quantum states
• 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)