For Hilbert spaces X,Y, the set of maximally entangled states, MES_{X,Y}, is a set of rank-1 positive semidefinite operators over the space X [o times] Y. In this thesis, we consider the problem of classifying the linear maps that take maximally entangled states to maximally entangled states in the case of finite dimensional spaces X,Y. After classifying these linear maps in the case where dim X divides dim Y, we consider possible avenues of extending these results and consider the set WMES_{X,Y}, which is a set of low-rank positive semidefinite operators over X [o times] Y. We then discuss the "fractional minimal rank", a fractional parameter assigned to partial matrices. We compute the fractional minimal rank for partial matrices whose pattern of knowns is a "minimal cycle", which is the family of the smallest cases for which it is known that the ''minimal rank'' and ''triangular minimal ranks'' differ in general.
For Hilbert spaces X,Y, the set of maximally entangled states, MES_{X,Y}, is a set of rank-1 positive semidefinite operators over the space X [o times] Y. In this thesis, we consider the problem of classifying the linear maps that take maximally entangled states to maximally entangled states in the case of finite dimensional spaces X,Y. After classifying these linear maps in the case where dim X divides dim Y, we consider possible avenues of extending these results and consider the set WMES_{X,Y}, which is a set of low-rank positive semidefinite operators over X [o times] Y. We then discuss the "fractional minimal rank", a fractional parameter assigned to partial matrices. We compute the fractional minimal rank for partial matrices whose pattern of knowns is a "minimal cycle", which is the family of the smallest cases for which it is known that the ''minimal rank'' and ''triangular minimal ranks'' differ in general.
For Hilbert spaces X , Y, the set of maximally entangled states, MES X ,Y , is a set of rank-1 positive semidefinite operators over the space X ⊗ Y.In this thesis, we consider the problem of classifying the linear maps that take maximally entangled states to maximally entangled states in the case of finite dimensional spaces X , Y.After classifying these linear maps in the case where dim X divides dim Y, we consider possible avenues of extending these results and consider the set WMES X ,Y , which is a set of low-rank positive semidefinite operators over X ⊗ Y.We then discuss the "fractional minimal rank", a fractional parameter assigned to partial matrices.We compute the fractional minimal rank for partial matrices whose pattern of knowns is a "minimal cycle", which is the family of the smallest cases for which it is known that the "minimal rank" and "triangular minimal ranks" differ in general.
We present solutions to a set of problems that arise in quantum entanglement theory, whose common trait is the use of algebraic methods. The backbone of the thesis consists of two general theorems, pertaining to specific convex sets of quantum maps. They are complemented by solutions of many more specific problems of rather technical character. These problems concerned questions such as the higher rank numerical ranges, the lengths of separable states, the solutions of compression equations, the completely entangled subspaces, and maximally entangled states. The solutions were obtained partly by hand, and partly by using the Groebner basis toolset available in computer algebra systems. The main results, which are those of general nature, consist of a characterization of mapping cones, which is a full analogue of the positive maps criterion for separability, as well as of a full characterization of positive-partial-transpose entangled states of minimum rank. The thesis also contains an introduction to the theory of quantum entanglement and to basic algebraic geometry, whose methods have been used
We present a simple semidefinite program whose optimal value is equal to the maximum probability of perfectly distinguishing orthogonal maximally entangled states using any PPT measurement (a measurement whose operators are positive under partial transpose). When the states to be distinguished are given by the tensor product of Bell states, the semidefinite program simplifies to a linear program. In Phys. Rev. Lett. 109, 020506 (2012), Yu, Duan, and Ying exhibit a set of four maximally entangled states in ${\mathbb{C}}^{4}\ensuremath{\bigotimes}{\mathbb{C}}^{4}$, which is distinguishable by any PPT measurement only with probability strictly less than 1. Using semidefinite programming, we show a tight bound of 7/8 on this probability (3/4 for the case of unambiguous PPT measurements). We generalize this result by demonstrating a simple construction of a set of k states in ${\mathbb{C}}^{k}\ensuremath{\bigotimes}{\mathbb{C}}^{k}$ with the same property, for any k that is a power of 2. By running numerical experiments, we show the local indistinguishability of certain sets of generalized Bell states in ${\mathbb{C}}^{5}\ensuremath{\bigotimes}{\mathbb{C}}^{5}$ and ${\mathbb{C}}^{6}\ensuremath{\bigotimes}{\mathbb{C}}^{6}$ previously considered in the literature.
Optimization is a fundamental area in mathematics and computer science, with many real-world applications. In this thesis we study the efficiency with which we can solve certain optimization problems from two different perspectives. Firstly, we study it from the perspective of matrix factorization ranks, which comes with connections to quantum information theory. Secondly, we study it from the perspective of quantum computing. This thesis is accordingly divided into two parts, where we take these perspectives. In the first part of this thesis we study several matrix factorization ranks and their connections to quantum information theory. In Chapter 5, we first give a unified approach to lower bounding matrix factorization ranks, using polynomial optimization techniques. In Chapter 6, we exploit the connection between one particular factorization rank, the completely positive semidefinite rank, and quantum correlations to provide an explicit family of matrices with a large completely positive semidefinite factorization rank. In Chapter 8, we use the same connection to study quantum versions of classical graph parameters from the perspective of polynomial optimization (albeit in noncommutative variables). In Chapter 7 we propose and study a new measure for the amount of entanglement needed to realize quantum correlations. We can approximate this new measure using our approach to matrix factorization ranks, i.e., through polynomial optimization in noncommutative variables. In the second part of this thesis we turn our attention to the question: Can we solve optimization problems faster on a quantum computer? First, in Chapter 10, we look at the problem of evaluating a Boolean function. We give a new semidefinite programming characterization of the minimum number of quantum queries to the input that are needed to determine the corresponding function value. In Chapter 11 we revisit the semidefinite programming problem that plays a crucial role in the rest of the thesis; we provide a quantum algorithm for solving semidefinite programs. Finally, in Chapter 12, we study the general problem of solving convex optimization problems in the oracle model. We provide both upper and lower bounds on the efficiency of various reductions in the quantum setting. In particular, we show that quantum computers are more efficient than classical computers for the task of answering separation queries when access to the convex problem is given through membership queries.
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.
Deciding whether a mixed quantum state is separable or entangled is a difficult problem in general. Separable states are positive under partial transposition [they are positive-partial-transpose (PPT) states], but this simple test does not exclude all entangled states. In order to understand the entangled PPT states, having so-called bound entanglement, we want to study the extremal PPT states. An extremal PPT state is either a pure product state, then it is separable, or it is entangled, in which case the state and its partial transpose must still be rather low-rank density matrices, although it is known that the rank must be at least 4. In a previous paper we presented a complete classification of the rank-4 entangled PPT states in dimension $3\ifmmode\times\else\texttimes\fi{}3$, generalizing the construction by Bennett et al. from unextendible sets of orthogonal product vectors. In the present paper we continue our investigations of the low-rank entangled PPT states, mostly in dimension $3\ifmmode\times\else\texttimes\fi{}3$, using a combination of analytical and numerical methods. We use perturbation theory in order to construct rank-5 entangled PPT states close to the known rank-4 states, and in order to compute dimensions and study the geometry of surfaces of low-rank PPT states. We exploit the close connection between low-rank PPT states and product vectors. In particular, we show how to reconstruct a low-rank PPT state from a sufficient number of product vectors in its kernel. It may seem surprising that the number of product vectors needed may be smaller than the dimension of the kernel.