Computational Complexity Measures of Multipartite Quantum Entanglement

Abstract

We shed new light on entanglement measures in multipartite quantum systems by taking a computational-complexity approach toward quantifying quantum entanglement with two familiar notions--approximability and distinguishability. Built upon the formal treatment of partial separability, we measure the complexity of an entangled quantum state by determining (i) how hard to approximate it from a fixed classical state and (ii) how hard to distinguish it from all partially separable states. We further consider the Kolmogorovian-style descriptive complexity of approximation and distinction of partial entanglement.

To appear in the Proceedings of the 14th Annual International Conference on Algorithms and Computation, December 2003