Strong NP-Hardness of the Quantum Separability Problem

Details Strong NP-Hardness of the Quantum Separability Problem Strong NP-Hardness of the Quantum Separability Problem

2008-10-24

arxiv.org/abs/0810.4507v5

Quantum Information and Computation, Vol. 10, No. 3&4, pp. 343-360, 2010

Physics

Quantum Physics

18 pages, 1 figure. v5: Updated version to appear in Quantum Information & Computation. Includes additional details in proof o

Scientific paper

Given the density matrix rho of a bipartite quantum state, the quantum separability problem asks whether rho is entangled or separable. In 2003, Gurvits showed that this problem is NP-hard if rho is located within an inverse exponential (with respect to dimension) distance from the border of the set of separable quantum states. In this paper, we extend this NP-hardness to an inverse polynomial distance from the separable set. The result follows from a simple combination of works by Gurvits, Ioannou, and Liu. We apply our result to show (1) an immediate lower bound on the maximum distance between a bound entangled state and the separable set (assuming P != NP), and (2) NP-hardness for the problem of determining whether a completely positive trace-preserving linear map is entanglement-breaking.

Affiliated with

Also associated with

No associations

Rating

Strong NP-Hardness of the Quantum Separability Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Strong NP-Hardness of the Quantum Separability Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strong NP-Hardness of the Quantum Separability Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-698892