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:0908.0440 · Physical Review A

Multipartite-to-bipartite entanglement transformations and polynomial identity testing

Eric Chitambar, Runyao Duan, Yaoyun Shi

Published May 10, 2010• 12 citations
arXivHTMLPDF

Abstract

We consider the problem of deciding if some multiparty entangled pure state can be converted, with a nonzero success probability, into a given bipartite pure state shared between two specified parties through local quantum operations and classical communication. We show that this question is equivalent to the well-known computational problem of deciding if a multivariate polynomial is identically zero. Efficient randomized algorithms developed to study the latter can thus be applied to our question. As a result, a given transformation is possible if and only if it is generically attainable by a simple randomized protocol.

DOI
10.1103/physreva.81.052310

Related papers

Deciding unitary equivalence between matrix polynomials and sets of bipartite quantum states

Eric Chitambar, Carl A. Miller, Yaoyun Shi

In this brief report, we consider the equivalence between two sets of m + 1 bipartite quantum states under local unitary transformations. For pure states, this problem corresponds to the matrix algebra question of whether two degree m matrix polynomials are unitarily equivalent; i.e. UAiV† = Bi for 0 ≤ i ≤ m where U and V are unitary and (Ai, Bi) are arbitrary pairs of rectangular matrices. We present a randomized polynomial-time algorithm that solves this problem with an arbitrarily high success probability and outputs transforming matrices U and V.

Quantum Information and Computation•Sep 1, 2011•0 citations

Deciding unitary equivalence between matrix polynomials and sets of bipartite quantum states

Eric Chitambar, Carl W. Miller, Yaoyun Shi

In this brief report, we consider the equivalence between two sets of $m+1$ bipartite quantum states under local unitary transformations. For pure states, this problem corresponds to the matrix algebra question of whether two degree $m$ matrix polynomials are unitarily equivalent; i.e. $UA_iV^\dagger=B_i$ for $0\leq i\leq m$ where $U$ and $V$ are unitary and $(A_i, B_i)$ are arbitrary pairs of rectangular matrices. We present a randomized polynomial-time algorithm that solves this problem with an arbitrarily high success probability and outputs transforming matrices $U$ and $V$.

Quantum Information and Computation•Sep 1, 2011•0 citations

Deciding Unitary Equivalence Between Matrix Polynomials and Sets of Bipartite Quantum States

Eric Chitambar, Carl A. Miller, Yaoyun Shi

In this brief report, we consider the equivalence between two sets of $m+1$ bipartite quantum states under local unitary transformations. For pure states, this problem corresponds to the matrix algebra question of whether two degree $m$ matrix polynomials are unitarily equivalent; i.e. $UA_iV^\dagger=B_i$ for $0\leq i\leq m$ where $U$ and $V$ are unitary and $(A_i, B_i)$ are arbitrary pairs of rectangular matrices. We present a randomized polynomial-time algorithm that solves this problem with an arbitrarily high success probability and outputs transforming matrices $U$ and $V$.

arXiv:1010.1018•Oct 5, 2010•0 citations

Reexamination of quantum state transformations with zero communication

Ian George, Eric Chitambar

It is known that general convertibility of bipartite entangled states is not possible to arbitrary error without some classical communication. While some tradeoffs between communication cost and conversion error have been proven, these bounds can be very loose. In particular, there are many cases in which tolerable error might be achievable using zero-communication protocols. In this work we address these cases by deriving the optimal fidelity of pure quantum state conversions under local unitaries as well as local operations and shared randomness. We also use these results to explore catalytic conversions between pure states using zero communication.

arXiv:2301.04735•Physical Review A•Jun 12, 2024•4 citations

Computational complexity in entanglement transformations

Eric Chitambar

In physics, systems having three parts are typically much more difficult to analyze than those having just two. Even in classical mechanics, predicting the motion of three interacting celestial bodies remains an insurmountable challenge while the analogous two-body problem has an elementary solution. It is as if just by adding a third party, a fundamental change occurs in the structure of the problem that renders it unsolvable. In this thesis, we demonstrate how such an effect is likewise present in the theory of quantum entanglement. In fact, the complexity differences between two-party and three-party entanglement become quite conspicuous when comparing the difficulty in deciding what state changes are possible for these systems when no additional entanglement is consumed in the transformation process. We examine this entanglement transformation question and its variants in the language of computational complexity theory, a powerful subject that formalizes the concept of problem difficulty. Since deciding feasibility of a specified bipartite transformation is relatively easy, this task belongs to the complexity class P. On the other hand, for tripartite systems, we find the problem to be NP-Hard, meaning that its solution is at least as hard as the solution to some of the most difficult problems humans have encountered. One can then rigorously defend the assertion that a fundamental complexity difference exists between bipartite and tripartite entanglement since unlike the former, the full range of forms realizable by the latter is incalculable (assuming P unequal to NP). However, similar to the three-body celestial problem, when one examines a special subclass of the problem - invertible transformations on systems having at least one qubit subsystem - we prove that the problem can be solved efficiently. As a hybrid of the two questions, we find that the question of tripartite to bipartite transformations can be solved by an efficient randomized algorithm. Our results are obtained by encoding well-studied computational problems such as polynomial identity testing and tensor rank into questions of entanglement transformation. In this way, entanglement theory provides a physical manifestation of some of the most puzzling and abstract classical computation questions.

•Jan 1, 2010•0 citations

Application and Manipulation of Bipartite and Multipartite Entangled States

Ben Fortescue

The phenomenon of quantum entanglement is a fundamental feature of quantum mechanics which, as a counterintuitive and inherently ”quantum” phenomenon (with no classical analogue) has been the subject of much study, especially in quantum information theory. One fruitful approach to the description of entanglement has been in its operational description - that is, in the consideration of what can be achieved using entangled states under certain restrictions, typically the regime of local operations and classical communications.\n\nWe present results here related to the operational characterisation of entanglement in the resource model, in both bipartite and multipartite cases. First, we consider the conversion between pure bipartite entangled states in terms of an often-ignored resource - the classical communication cost. Using prior results for more specific conversions, we derive lower bounds on this cost (and the related quantity of the conversion inefficiency) for general bipartite pure states.\n\nWe also consider pure-state conversions of multipartite entanglement, in particular the class of protocols in which multipartite states are converted to states shared between fewer parties. We have found a previously-unconsidered variety of such conversions, in which the target state of the conversion is a state shared between a random subset of the parties. We find that when such post-selection of parties in the protocol is permitted allows for a wider variety of achievable target states; certain states which can not be reliably obtained between predetermined parties (even some where the probability of doing so is arbitrarily small) can be obtained between random parties. We consider a variety of states in which this phenomenon occurs, as well as bounds on such protocols can achieve.\n\nFinally we consider a practical use of entanglement as a resource, in an experimental implementation of a multipartite QKD protocol. This is based on the tripartite GHZ entangled state, but can be implemented using only bipartite entanglement. We adapt existing QKD results for both the bipartite and multipartite case to derive a secure key rate for this implementation, taking into account the ways in which it differs from the idealised theoretical case.

•Sep 24, 2009•0 citations
We consider the problem of deciding if some multiparty entangled pure state can be converted, with a nonzero success probability, into a given bipartite pure state shared between two specified parties through local quantum operations and classical communication. We show that this question is equivalent to the well-known computational problem of deciding if a multivariate polynomial is identically zero. Efficient randomized algorithms developed to study the latter can thus be applied to our question. As a result, a given transformation is possible if and only if it is generically attainable by a simple randomized protocol.
In this brief report, we consider the equivalence between two sets of m + 1 bipartite quantum states under local unitary transformations. For pure states, this problem corresponds to the matrix algebra question of whether two degree m matrix polynomials are unitarily equivalent; i.e. UAiV† = Bi for 0 ≤ i ≤ m where U and V are unitary and (Ai, Bi) are arbitrary pairs of rectangular matrices. We present a randomized polynomial-time algorithm that solves this problem with an arbitrarily high success probability and outputs transforming matrices U and V.
In this brief report, we consider the equivalence between two sets of m+1m+1m+1 bipartite quantum states under local unitary transformations. For pure states, this problem corresponds to the matrix algebra question of whether two degree mmm matrix polynomials are unitarily equivalent; i.e. UAiV†=BiUA_iV^\dagger=B_iUAi​V†=Bi​ for 0≤i≤m0\leq i\leq m0≤i≤m where UUU and VVV are unitary and (Ai,Bi)(A_i, B_i)(Ai​,Bi​) are arbitrary pairs of rectangular matrices. We present a randomized polynomial-time algorithm that solves this problem with an arbitrarily high success probability and outputs transforming matrices UUU and VVV.
In this brief report, we consider the equivalence between two sets of m+1m+1m+1 bipartite quantum states under local unitary transformations. For pure states, this problem corresponds to the matrix algebra question of whether two degree mmm matrix polynomials are unitarily equivalent; i.e. UAiV†=BiUA_iV^\dagger=B_iUAi​V†=Bi​ for 0≤i≤m0\leq i\leq m0≤i≤m where UUU and VVV are unitary and (Ai,Bi)(A_i, B_i)(Ai​,Bi​) are arbitrary pairs of rectangular matrices. We present a randomized polynomial-time algorithm that solves this problem with an arbitrarily high success probability and outputs transforming matrices UUU and VVV.
It is known that general convertibility of bipartite entangled states is not possible to arbitrary error without some classical communication. While some tradeoffs between communication cost and conversion error have been proven, these bounds can be very loose. In particular, there are many cases in which tolerable error might be achievable using zero-communication protocols. In this work we address these cases by deriving the optimal fidelity of pure quantum state conversions under local unitaries as well as local operations and shared randomness. We also use these results to explore catalytic conversions between pure states using zero communication.
In physics, systems having three parts are typically much more difficult to analyze than those having just two. Even in classical mechanics, predicting the motion of three interacting celestial bodies remains an insurmountable challenge while the analogous two-body problem has an elementary solution. It is as if just by adding a third party, a fundamental change occurs in the structure of the problem that renders it unsolvable. In this thesis, we demonstrate how such an effect is likewise present in the theory of quantum entanglement. In fact, the complexity differences between two-party and three-party entanglement become quite conspicuous when comparing the difficulty in deciding what state changes are possible for these systems when no additional entanglement is consumed in the transformation process. We examine this entanglement transformation question and its variants in the language of computational complexity theory, a powerful subject that formalizes the concept of problem difficulty. Since deciding feasibility of a specified bipartite transformation is relatively easy, this task belongs to the complexity class P. On the other hand, for tripartite systems, we find the problem to be NP-Hard, meaning that its solution is at least as hard as the solution to some of the most difficult problems humans have encountered. One can then rigorously defend the assertion that a fundamental complexity difference exists between bipartite and tripartite entanglement since unlike the former, the full range of forms realizable by the latter is incalculable (assuming P unequal to NP). However, similar to the three-body celestial problem, when one examines a special subclass of the problem - invertible transformations on systems having at least one qubit subsystem - we prove that the problem can be solved efficiently. As a hybrid of the two questions, we find that the question of tripartite to bipartite transformations can be solved by an efficient randomized algorithm. Our results are obtained by encoding well-studied computational problems such as polynomial identity testing and tensor rank into questions of entanglement transformation. In this way, entanglement theory provides a physical manifestation of some of the most puzzling and abstract classical computation questions.
The phenomenon of quantum entanglement is a fundamental feature of quantum mechanics which, as a counterintuitive and inherently ”quantum” phenomenon (with no classical analogue) has been the subject of much study, especially in quantum information theory. One fruitful approach to the description of entanglement has been in its operational description - that is, in the consideration of what can be achieved using entangled states under certain restrictions, typically the regime of local operations and classical communications.\n\nWe present results here related to the operational characterisation of entanglement in the resource model, in both bipartite and multipartite cases. First, we consider the conversion between pure bipartite entangled states in terms of an often-ignored resource - the classical communication cost. Using prior results for more specific conversions, we derive lower bounds on this cost (and the related quantity of the conversion inefficiency) for general bipartite pure states.\n\nWe also consider pure-state conversions of multipartite entanglement, in particular the class of protocols in which multipartite states are converted to states shared between fewer parties. We have found a previously-unconsidered variety of such conversions, in which the target state of the conversion is a state shared between a random subset of the parties. We find that when such post-selection of parties in the protocol is permitted allows for a wider variety of achievable target states; certain states which can not be reliably obtained between predetermined parties (even some where the probability of doing so is arbitrarily small) can be obtained between random parties. We consider a variety of states in which this phenomenon occurs, as well as bounds on such protocols can achieve.\n\nFinally we consider a practical use of entanglement as a resource, in an experimental implementation of a multipartite QKD protocol. This is based on the tripartite GHZ entangled state, but can be implemented using only bipartite entanglement. We adapt existing QKD results for both the bipartite and multipartite case to derive a secure key rate for this implementation, taking into account the ways in which it differs from the idealised theoretical case.