Strong NP-hardness of the quantum separability problem

S. Gharibian, Quantum Information & Computation 10 (2010) 343–360.

Journal Article | Published | English
Department
Abstract
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.
Publishing Year
Journal Title
Quantum Information & Computation
Volume
10
Issue
3{\&}4
Page
343-360
LibreCat-ID

Cite this

Gharibian S. Strong NP-hardness of the quantum separability problem. Quantum Information & Computation. 2010;10(3{\&}4):343-360.
Gharibian, S. (2010). Strong NP-hardness of the quantum separability problem. Quantum Information & Computation, 10(3{\&}4), 343–360.
@article{Gharibian_2010, title={Strong NP-hardness of the quantum separability problem}, volume={10}, number={3{\&}4}, journal={Quantum Information & Computation}, author={Gharibian, Sevag}, year={2010}, pages={343–360} }
Gharibian, Sevag. “Strong NP-Hardness of the Quantum Separability Problem.” Quantum Information & Computation 10, no. 3{\&}4 (2010): 343–60.
S. Gharibian, “Strong NP-hardness of the quantum separability problem,” Quantum Information & Computation, vol. 10, no. 3{\&}4, pp. 343–360, 2010.
Gharibian, Sevag. “Strong NP-Hardness of the Quantum Separability Problem.” Quantum Information & Computation, vol. 10, no. 3{\&}4, 2010, pp. 343–60.

Link(s) to Main File(s)
Access Level
Restricted Closed Access

Export

Marked Publications

Open Data LibreCat

Sources

arXiv 0810.4507

Search this title in

Google Scholar