Hannover 2013 – scientific programme

Parts | Days | Selection | Search | Updates | Downloads | Help

Q: Fachverband Quantenoptik und Photonik

Q 33: Quantum information: Concepts and methods II

Q 33.1: Talk

Tuesday, March 19, 2013, 14:00–14:15, E 214

Witnessing genuine entanglement from local information: possible, but hard — Alexandre Lopes, •Panagiotis Papanastasiou, and David Gross — University of Freiburg

It has recently been observed [M. Walter et al, arXiv:1208.0365] that in some instances, strong statements about multi-particle entanglement can be deduced from single-site information alone. The conceptually simplest case concerns the presence of genuine entanglement: It has been shown that certain local density matrices are compatible only with a global state that is not bi-separable (assuming it is close to pure). Here, we analyze the computational complexity of this task. We show that, while there are many efficiently solvable instances, the general problem is NP-hard. This leaves us with the situation that few, easily obtainable physical measurements may be sufficient to witness many-body entanglement – but that the classical post-processing is intractable. To the best of our knowledge, this is the first natural instance of a pure state entanglement problem that has been proven to be hard.