Abstract :

A quantum system consisting of multiple subsystems may be in a so called ``entangled'' state, which is inherently non-classical. Quantum entanglement underlies many counter-intuitive properties of quantum mechanics, as well as their information processing applications. While bipartite entanglement is well understood, much less is known about three- or more partite entanglement. A basic question is that of the classification of different ``types'' of entanglement, according to the feasibility of converting one state to another through protocols that disallow quantum communication.

I will present two results on this question. The first shows that the computational problem of deciding the existence of a probabilistic conversion encodes many classical problems, ranging from NP-complete problems, polynomial identity testing to matrix multiplication. The second shows that a maximum entangled state, i.e. a state that can be converted to any other state in the same space, exists if and only if one subsystem has a dimension no less than that of the other subsystems combined. Our results are obtained using connections with tensor rank, which is the smallest number of tensor product elements that linearly express a tensor, and has been studied extensively in algebraic complexity theory.

Joint works with Eric Chitambar and Runyao Duan.

Biography :

Yaoyun Shi received his undergraduate degree from Beijing University in 1997, and his PhD from Princeton University in 2001, both in computer science. After a year of postdoctoral research at California Institute of Technology, he joined University of Michigan, Ann Arbor, as an assistant professor in 2002, and is now an associate professor. His research interests include the theory of computation and quantum information processing.