dorsal/arxiv
View SchemaComputational complexity of the quantum separability problem
| Authors | Lawrence M. Ioannou |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0603199 |
| URL | https://arxiv.org/abs/quant-ph/0603199 |
| Journal | Quantum Information and Computation, Vol. 7, No. 4 (2007) 335-370 |
Abstract
Ever since entanglement was identified as a computational and cryptographic resource, researchers have sought efficient ways to tell whether a given density matrix represents an unentangled, or separable, state. This paper gives the first systematic and comprehensive treatment of this (bipartite) quantum separability problem, focusing on its deterministic (as opposed to randomized) computational complexity. First, I review the one-sided tests for separability, paying particular attention to the semidefinite programming methods. Then, I discuss various ways of formulating the quantum separability problem, from exact to approximate formulations, the latter of which are the paper's main focus. I then give a thorough treatment of the problem's relationship with the complexity classes NP, NP-complete, and co-NP. I also discuss extensions of Gurvits' NP-hardness result to strong NP-hardness of certain related problems. A major open question is whether the NP-contained formulation (QSEP) of the quantum separability problem is Karp-NP-complete; QSEP may be the first natural example of a problem that is Turing-NP-complete but not Karp-NP-complete. Finally, I survey all the proposed (deterministic) algorithms for the quantum separability problem, including the bounded search for symmetric extensions (via semidefinite programming), based on the recent quantum de Finetti theorem; and the entanglement-witness search (via interior-point algorithms and global optimization). These two algorithms have the lowest complexity, with the latter being the best under advice of asymptotically optimal point-coverings of the sphere.
{
"annotation_id": "dec683bf-d30d-4298-a1eb-4d6b114cc2a0",
"date_created": "2026-03-02T18:02:27.225000Z",
"date_modified": "2026-03-02T18:02:27.225000Z",
"file_hash": "9ad55cd9ba5de78e5d46f1d089a6d81703a43f5115ee9619cd2351355ecb0513",
"private": false,
"record": {
"abstract": "Ever since entanglement was identified as a computational and cryptographic\nresource, researchers have sought efficient ways to tell whether a given\ndensity matrix represents an unentangled, or separable, state. This paper gives\nthe first systematic and comprehensive treatment of this (bipartite) quantum\nseparability problem, focusing on its deterministic (as opposed to randomized)\ncomputational complexity. First, I review the one-sided tests for separability,\npaying particular attention to the semidefinite programming methods. Then, I\ndiscuss various ways of formulating the quantum separability problem, from\nexact to approximate formulations, the latter of which are the paper\u0027s main\nfocus. I then give a thorough treatment of the problem\u0027s relationship with the\ncomplexity classes NP, NP-complete, and co-NP. I also discuss extensions of\nGurvits\u0027 NP-hardness result to strong NP-hardness of certain related problems.\nA major open question is whether the NP-contained formulation (QSEP) of the\nquantum separability problem is Karp-NP-complete; QSEP may be the first natural\nexample of a problem that is Turing-NP-complete but not Karp-NP-complete.\nFinally, I survey all the proposed (deterministic) algorithms for the quantum\nseparability problem, including the bounded search for symmetric extensions\n(via semidefinite programming), based on the recent quantum de Finetti theorem;\nand the entanglement-witness search (via interior-point algorithms and global\noptimization). These two algorithms have the lowest complexity, with the latter\nbeing the best under advice of asymptotically optimal point-coverings of the\nsphere.",
"arxiv_id": "quant-ph/0603199",
"authors": [
"Lawrence M. Ioannou"
],
"categories": [
"quant-ph",
"cs.CC"
],
"journal_ref": "Quantum Information and Computation, Vol. 7, No. 4 (2007) 335-370",
"title": "Computational complexity of the quantum separability problem",
"url": "https://arxiv.org/abs/quant-ph/0603199"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "c180e4da-c1e4-47d7-a9c5-cb059411ed7e",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}