Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1405.6015 · Computational Complexity

Multipartite Quantum Correlation and Communication Complexities

Rahul Jain, Zhaohui Wei, Penghui Yao, Shengyu Zhang

Published May 23, 2016• 4 citations
arXivHTMLPDF
DOI
10.1007/s00037-016-0126-y

Related papers

Approximate and Multipartite Quantum Correlation (Communication) Complexity

Rahul Jain, Zhaohui Wei, Penghui Yao +1 more

The concepts of quantum correlation and communication complexity have been proposed to quantify the worst-case computational resources needed in generating bipartite classical distributions or bipartite quantum states in the single-shot setting by Zhang (Proc. 3rd Innov Theor Comput., pp. 39-59, 2012). The former characterizes the minimal size of the initial shared state needed if no communication is allowed, and the latter characterizes the minimal amount of communication needed if sharing nothing at the beginning. In this paper, we generalize these two concepts to approximate bipartite cases and various multipartite cases. 1. To generate a bipartite classical distribution P (x, y) approximately, we show that the minimal amount of quantum communication needed can be characterized completely by the approximate PSD-rank of P . This result is obtained based on the fact that the cost to approximate a bipartite quantum state equals that to approximate its exact purifications, which also implies a result for a general bipartite quantum state. 2. In the bipartite case, correlation complexity is always equivalent to communication complexity, but in multipartite cases, this is not true any more. For multipartite pure states, we show that both of them could be characterized by local ranks of subsystems. 3. For any bipartite quantum state, its correlation complexity is always equivalent to that of its optimal purification, while in multipartite cases the former could be smaller strictly than the latter. We characterize the relationship between them by giving upper and lower bounds. 4. For multipartite classical distributions, we show that the approximate correlation complexity could also be characterized by the generalized PSD-rank.

•May 23, 2014•0 citations

Information, Quantum Correlations and Communication

Stephen Mark Barnett, David Thomas Pegg, Simon J. D. Phoenix

NATO ASI series. Series B : Physics•Jan 1, 1992•1 citation

Complementary quantum correlations among multipartite systems

Zhi‐Xiang Jin, Shao-Ming Fei, Cong‐Feng Qiao

arXiv:2002.04456•Quantum Information Processing•Feb 4, 2020•17 citations

Quantum Correlations Require Multipartite Information Principles

Rodrigo Gallego, Lars Erik Würflinger, Antonio Acín +1 more

Identifying which correlations among distant observers are possible within our current description of nature, based on quantum mechanics, is a fundamental problem in physics. Recently, information concepts have been proposed as the key ingredient to characterize the set of quantum correlations. Novel information principles, such as information causality or nontrivial communication complexity, have been introduced in this context and successfully applied to some concrete scenarios. We show in this work a fundamental limitation of this approach: no principle based on bipartite information concepts is able to singleout the set of quantum correlations for an arbitrary number of parties. Our results reflect the intricate structure of quantum correlations and imply that new and intrinsically multipartite information concepts are needed for their full understanding.

arXiv:1107.3738•Physical Review Letters•Nov 15, 2011•99 citations

Quantum Correlations in Multipartite Quantum Systems

Thiago Rodrigues de Oliveira

arXiv:1706.03101•Quantum science and technology•Jan 1, 2017•1 citation

Measuring multipartite quantum correlations by thermodynamic work extraction

Toshihiro Yada, Nobuyuki Yoshioka, Takahiro Sagawa

While bipartite quantum correlations have been extensively studied across various fields, the role of multipartite quantum correlations in many-body systems remains elusive due to their complex structure. A primary challenge lies in the fact that the calculation of multipartite quantum correlation measure often requires an exponential cost with respect to the system size. In this work, we address this problem by adopting a thermodynamic approach: We introduce a measure of multipartite quantum correlations based on the difference in extractable thermodynamic work between global operations and LOCC (local operations and classical communication). This can be regarded as a multipartite generalization of the bipartite work deficit, which has attracted attention as a thermodynamic measure of bipartite quantum correlation. Importantly, we develop an efficient method for computing the multipartite work deficit in a special class of quantum many-body systems described by matrix product states (MPS). The numerical cost of this method scales linearly with system size, significantly reducing the exponential overhead required for direct calculations. We apply this method to an MPS family and show that a quantum phase transition is well captured by the multipartite work deficit, which exhibits singular behavior at the transition point. Our work shows that the multipartite work deficit not only highlights the fundamental connection between multipartite quantum correlations and quantum thermodynamics, but also serves as an efficiently computable probe of the structures of quantum many-body systems.

arXiv:2407.04058•Physical Review Research•Oct 14, 2025•4 citations
The concepts of quantum correlation and communication complexity have been proposed to quantify the worst-case computational resources needed in generating bipartite classical distributions or bipartite quantum states in the single-shot setting by Zhang (Proc. 3rd Innov Theor Comput., pp. 39-59, 2012). The former characterizes the minimal size of the initial shared state needed if no communication is allowed, and the latter characterizes the minimal amount of communication needed if sharing nothing at the beginning. In this paper, we generalize these two concepts to approximate bipartite cases and various multipartite cases. 1. To generate a bipartite classical distribution P (x, y) approximately, we show that the minimal amount of quantum communication needed can be characterized completely by the approximate PSD-rank of P . This result is obtained based on the fact that the cost to approximate a bipartite quantum state equals that to approximate its exact purifications, which also implies a result for a general bipartite quantum state. 2. In the bipartite case, correlation complexity is always equivalent to communication complexity, but in multipartite cases, this is not true any more. For multipartite pure states, we show that both of them could be characterized by local ranks of subsystems. 3. For any bipartite quantum state, its correlation complexity is always equivalent to that of its optimal purification, while in multipartite cases the former could be smaller strictly than the latter. We characterize the relationship between them by giving upper and lower bounds. 4. For multipartite classical distributions, we show that the approximate correlation complexity could also be characterized by the generalized PSD-rank.
Identifying which correlations among distant observers are possible within our current description of nature, based on quantum mechanics, is a fundamental problem in physics. Recently, information concepts have been proposed as the key ingredient to characterize the set of quantum correlations. Novel information principles, such as information causality or nontrivial communication complexity, have been introduced in this context and successfully applied to some concrete scenarios. We show in this work a fundamental limitation of this approach: no principle based on bipartite information concepts is able to singleout the set of quantum correlations for an arbitrary number of parties. Our results reflect the intricate structure of quantum correlations and imply that new and intrinsically multipartite information concepts are needed for their full understanding.
While bipartite quantum correlations have been extensively studied across various fields, the role of multipartite quantum correlations in many-body systems remains elusive due to their complex structure. A primary challenge lies in the fact that the calculation of multipartite quantum correlation measure often requires an exponential cost with respect to the system size. In this work, we address this problem by adopting a thermodynamic approach: We introduce a measure of multipartite quantum correlations based on the difference in extractable thermodynamic work between global operations and LOCC (local operations and classical communication). This can be regarded as a multipartite generalization of the bipartite work deficit, which has attracted attention as a thermodynamic measure of bipartite quantum correlation. Importantly, we develop an efficient method for computing the multipartite work deficit in a special class of quantum many-body systems described by matrix product states (MPS). The numerical cost of this method scales linearly with system size, significantly reducing the exponential overhead required for direct calculations. We apply this method to an MPS family and show that a quantum phase transition is well captured by the multipartite work deficit, which exhibits singular behavior at the transition point. Our work shows that the multipartite work deficit not only highlights the fundamental connection between multipartite quantum correlations and quantum thermodynamics, but also serves as an efficiently computable probe of the structures of quantum many-body systems.