Computational complexity of the quantum separability problem
(pp335-370)
Lawrence
M. Ioannou
doi:
https://doi.org/10.26421/QIC7.4-5
Abstracts:
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 \emph{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 NP, NP-completeness, 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 \cite{DPS02,DPS04,qphCKMR06}; and
the entanglement-witness search (via interior-point algorithms and
global optimization) \cite{ITCE04,IT06}. These two algorithms have the
lowest complexity, with the latter being the best under advice of
asymptotically optimal point-coverings of the sphere.
Key words:
saparability, computational complexity |