All Abstracts | Poster Abstracts | Talk Abstracts | Tutorial Abstracts

Strong NP-Hardness of the Quantum Separability Problem

Sevag Gharibian, Institute for Quantum Computing, University of Waterloo

(Session 8 : Saturday from 4:00-4:30)

Abstract. Quantum entanglement is generally believed to be a valuable resource in the theory of quantum computing. The problem of determining whether an arbitrary quantum state is entangled, dubbed the Quantum Separability problem, has hence received much attention over the past decade. In 2003, Gurvits showed that the Quantum Separability problem is NP-hard, with one caveat - one must allow instances in which the input quantum state is exponentially close (with respect to dimension, and in Euclidean distance) to the border of the set of separable (equivalently, unentangled) quantum states. This leaves open the question - is the Quantum Separability problem "weakly" NP-hard, i.e. can it be solved efficiently if one is promised that the input state is at least an inverse polynomial distance away from the border of the separable set? In this talk, we answer this question negatively by showing that the Quantum Separability problem is in fact "strongly" NP-hard. This is accomplished by combining previous work by Gurvits and a recent non-ellipsoidal reduction of Liu to show that the Weak Membership problem over the set of separable quantum states is strongly NP-hard. Based on this result, we observe an immediate lower bound on the maximum distance possible between a bound entangled state and the separable set (assuming P != NP). Time permitting, we also demonstrate that determining whether a completely positive trace-preserving linear map (i.e. a quantum channel) is entanglement-breaking is NP-hard.