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:2204.00781 · Quantum

The Round Complexity of Local Operations and Classical Communication (LOCC) in Random-Party Entanglement Distillation

Guangkuo Liu, Ian M. George, Eric Chitambar

Published Sep 7, 2023• 4 citations
arXivHTMLPDF

Abstract

A powerful operational paradigm for distributed quantum information processing involves manipulating pre-shared entanglement by local operations and classical communication (LOCC). The LOCC round complexity of a given task describes how many rounds of classical communication are needed to complete the task. Despite some results separating one-round versus two-round protocols, very little is known about higher round complexities. In this paper, we revisit the task of one-shot random-party entanglement distillation as a way to highlight some interesting features of LOCC round complexity. We first show that for random-party distillation in three qubits, the number of communication rounds needed in an optimal protocol depends on the entanglement measure used; for the same fixed state some entanglement measures need only two rounds to maximize whereas others need an unbounded number of rounds. In doing so, we construct a family of LOCC instruments that require an unbounded number of rounds to implement. We then prove explicit tight lower bounds on the LOCC round number as a function of distillation success probability. Our calculations show that the original W-state random distillation protocol by Fortescue and Lo is essentially optimal in terms of round complexity.

DOI
10.22331/q-2023-09-07-1104

Related papers

Local Quantum Transformations Requiring Infinite Rounds of Classical Communication

Eric Chitambar

In this Letter, we investigate the number of measurement and communication rounds needed to implement certain tasks by local quantum operations and classical communication (LOCC), a relatively unexplored topic. To demonstrate the possible strong dependence on the round number, we consider the problem of converting three-qubit entanglement into two-qubit form, specifically in the random distillation setting of [Phys. Rev. Lett. 98, 260501 (2007)]. We find that the number of LOCC rounds needed for a transformation can depend on the amount of entanglement distilled. In fact, for a wide range of transformations, the required number of rounds is infinite (unbounded). This represents the first concrete example of a task needing an infinite number of rounds to implement.

arXiv:1105.3451•Physical Review Letters•Nov 4, 2011•49 citations

A Four-Round LOCC Protocol Outperforms All Two-Round Protocols in Reducing the Entanglement Cost for A Distributed Quantum Information Processing

Eyuri Wakakuwa, Akihito Soeda, Mio Murao

We prove that there is a trade-off relation between the entanglement cost and the number of rounds of communication, for two distant parties to accomplish a bidirectional quantum information task by local operations and classical communication (LOCC). We consider an implementation of a class of two-qubit controlled-unitary gate by LOCC assisted by shared entanglement, in an information theoretical scenario of asymptotically many input pairs and vanishingly small error. We prove the trade-off relation by showing that one ebit of entanglement per pair is necessary to be consumed for implementing the unitary by any two-round protocol, whereas the entanglement cost by a four-round protocol is strictly smaller than one ebit per pair.

arXiv:1608.07461•Aug 26, 2016•5 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

Strong bounds on required resources for quantum channels by local operations and classical communication

Scott M. Cohen

Given a protocol $\mathcal{P}$ that implements multipartite quantum channel $\mathcal{E}$ by repeated rounds of local operations and classical communication (LOCC), we construct an alternate LOCC protocol for $\mathcal{E}$ in no more rounds than $\mathcal{P}$ and no more than a fixed, constant number of outcomes for each local measurement, the same constant number for every party and every round. We then obtain another upper bound on the number of outcomes that, under certain conditions, improves on the first. The latter bound shows that for LOCC channels that are extreme points of the convex set of all quantum channels, the parties can restrict the number of outcomes in their individual local measurements to no more than the square of their local Hilbert space dimension, ${d}_{\ensuremath{\alpha}}$, suggesting a possible link between the required resources for LOCC and the convex structure of the set of all quantum channels. Our bounds on the number of outcomes indicating the need for only constant resources per round, independent of the number of rounds $r$ including when that number is infinite, are a stark contrast to the exponential $r$ dependence in the only previously published bound of which we are aware. If a lower bound is known on the number of product operators needed to represent the channel, we obtain a lower bound on the number of rounds required to implement the given channel by LOCC. Finally, we show that when the quantum channel is not required but only that a given task be implemented deterministically, then no more than ${d}_{\ensuremath{\alpha}}^{2}$ outcomes are needed for each local measurement by party $\ensuremath{\alpha}$.

arXiv:1904.10980•Physical Review A•Oct 21, 2019•1 citation

Everything you always wanted to know about LOCC (but were afraid to ask

Eric Chitambar, Debbie Leung, Māris Ozols +1 more

In this paper we study the subset of generalized quantum measurements on finite dimensional systems known as local operations and classical communication (LOCC). While LOCC emerges as the natural class of operations in many important quantum information tasks, its mathematical structure is complex and difficult to characterize. Here we provide a precise description of LOCC and related operational classes in terms of quantum instruments. Our formalism captures both finite round protocols as well as those that utilize an unbounded number of communication rounds. While the set of LOCC is not topologically closed, we show that finite round LOCC constitutes a compact subset of quantum operations. Additionally we show the existence of an open ball around the completely depolarizing map that consists entirely of LOCC implementable maps. Finally, we demonstrate a two-qubit map whose action can be approached arbitrarily close using LOCC, but nevertheless cannot be implemented perfectly.

•Aug 17, 2016•181 citations

Round complexity in the local transformations of quantum and classical states

Eric Chitambar, Min-Hsiu Hsieh

In distributed quantum and classical information processing, spatially separated parties operate locally on their respective subsystems, but coordinate their actions through multiple exchanges of public communication. With interaction, the parties can perform more tasks. But how the exact number and order of exchanges enhances their operational capabilities is not well understood. Here we consider the minimum number of communication rounds needed to perform the locality-constrained tasks of entanglement transformation and its classical analog of secrecy manipulation. We provide an explicit construction of both quantum and classical state transformations which, for any given r, can be achieved using r rounds of classical communication exchanges, but no fewer. To show this, we build on the common structure underlying both resource theories of quantum entanglement and classical secret key. Our results reveal that highly complex communication protocols are indeed necessary to fully harness the information-theoretic resources contained in general quantum and classical states.

arXiv:1610.01998•Nature Communications•Dec 6, 2017•18 citations
A powerful operational paradigm for distributed quantum information processing involves manipulating pre-shared entanglement by local operations and classical communication (LOCC). The LOCC round complexity of a given task describes how many rounds of classical communication are needed to complete the task. Despite some results separating one-round versus two-round protocols, very little is known about higher round complexities. In this paper, we revisit the task of one-shot random-party entanglement distillation as a way to highlight some interesting features of LOCC round complexity. We first show that for random-party distillation in three qubits, the number of communication rounds needed in an optimal protocol depends on the entanglement measure used; for the same fixed state some entanglement measures need only two rounds to maximize whereas others need an unbounded number of rounds. In doing so, we construct a family of LOCC instruments that require an unbounded number of rounds to implement. We then prove explicit tight lower bounds on the LOCC round number as a function of distillation success probability. Our calculations show that the original W-state random distillation protocol by Fortescue and Lo is essentially optimal in terms of round complexity.
In this Letter, we investigate the number of measurement and communication rounds needed to implement certain tasks by local quantum operations and classical communication (LOCC), a relatively unexplored topic. To demonstrate the possible strong dependence on the round number, we consider the problem of converting three-qubit entanglement into two-qubit form, specifically in the random distillation setting of [Phys. Rev. Lett. 98, 260501 (2007)]. We find that the number of LOCC rounds needed for a transformation can depend on the amount of entanglement distilled. In fact, for a wide range of transformations, the required number of rounds is infinite (unbounded). This represents the first concrete example of a task needing an infinite number of rounds to implement.
We prove that there is a trade-off relation between the entanglement cost and the number of rounds of communication, for two distant parties to accomplish a bidirectional quantum information task by local operations and classical communication (LOCC). We consider an implementation of a class of two-qubit controlled-unitary gate by LOCC assisted by shared entanglement, in an information theoretical scenario of asymptotically many input pairs and vanishingly small error. We prove the trade-off relation by showing that one ebit of entanglement per pair is necessary to be consumed for implementing the unitary by any two-round protocol, whereas the entanglement cost by a four-round protocol is strictly smaller than one ebit per pair.
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.
Given a protocol P\mathcal{P}P that implements multipartite quantum channel E\mathcal{E}E by repeated rounds of local operations and classical communication (LOCC), we construct an alternate LOCC protocol for E\mathcal{E}E in no more rounds than P\mathcal{P}P and no more than a fixed, constant number of outcomes for each local measurement, the same constant number for every party and every round. We then obtain another upper bound on the number of outcomes that, under certain conditions, improves on the first. The latter bound shows that for LOCC channels that are extreme points of the convex set of all quantum channels, the parties can restrict the number of outcomes in their individual local measurements to no more than the square of their local Hilbert space dimension, ${d}_{\ensuremath{\alpha}}$, suggesting a possible link between the required resources for LOCC and the convex structure of the set of all quantum channels. Our bounds on the number of outcomes indicating the need for only constant resources per round, independent of the number of rounds rrr including when that number is infinite, are a stark contrast to the exponential rrr dependence in the only previously published bound of which we are aware. If a lower bound is known on the number of product operators needed to represent the channel, we obtain a lower bound on the number of rounds required to implement the given channel by LOCC. Finally, we show that when the quantum channel is not required but only that a given task be implemented deterministically, then no more than ${d}_{\ensuremath{\alpha}}^{2}$ outcomes are needed for each local measurement by party $\ensuremath{\alpha}$.
In this paper we study the subset of generalized quantum measurements on finite dimensional systems known as local operations and classical communication (LOCC). While LOCC emerges as the natural class of operations in many important quantum information tasks, its mathematical structure is complex and difficult to characterize. Here we provide a precise description of LOCC and related operational classes in terms of quantum instruments. Our formalism captures both finite round protocols as well as those that utilize an unbounded number of communication rounds. While the set of LOCC is not topologically closed, we show that finite round LOCC constitutes a compact subset of quantum operations. Additionally we show the existence of an open ball around the completely depolarizing map that consists entirely of LOCC implementable maps. Finally, we demonstrate a two-qubit map whose action can be approached arbitrarily close using LOCC, but nevertheless cannot be implemented perfectly.
In distributed quantum and classical information processing, spatially separated parties operate locally on their respective subsystems, but coordinate their actions through multiple exchanges of public communication. With interaction, the parties can perform more tasks. But how the exact number and order of exchanges enhances their operational capabilities is not well understood. Here we consider the minimum number of communication rounds needed to perform the locality-constrained tasks of entanglement transformation and its classical analog of secrecy manipulation. We provide an explicit construction of both quantum and classical state transformations which, for any given r, can be achieved using r rounds of classical communication exchanges, but no fewer. To show this, we build on the common structure underlying both resource theories of quantum entanglement and classical secret key. Our results reveal that highly complex communication protocols are indeed necessary to fully harness the information-theoretic resources contained in general quantum and classical states.