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:1412.0449

The Generation Cost of Bipartite Quantum States under LOCC

Zhaohui Wei, Zhang‐qi Yin

Published Dec 1, 2014• 0 citations
arXivHTMLPDF

Abstract

We consider a realistic setting of quantum tasks that generate shared bipartite quantum states. Suppose \alice and \bob are located at different places and need to produce a target shared quantum state $ρ$. In order to save quantum communication, they can choose to share a proper smaller quantum state $σ$ first, and then turn $σ$ to $ρ$ by performing only local quantum operations and classical communications (LOCC). We hope $σ$ is the optimal such that the quantum communication needed is as little as possible, which is called the generation cost of $ρ$. In this paper, for an arbitrary bipartite $ρ$, we characterize its generation cost completely by proving that it is exactly equivalent to the logarithm of the Schmidt number of $ρ$. Similar quantum schemes where classical communication is not allowed have actually been considered. By comparing the two settings, we are able to look into the role that classical communication plays in these fundamental tasks, where we exhibit some instances in which classical communication is not helpful completely.

DOI
10.48550/arxiv.1412.0449

Related papers

A coding theorem for bipartite unitaries in distributed quantum computation

Eyuri Wakakuwa, Akihito Soeda, Mio Murao

We analyze implementations of bipartite unitaries in a distributed quantum computation setting using local operations and classical communication (LOCC) assisted by shared entanglement. We employ concepts and techniques developed in quantum Shannon theory to study an asymptotic scenario in which the two distant parties perform the same bipartite unitary on infinitely many pairs of input states generated by a completely random i.i.d. (independent and identically distributed) quantum information source. We analyze the minimum costs of resources of entanglement and classical communication per copy. For protocols consisting of two-round LOCC, we prove that an achievable rate tuple of costs of entanglement and classical communication is given by the “Markovianizing cost” of a tripartite state associated with the unitary, which is conjectured to be optimal as well. The Markovianizing cost can be computed by a finite-step algorithm.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2015•6 citations

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

Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States

Rahul Jain, Yaoyun Shi, Zhaohui Wei +1 more

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 ϵ 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 etal. (SIAM J. Comput., 32 (6):1570-1585, 2003).

IEEE Transactions on Information Theory•May 15, 2013•56 citations

Efficient protocols for generating bipartite classical distributions and quantum states

Rahul Jain, Yaoyun Shi, Zhaohui Wei +1 more

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, Massar, Pokutta, Tiwary and de Wolf (Proceedings of the 44th A CM 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 (SIAM Journal on Computing, 32(6):1570–1585, 2003).

ACM-SIAM Symposium on Discrete Algorithms (SODA)•Jan 6, 2013•3 citations

More assistance of entanglement, less rounds of classical communication

Atanu Bhunia, Indranil Biswas, Indrani Chattopadhyay +1 more

Abstract Classical communication plays a crucial role to distinguish locally a class of quantum states. Despite considerable advances, we have very little knowledge about the number of measurement and communication rounds needed to implement a discrimination task by local quantum operations and classical communications (in short, LOCC). In this paper, we are able to show the relation between round numbers with the local discrimination of a set of pure bipartite orthogonal quantum states. To demonstrate the possible strong dependence on the round numbers, we consider a class of orthogonal product states in d ⊗ d , which require at least 2 d − 2 round of classical communications. Curiously the round number can be reduced to d by the assistance of one-ebit of entanglement as resource and can be reduced further by assistance of more entanglement. We are also able to show that the number of LOCC rounds needed for a discrimination task may depend on the amount of entanglement assistance.

arXiv:2303.13645•Journal of Physics A Mathematical and Theoretical•Aug 7, 2023•7 citations

Quantum states with the same entanglement and local unitary equivalence

Julio I. de Vicente

Local operations assisted by classical communication (LOCC) play a fundamental role in the resource-theoretic formulation of entanglement theory inducing an operationally meaningful ordering in the set of entangled states. The particular class within LOCC of local unitary (LU) transformations is obviously closed under inversion. Thus, LU-equivalent states are interconvertible by LOCC and have therefore the same entanglement. For this reason LU-equivalence has been thoroughly studied in the context of entanglement theory. However, as I note here with a simple example, the converse is not true: there exist entangled states that are interconvertible by LOCC but which are not LU-equivalent. This motivates studying under which conditions LOCC interconvertibility is characterized by LU-equivalence. I provide a sufficient condition for this to hold. When one considers multipartite states with full entanglement dimensionality (as quantified by the Schmidt number vector) LOCC interconvertibility can only hold under LU-equivalence.

quant-pharXiv:2609.21558•Sep 21, 2026•0 citations
We consider a realistic setting of quantum tasks that generate shared bipartite quantum states. Suppose \alice and \bob are located at different places and need to produce a target shared quantum state ρρρ. In order to save quantum communication, they can choose to share a proper smaller quantum state σσσ first, and then turn σσσ to ρρρ by performing only local quantum operations and classical communications (LOCC). We hope σσσ is the optimal such that the quantum communication needed is as little as possible, which is called the generation cost of ρρρ. In this paper, for an arbitrary bipartite ρρρ, we characterize its generation cost completely by proving that it is exactly equivalent to the logarithm of the Schmidt number of ρρρ. Similar quantum schemes where classical communication is not allowed have actually been considered. By comparing the two settings, we are able to look into the role that classical communication plays in these fundamental tasks, where we exhibit some instances in which classical communication is not helpful completely.
We analyze implementations of bipartite unitaries in a distributed quantum computation setting using local operations and classical communication (LOCC) assisted by shared entanglement. We employ concepts and techniques developed in quantum Shannon theory to study an asymptotic scenario in which the two distant parties perform the same bipartite unitary on infinitely many pairs of input states generated by a completely random i.i.d. (independent and identically distributed) quantum information source. We analyze the minimum costs of resources of entanglement and classical communication per copy. For protocols consisting of two-round LOCC, we prove that an achievable rate tuple of costs of entanglement and classical communication is given by the “Markovianizing cost” of a tripartite state associated with the unitary, which is conjectured to be optimal as well. The Markovianizing cost can be computed by a finite-step algorithm.
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.
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 ϵ 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 etal. (SIAM J. Comput., 32 (6):1570-1585, 2003).
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, Massar, Pokutta, Tiwary and de Wolf (Proceedings of the 44th A CM 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 (SIAM Journal on Computing, 32(6):1570–1585, 2003).
Abstract Classical communication plays a crucial role to distinguish locally a class of quantum states. Despite considerable advances, we have very little knowledge about the number of measurement and communication rounds needed to implement a discrimination task by local quantum operations and classical communications (in short, LOCC). In this paper, we are able to show the relation between round numbers with the local discrimination of a set of pure bipartite orthogonal quantum states. To demonstrate the possible strong dependence on the round numbers, we consider a class of orthogonal product states in d ⊗ d , which require at least 2 d − 2 round of classical communications. Curiously the round number can be reduced to d by the assistance of one-ebit of entanglement as resource and can be reduced further by assistance of more entanglement. We are also able to show that the number of LOCC rounds needed for a discrimination task may depend on the amount of entanglement assistance.
Local operations assisted by classical communication (LOCC) play a fundamental role in the resource-theoretic formulation of entanglement theory inducing an operationally meaningful ordering in the set of entangled states. The particular class within LOCC of local unitary (LU) transformations is obviously closed under inversion. Thus, LU-equivalent states are interconvertible by LOCC and have therefore the same entanglement. For this reason LU-equivalence has been thoroughly studied in the context of entanglement theory. However, as I note here with a simple example, the converse is not true: there exist entangled states that are interconvertible by LOCC but which are not LU-equivalent. This motivates studying under which conditions LOCC interconvertibility is characterized by LU-equivalence. I provide a sufficient condition for this to hold. When one considers multipartite states with full entanglement dimensionality (as quantified by the Schmidt number vector) LOCC interconvertibility can only hold under LU-equivalence.