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

Applications of matrix spaces in quantum information and computational complexity

Yinan Li

Published Jan 1, 2018• 0 citations
OpenAlex

Abstract

This thesis explores the applications of matrix spaces in quantum information and computational complexity, specifically in the areas of quantum state/channel discrimination, entanglement transformation and isomorphism testing.We achieve the following contributions:• We derive a necessary condition which determines whether a set of orthogonal bipartite states can be distinguished by positive-partial-transpose (PPT) operations, in the many-copy scenario.We reduce the discrimination task to the following problem:Decide whether there exist a nonzero bipartite matrix with positive partial-transpose, such that all its eigenvectors with nonzero eigenvalues is orthogonal to a given bipartite vector space.As applications, we reprove and extend a variety of existing results, including the local indistinguishability of the bipartite maximally entangled state and its orthogonal complement [Yu, Duan and Ying, IEEE transaction on Information Theory, 2014] and the maximum dimension of non-positive-partialtranspose subspaces [Johnston, Physical Review A, 2013].• We show that determining the parallel distinguishability of quantum channels is equivalent to determining whether the orthogonal complement of a given matrix space contains nonzero positive semidefinite matrices.Our characterization immediately implies a necessary condition to decide the parallel distinguishability.We further prove that our condition is also sufficient for two large families of quantum channels, which leads to an alternating proof for the parallel distinguishability of vi Abstract unitary operations [Acín, Physical Review Letters, 2001].We also present an illustrative example showing our necessary condition cannot determine the parallel distinguishability.• We systematically study the tripartite-to-bipartite entanglement transformations by stochastic local operations and classical communication (SLOCC).Such a problem is equivalent to computing the maximal rank of a matrix space [Chitambar, Duan and Shi, Physical Review A, 2010].We analyze the SLOCC convertibility in both the finite-copy and asymptotic regimes.In particular, we derive explicit formulas which compute asymptotic entanglement transformation rates for two families of tripartite states by resorting to certain results of the structure of matrix spaces, including the study of matrix semi-invariants.Significantly, we show that the problem of deciding the asymptotic SLOCC convertibility of tripartite pure states to the bipartite maximally entangled states and the non-commutative symbolic determinant identity testing problem is algorithmically equivalent, which builds a new connection between problems in algebraic complexity and problems in asymptotic SLOCC entanglement transformations.• We devise algorithms which test isometry between alternating matrix spaces over finite field.Algorithms for such a problem in time polynomial in the underlying vector space size resolves the believed bottleneck case of the group isomorphism problem, i.e. testing isomorphism of p-groups of class 2 and exponent p in time polynomial in the group order.Our approach is to view it as a linear algebraic analog of the graph isomorphism problem.We devise an average-case efficient algorithm for the alternating matrix space isometry problem over a key range of parameters.in a random model of alternating matrix spaces in vein of the Erdős-Rényi model of random graphs.To devise our algorithm, we developed linear algebraic individualization and refinement techniques, which are crucial in the first average-case efficient algorithm for graph isomorphism, devised by Babai, Erdős, and Selkow in the 1970s [Babai, Erdős and Selkow, SIAM Journal on Computing, 1980].We also adapt Luks' dynamic programming technique for graph isomorphism [Luks, STOC, 1999] to slightly improve the worst-case time complexity of the alternating matrix space isometry problem.Very little of the work in this thesis would have been possible without the support of my supervisors, collaborators, colleagues, friends and family.First and foremost, I would like to thank my supervisor, Runyao Duan.Without his guidance and insight, I would not have complete my PhD study.I am greatly indebted to him for leading me into the quantum world.Dating back to 2013 in Wuhan University, when I was still a third-year undergraduate student, I was so inspired by his talk about quantum computation.He encouraged me to investigate the parallel distinguishability of quantum channels, which becomes the departure point of my research career.Furthermore, I am grateful for Runyao's spiritual support for my life.He is not only my academic supervisor but also a spiritual mentor, sharing his experience and scope in both research and life.Thanks to my co-supervisor, Youming Qiao, my research interests have been developed and extended.I would like to thank him for his inspirational discussions and conversations from which I really benefit a lot.I have learned about many interesting topics from him, especially for introducing me to the beauty of computational complexity theory.

Related papers

Distinguishability of Quantum States by Positive Operator-Valued Measures With Positive Partial Transpose

Nengkun Yu, Runyao Duan, Mingsheng Ying

We study the distinguishability of bipartite quantum states by positive operator-valued measures with positive partial transpose (PPT POVMs). The contributions of this paper include: 1) we give a negative answer to an open problem of showing a limitation of a previous known method for detecting nondistinguishability; 2) we show that a maximally entangled state and its orthogonal complement, no matter how many copies are supplied, cannot be distinguished by the PPT POVMs, even unambiguously. This result is much stronger than the previous known ones; and 3) we study the entanglement cost of distinguishing quantum states. It is proved that √{2/3}|00〉+√{1/3}|11〉 is sufficient and necessary for distinguishing three Bell states by the PPT POVMs. An upper bound of entanglement cost of distinguishing a d ⊗ d pure state and its orthogonal complement is obtained for separable operations. Based on this bound, we are able to construct two orthogonal quantum states, which cannot be distinguished unambiguously by separable POVMs, but finite copies would make them perfectly distinguishable by local operations and classical communication. We further observe that a two-qubit maximally entangled state is always enough for distinguishing a d ⊗ d pure state and its orthogonal complement by the PPT POVMs, no matter the value of d. In sharp contrast, an entangled state with Schmidt number at least d is always needed for distinguishing such two states by separable POVMs. As an application, we show that the entanglement cost of distinguishing a d ⊗ d maximally entangled state and its orthogonal complement must be a maximally entangled state for d=2, which implies that teleportation is optimal, and in general, it could be chosen as O(logd/d).

arXiv:1209.4222•IEEE Transactions on Information Theory•Feb 24, 2014•71 citations

Indistinguishability of bipartite states by positive-partial-transpose operations in the many-copy scenario

Yinan Li, Xin Wang, Runyao Duan

A bipartite subspace $S$ is called strongly positive-partial-transpose (PPT) unextendible if for every positive integer $k$, there is no PPT operator supporting on the orthogonal complement of ${S}^{\ensuremath{\bigotimes}k}$. We show that a subspace is strongly PPT unextendible if it contains a PPT-definite operator (a positive semidefinite operator whose partial transpose is positive definite). Based on these, we are able to propose a simple criterion for verifying whether a set of bipartite orthogonal quantum states is indistinguishable by PPT operations in the many-copy scenario. Utilizing this criterion, we further point out that any entangled pure state and its orthogonal complement cannot be distinguished by PPT operations in the many-copy scenario. On the other hand, we investigate that the minimum dimension of strongly PPT-unextendible subspaces in an $m\ensuremath{\bigotimes}n$ system is $m+n\ensuremath{-}1$, which involves a generalization of the result that non-positive-partial-transpose subspaces can be as large as any entangled subspace [N. Johnston, Phys. Rev. A 87, 064302 (2013)].

arXiv:1702.00231•Physical Review A•May 30, 2017•20 citations

Distinguishing Maximally Entangled States by PPT Operations and Entanglement Catalysis Discrimination

Nengkun Yu, Runyao Duan, Mingsheng Ying

In order to better understand the class of quantum operations that preserve the positivity of partial transpose (PPT operations) and its relation to the widely used class of local operations and classical communication (LOCC), we study the problem of distinguishing orthogonal maximally entangled states (MES) by PPT operations. Firstly, we outline a rather simple proof to show that the number of $d\otimes d$ PPT distinguishable MES is at most $d$, which slightly generalizes existing results on this problem. Secondly, we construct 4 MES in $4\otimes 4$ state space that cannot be distinguished by PPT operations. Before our work, it was unknown whether there exists $d$ MES in $d\otimes d$ state space that are locally indistinguishable. This example leads us to a novel phenomenon of Entanglement Catalysis Discrimination. Moreover, we find there exists a set of locally indistinguishable states $K$ such that $K^{\otimes m}$ is locally distinguishable for some finite $m$. As an interesting application, we exhibit a quantum channel with one sender and two receivers, whose one-shot zero-error local capacity is not optimal, but multi-use would enhance the capacity to achieve the full output dimension even without entangled input. Finally, we consider the entanglement cost of distinguishing three Bell states and a $2\otimes 2$ entangled basis. In the former case a bipartite pure entangled state with the largest Schmidt coefficient at most 2/3 is necessary and sufficient, while in the latter case an additional Bell state, or one ebit, should be supplied.

•Jul 16, 2011•0 citations

Asymptotic Indistinguishability of Bipartite Quantum States by Operations Completely Preserving Positivity of Partial Transpose

Yinan Li, Xin Wang, Runyao Duan

A bipartite subspace $S$ is called strongly positive-partial-transpose-unextendible (PPT-unextendible) if for every positive integer $k$, there is no PPT state supporting on the orthogonal complement of $S^{\otimes k}$. We show that a subspace is strongly PPT-unextendible if it contains a PPT-definite operator (a positive semidefinite operator whose partial transpose is positive definite). Applying this result, we demonstrate a simple criterion for verifying whether a set of bipartite quantum states is asymptotically indistinguishable by operations completely preserving positivity of partial transpose. This criterion is based on the observation that if the support of some bipartite state is strongly PPT-unextendible, then any set of bipartite quantum states which contains this state cannot be asymptotically distinguished by PPT operations. Utilizing this criterion, we further show that any entangled pure state and its orthogonal complement cannot be distinguished asymptotically by PPT operations. Meanwhile, we also investigate that the minimum dimension of strongly PPT-unextendible subspaces in a $m\otimes n$ system is $m+n-1$, which involves an extension of the result that non-positive-partial-transpose (NPT) subspaces can be as large as any entangled subspace [N. Johnston, Phys. Rev. A 87: 064302 (2013)].

•Feb 1, 2017•1 citation

From symmetric functions to qubits.

Jean-Gabriel Luque, Jean‐Yves Thibon

1. For mathematical point of view, Quantum Information Theory deals with finite dimensional Hilbert spaces, the state spaces of finite k-bipartite systems. In the case of pure k-bipartite systems, this space has the special form 2. H=V1 ⊗ ... ⊗ Vk, 3. where Vi denotes a finite dimensional state space of the ith particle of the system (most of the time, one assumes that it is a qubit, i.e. dim Vi = 2). The interesting non-classical behavior already occurs for two-qubit systems, for the so-called entangled states: the states which cannot be written in the form v1 ⊗ v2. There is no general agreement on the definition of entanglement for system with more than two parts. Klyachko has proposed to regard as entangled the states which are semi-stable for the action of the SLOCC group (G=SL(V1) × ... × SL(Vk)) in the sense of geometric invariant theory. Geometric invariant theory provides 4. methods for characterizing such states without explicitly computing the invariants. In order to test the significance of this property, we have explicitly computed the invariants in the simplest cases. 5. The non-locality properties of an entangled states does not change under unitary operations acting independently on each of its subsystem. The idea to construct entanglement measure by means of unitary invariant have been explored for example by Grassl et al. (1998), Schlienz and Mahler (1996). We have proved in 2006, that such invariants can be deduced from SLOCC-covariants. The knowledge of all the covariants and hence, the classification of the SLOCC orbits seems to be relevant in this context. However, except for simplest systems there are far too many orbits and the complete classification is out of reach. 6. 7. The aim of the series of four lectures given by Jean-Gabriel Luque and Jean-Yves Thibon is to explain a subproblem: how to compute the Hilbert series of the algebraic invariants for the pure k-qubit systems. 8. 9. In the two first lectures, Jean-Gabriel Luque will give a brief account on the symmetric functions and the characters of the symmetric groups. The first two talks will be meant for an audience of beginner in the area of symmetric functions. In the 10. two remaining lectures, Jean-Yves Thibon will explore the links between symmetric functions and Kronecker product (Lecture 3) in order to explain how to compute the Hilbert series (Lecture 4).

•Nov 23, 2009•0 citations

Parallel quantum channel discrimination and numerical ranges in tensor product subspaces

Adam Bílek, Paulina Lewandowska, Ryszard Kukulski

Quantum channel discrimination plays a crucial role in quantum information theory. Of particular interest is the case in which the channels can be discriminated perfectly. In this work, we focus on the perfect quantum channel discrimination task in a parallel scheme. We develop an SDP formulation combined with a bisection procedure to compute a quantum state for perfect discrimination in time linear in the number of copies. In addition, we obtain the minimal number of copies of quantum channels to achieve perfect discrimination. Thanks to that, we settle in the affirmative Conjecture 1 of Duan, Guo, Li and Li [arXiv:1605.02294, IEEE ISIT 2016], which characterizes the number of parallel uses needed to discriminate perfectly a distinguished family of operator subspaces. All our results are obtained using the notion and basic properties of the numerical range. In particular, the key fact that we prove and use is that the minimal angle of the numerical range of a tensor product of matrix subspaces equals the sum of the minimal angles of the numerical ranges of the individual subspaces.

quant-pharXiv:2609.20781•Sep 18, 2026•0 citations
This thesis explores the applications of matrix spaces in quantum information and computational complexity, specifically in the areas of quantum state/channel discrimination, entanglement transformation and isomorphism testing.We achieve the following contributions:• We derive a necessary condition which determines whether a set of orthogonal bipartite states can be distinguished by positive-partial-transpose (PPT) operations, in the many-copy scenario.We reduce the discrimination task to the following problem:Decide whether there exist a nonzero bipartite matrix with positive partial-transpose, such that all its eigenvectors with nonzero eigenvalues is orthogonal to a given bipartite vector space.As applications, we reprove and extend a variety of existing results, including the local indistinguishability of the bipartite maximally entangled state and its orthogonal complement [Yu, Duan and Ying, IEEE transaction on Information Theory, 2014] and the maximum dimension of non-positive-partialtranspose subspaces [Johnston, Physical Review A, 2013].• We show that determining the parallel distinguishability of quantum channels is equivalent to determining whether the orthogonal complement of a given matrix space contains nonzero positive semidefinite matrices.Our characterization immediately implies a necessary condition to decide the parallel distinguishability.We further prove that our condition is also sufficient for two large families of quantum channels, which leads to an alternating proof for the parallel distinguishability of vi Abstract unitary operations [Acín, Physical Review Letters, 2001].We also present an illustrative example showing our necessary condition cannot determine the parallel distinguishability.• We systematically study the tripartite-to-bipartite entanglement transformations by stochastic local operations and classical communication (SLOCC).Such a problem is equivalent to computing the maximal rank of a matrix space [Chitambar, Duan and Shi, Physical Review A, 2010].We analyze the SLOCC convertibility in both the finite-copy and asymptotic regimes.In particular, we derive explicit formulas which compute asymptotic entanglement transformation rates for two families of tripartite states by resorting to certain results of the structure of matrix spaces, including the study of matrix semi-invariants.Significantly, we show that the problem of deciding the asymptotic SLOCC convertibility of tripartite pure states to the bipartite maximally entangled states and the non-commutative symbolic determinant identity testing problem is algorithmically equivalent, which builds a new connection between problems in algebraic complexity and problems in asymptotic SLOCC entanglement transformations.• We devise algorithms which test isometry between alternating matrix spaces over finite field.Algorithms for such a problem in time polynomial in the underlying vector space size resolves the believed bottleneck case of the group isomorphism problem, i.e. testing isomorphism of p-groups of class 2 and exponent p in time polynomial in the group order.Our approach is to view it as a linear algebraic analog of the graph isomorphism problem.We devise an average-case efficient algorithm for the alternating matrix space isometry problem over a key range of parameters.in a random model of alternating matrix spaces in vein of the Erdős-Rényi model of random graphs.To devise our algorithm, we developed linear algebraic individualization and refinement techniques, which are crucial in the first average-case efficient algorithm for graph isomorphism, devised by Babai, Erdős, and Selkow in the 1970s [Babai, Erdős and Selkow, SIAM Journal on Computing, 1980].We also adapt Luks' dynamic programming technique for graph isomorphism [Luks, STOC, 1999] to slightly improve the worst-case time complexity of the alternating matrix space isometry problem.Very little of the work in this thesis would have been possible without the support of my supervisors, collaborators, colleagues, friends and family.First and foremost, I would like to thank my supervisor, Runyao Duan.Without his guidance and insight, I would not have complete my PhD study.I am greatly indebted to him for leading me into the quantum world.Dating back to 2013 in Wuhan University, when I was still a third-year undergraduate student, I was so inspired by his talk about quantum computation.He encouraged me to investigate the parallel distinguishability of quantum channels, which becomes the departure point of my research career.Furthermore, I am grateful for Runyao's spiritual support for my life.He is not only my academic supervisor but also a spiritual mentor, sharing his experience and scope in both research and life.Thanks to my co-supervisor, Youming Qiao, my research interests have been developed and extended.I would like to thank him for his inspirational discussions and conversations from which I really benefit a lot.I have learned about many interesting topics from him, especially for introducing me to the beauty of computational complexity theory.
We study the distinguishability of bipartite quantum states by positive operator-valued measures with positive partial transpose (PPT POVMs). The contributions of this paper include: 1) we give a negative answer to an open problem of showing a limitation of a previous known method for detecting nondistinguishability; 2) we show that a maximally entangled state and its orthogonal complement, no matter how many copies are supplied, cannot be distinguished by the PPT POVMs, even unambiguously. This result is much stronger than the previous known ones; and 3) we study the entanglement cost of distinguishing quantum states. It is proved that √{2/3}|00〉+√{1/3}|11〉 is sufficient and necessary for distinguishing three Bell states by the PPT POVMs. An upper bound of entanglement cost of distinguishing a d ⊗ d pure state and its orthogonal complement is obtained for separable operations. Based on this bound, we are able to construct two orthogonal quantum states, which cannot be distinguished unambiguously by separable POVMs, but finite copies would make them perfectly distinguishable by local operations and classical communication. We further observe that a two-qubit maximally entangled state is always enough for distinguishing a d ⊗ d pure state and its orthogonal complement by the PPT POVMs, no matter the value of d. In sharp contrast, an entangled state with Schmidt number at least d is always needed for distinguishing such two states by separable POVMs. As an application, we show that the entanglement cost of distinguishing a d ⊗ d maximally entangled state and its orthogonal complement must be a maximally entangled state for d=2, which implies that teleportation is optimal, and in general, it could be chosen as O(logd/d).
A bipartite subspace SSS is called strongly positive-partial-transpose (PPT) unextendible if for every positive integer kkk, there is no PPT operator supporting on the orthogonal complement of ${S}^{\ensuremath{\bigotimes}k}$. We show that a subspace is strongly PPT unextendible if it contains a PPT-definite operator (a positive semidefinite operator whose partial transpose is positive definite). Based on these, we are able to propose a simple criterion for verifying whether a set of bipartite orthogonal quantum states is indistinguishable by PPT operations in the many-copy scenario. Utilizing this criterion, we further point out that any entangled pure state and its orthogonal complement cannot be distinguished by PPT operations in the many-copy scenario. On the other hand, we investigate that the minimum dimension of strongly PPT-unextendible subspaces in an $m\ensuremath{\bigotimes}n$ system is $m+n\ensuremath{-}1$, which involves a generalization of the result that non-positive-partial-transpose subspaces can be as large as any entangled subspace [N. Johnston, Phys. Rev. A 87, 064302 (2013)].
In order to better understand the class of quantum operations that preserve the positivity of partial transpose (PPT operations) and its relation to the widely used class of local operations and classical communication (LOCC), we study the problem of distinguishing orthogonal maximally entangled states (MES) by PPT operations. Firstly, we outline a rather simple proof to show that the number of d⊗dd\otimes dd⊗d PPT distinguishable MES is at most ddd, which slightly generalizes existing results on this problem. Secondly, we construct 4 MES in 4⊗44\otimes 44⊗4 state space that cannot be distinguished by PPT operations. Before our work, it was unknown whether there exists ddd MES in d⊗dd\otimes dd⊗d state space that are locally indistinguishable. This example leads us to a novel phenomenon of Entanglement Catalysis Discrimination. Moreover, we find there exists a set of locally indistinguishable states KKK such that K⊗mK^{\otimes m}K⊗m is locally distinguishable for some finite mmm. As an interesting application, we exhibit a quantum channel with one sender and two receivers, whose one-shot zero-error local capacity is not optimal, but multi-use would enhance the capacity to achieve the full output dimension even without entangled input. Finally, we consider the entanglement cost of distinguishing three Bell states and a 2⊗22\otimes 22⊗2 entangled basis. In the former case a bipartite pure entangled state with the largest Schmidt coefficient at most 2/3 is necessary and sufficient, while in the latter case an additional Bell state, or one ebit, should be supplied.
A bipartite subspace SSS is called strongly positive-partial-transpose-unextendible (PPT-unextendible) if for every positive integer kkk, there is no PPT state supporting on the orthogonal complement of S⊗kS^{\otimes k}S⊗k. We show that a subspace is strongly PPT-unextendible if it contains a PPT-definite operator (a positive semidefinite operator whose partial transpose is positive definite). Applying this result, we demonstrate a simple criterion for verifying whether a set of bipartite quantum states is asymptotically indistinguishable by operations completely preserving positivity of partial transpose. This criterion is based on the observation that if the support of some bipartite state is strongly PPT-unextendible, then any set of bipartite quantum states which contains this state cannot be asymptotically distinguished by PPT operations. Utilizing this criterion, we further show that any entangled pure state and its orthogonal complement cannot be distinguished asymptotically by PPT operations. Meanwhile, we also investigate that the minimum dimension of strongly PPT-unextendible subspaces in a m⊗nm\otimes nm⊗n system is m+n−1m+n-1m+n−1, which involves an extension of the result that non-positive-partial-transpose (NPT) subspaces can be as large as any entangled subspace [N. Johnston, Phys. Rev. A 87: 064302 (2013)].
1. For mathematical point of view, Quantum Information Theory deals with finite dimensional Hilbert spaces, the state spaces of finite k-bipartite systems. In the case of pure k-bipartite systems, this space has the special form 2. H=V1 ⊗ ... ⊗ Vk, 3. where Vi denotes a finite dimensional state space of the ith particle of the system (most of the time, one assumes that it is a qubit, i.e. dim Vi = 2). The interesting non-classical behavior already occurs for two-qubit systems, for the so-called entangled states: the states which cannot be written in the form v1 ⊗ v2. There is no general agreement on the definition of entanglement for system with more than two parts. Klyachko has proposed to regard as entangled the states which are semi-stable for the action of the SLOCC group (G=SL(V1) × ... × SL(Vk)) in the sense of geometric invariant theory. Geometric invariant theory provides 4. methods for characterizing such states without explicitly computing the invariants. In order to test the significance of this property, we have explicitly computed the invariants in the simplest cases. 5. The non-locality properties of an entangled states does not change under unitary operations acting independently on each of its subsystem. The idea to construct entanglement measure by means of unitary invariant have been explored for example by Grassl et al. (1998), Schlienz and Mahler (1996). We have proved in 2006, that such invariants can be deduced from SLOCC-covariants. The knowledge of all the covariants and hence, the classification of the SLOCC orbits seems to be relevant in this context. However, except for simplest systems there are far too many orbits and the complete classification is out of reach. 6. 7. The aim of the series of four lectures given by Jean-Gabriel Luque and Jean-Yves Thibon is to explain a subproblem: how to compute the Hilbert series of the algebraic invariants for the pure k-qubit systems. 8. 9. In the two first lectures, Jean-Gabriel Luque will give a brief account on the symmetric functions and the characters of the symmetric groups. The first two talks will be meant for an audience of beginner in the area of symmetric functions. In the 10. two remaining lectures, Jean-Yves Thibon will explore the links between symmetric functions and Kronecker product (Lecture 3) in order to explain how to compute the Hilbert series (Lecture 4).
Quantum channel discrimination plays a crucial role in quantum information theory. Of particular interest is the case in which the channels can be discriminated perfectly. In this work, we focus on the perfect quantum channel discrimination task in a parallel scheme. We develop an SDP formulation combined with a bisection procedure to compute a quantum state for perfect discrimination in time linear in the number of copies. In addition, we obtain the minimal number of copies of quantum channels to achieve perfect discrimination. Thanks to that, we settle in the affirmative Conjecture 1 of Duan, Guo, Li and Li [arXiv:1605.02294, IEEE ISIT 2016], which characterizes the number of parallel uses needed to discriminate perfectly a distinguished family of operator subspaces. All our results are obtained using the notion and basic properties of the numerical range. In particular, the key fact that we prove and use is that the minimal angle of the numerical range of a tensor product of matrix subspaces equals the sum of the minimal angles of the numerical ranges of the individual subspaces.