Quantum Entanglement and Tensor Rank
Professor, Electrical Engineering and Computer
of Michigan, Ann Arbor
Dec 18, 2008 (Thursday)
2:00pm - 3:00pm
Rm. 121, Ho Sin Hang Engineering Building, CUHK
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
Joint works with Eric Chitambar and Runyao Duan.
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.