Source-linked AI summary
Strong NP-Hardness of the Quantum Separability Problem
Sevag Gharibian
TL;DR
Quantum separability is made well-defined through weak membership because finite-precision encodings can misclassify states near the separable-set boundary. The paper combines prior reductions to establish strong NP-hardness at inverse-polynomial distance and derives applications to bound entanglement and entanglement-breaking maps.
Problem
Finite-precision encodings make exact separability ill-defined near the boundary, motivating weak membership with an allowed error margin.
Method
The paper studies WMEMβ(SM,N), using Gurvits's reduction framework and subsequent reduction results to analyze separability with an inverse-polynomial boundary margin.
Results
WMEMβ(SM,N) is strongly NP-hard for β ≤ 1/poly(M, N), and determining separability of quantum states with a mixed subsystem is NP-hard, implying NP-hardness of EBP.
Takeaways & Limitations
The result gives an immediate lower bound on the maximum distance of bound entangled states from the separable set, assuming P ≠ NP, and establishes NP-hardness for entanglement-breaking testing.
Takeaways & Limitations
Constant-distance NP-hardness remains open, and extending inverse-polynomial hardness to EBP requires a difficult inverse-polynomial bound on the transformed state's distance.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper formalizes quantum separability through weak membership to handle finite-precision boundary ambiguity, then strengthens Gurvits’s NP-hardness result from inverse-exponential to inverse-polynomial error.
- Problem formulation: Finite-precision encoding makes exact separability ill-defined when a state lies on the boundary of the separable set.A small perturbation can move an encoded state outside the set.
- Problem formulation: Weak Membership permits errors within Euclidean distance β of the separable set’s border, making the separability problem well-defined.The separable states are represented as real Bloch vectors so the convex-set formulation applies.
- Prior hardness: Gurvits’s reduction established NP-hardness only for β ≤1/ exp(M, N), because PARTITION is hard under exponentially large numerical parameters.Dynamic programming makes PARTITION efficient when its integer magnitudes are polynomially bounded.
- Main result: The paper’s main theorem states that WMEMβ(SM,N) is strongly NP-hard for β ≤1/ poly(M, N).Strong NP-hardness means hardness persists when numerical parameters are polynomially bounded in input length.
- Proof strategy: The strengthened result combines Gurvits’s and Ioannou’s reductions with Liu’s non-ellipsoidal reduction from Weak Optimization to Weak Membership.The technical contribution is the many-one reduction RSDF ≤m WOPTϵ(SM,N).
- Applications: Applications include a lower bound on bound-entangled states’ distance from separable states and NP-hardness of testing whether a quantum channel is entanglement-breaking.The distance bound is conditional on P ≠ NP.
2 Definitions and Notation
This section defines the source problem CLIQUE, robust semidefinite feasibility, and the weak optimization and membership problems used in the reduction, together with the geometric representation of separable states.
- CLIQUE: CLIQUE asks whether a graph contains a complete subgraph with at least c vertices.The graph is encoded by its adjacency matrix.
- RSDF: RSDF distinguishes whether g(B1, . . . , Bk) is at least ζ + η or at most ζ −η.The function maximizes a sum of squared quadratic forms over unit vectors.
- Geometric notation: S(K, δ) expands a convex set K by Euclidean distance δ, while S(K, −δ) retains points whose δ-neighborhood lies entirely within K.These sets represent an outer extension and an inner core, respectively.
- Weak problems: Weak Optimization asks whether a point in the core achieves a linear threshold, or whether every point in the expanded set remains below another threshold.The two promise cases use c^Ty ≥γ + ϵ and c^Tx ≤γ −ϵ.
- Weak problems: Weak Membership distinguishes points in S(K, −β) from points outside S(K, β).Inputs in the gap between these regions may receive either answer under the promise formulation.
- Separable-state representation: Separable states form a convex hull of pure product states and are represented as real Bloch vectors in dimension M^2N^2−1.The resulting set is compact, well-bounded, and has encoding size at most poly(MN).
3 The Reduction
The reduction maps CLIQUE through RSDF and weak optimization to weak membership over separable states, while preserving polynomial-time computability and inverse-polynomial error parameters. This yields strong NP-hardness for WMEMβ(SM,N), with explicit dimension-dependent bounds and a remaining constant-error gap.
- Reduction chain: The proof composes reductions from CLIQUE to RSDF, from RSDF to WOPTϵ(SM,N), and from weak optimization to WMEMβ(SM,N).The first and last links come from prior work, while the middle link is established using separable-state geometry and Bloch-vector representations.
- Reduction chain: The RSDF-to-WOPTϵ reduction rewrites the RSDF objective as linear optimization Tr(Cρ) over separable density matrices.The matrix objective is normalized into a Bloch-vector objective f(r) := c^Tr, with the separable-state set represented in real Euclidean space.
- Gap preservation: The YES and NO cases of RSDF are transferred to weak optimization by choosing γ between the two objective thresholds and selecting ϵ to preserve the gap.The argument uses convex-geometric approximations of the separable-state set and bounds objective changes with the Cauchy-Schwarz inequality.
- Parameter scaling: The reduction from CLIQUE uses M = N = n(n−1)^2 + 1 and an oracle tolerance β ∈ Ω(n^−73), with a generalized bound β ∈ Ω(M^−16N^−20.5) for M ≥ N.The construction encodes graph adjacency through k = n(n−1)/2 sparse symmetric matrices and obtains polynomial-time solvability of CLIQUE using WMEMβ.
- Scope: The reduction cannot achieve β ∈ Ω(1), so NP-hardness at constant distance remains open and the weak tolerance bound is dominated by the final reduction.The limitation is attributed in particular to the dependence on ϵ in Lemma 4 and the error scaling in Theorem 5.
4 Applications
The paper applies its separability-hardness framework to bound entangled states and to deciding whether quantum channels are entanglement-breaking. The channel result reduces restricted separability testing to a promised maximally mixed subsystem using preprocessing and local filtering, while leaving strong NP-hardness for channels open.
- Bound entangled states: Theorem 1 yields an inverse-polynomial lower bound on the maximum distance between some bound entangled state and the separable set, assuming P != NP.Any efficient separability test must fail to resolve the separable set within distance β ∈Ω(M−16N−20.5) of its border in the general case.
- Entanglement-breaking channels: A quantum channel is entanglement-breaking if applying it to one subsystem produces a separable state for every bipartite input.The paper studies this property through the Jamiołkowski representation, which links channel structure to separability of density operators.
- Entanglement-breaking channels: Separability of states satisfying TrA(ρ) = I/N is equivalent to determining whether the corresponding completely positive trace-preserving map is entanglement-breaking.The equivalence follows because complete positivity corresponds to positivity of J(Φ), while trace preservation corresponds to TrA(J(Φ)) = I/N.
- Entanglement-breaking channels: An efficient reduction maps arbitrary ρ to ρ′ = Υ(Φ(ρ)) with TrA′(ρ′) = I/N while preserving separability across the relevant bipartition.Φ mixes the state with identity and adds a marker ancilla; Υ then applies an invertible-with-nonzero-probability local filter.
- Entanglement-breaking channels: Strong NP-hardness for entanglement-breaking channels remains open because the reduction must lower-bound the transformed state's distance from the boundary in the Jamiołkowski space.The paper specifically leaves open whether inverse-polynomial separation is preserved under the transformation from ρ to Υ(Φ(ρ)).
5 Concluding Comments
The paper establishes strong NP-hardness for weak membership in the separable-state set even with inverse-polynomial error, and applies this result to bound entanglement and entanglement-breaking channels.
- Concluding Comments: WMEMβ(SM,N) is strongly NP-hard even when the allowed error satisfies β ≤ 1/ poly(M, N).Thus, deciding whether a quantum state within inverse-polynomial distance of the separable set is entangled remains NP-hard.
- Concluding Comments: NP-hardness for WMEMβ(SM,N) under a many-one reduction remains open.
- Concluding Comments: The result gives immediate lower bounds on the maximum Euclidean distance between a bound entangled state and SM,N.
- Concluding Comments: Determining whether a quantum channel is entanglement-breaking is NP-hard.Whether this latter problem is strongly NP-hard remains open.
A Appendix
The appendix relates graph structure to Bloch-vector calculations by representing graph edges in a symmetric matrix and identifying which generators contribute to its norm.
- Appendix: Each Bi is zero except for symmetric positions corresponding to entries of graph G's adjacency matrix.The construction places the relevant submatrices Bi in the upper-left corners of the matrices Ai.
- Appendix: Only generators of the form Upq contribute to the sum because C is symmetric and has zero trace.
- Appendix: Each graph edge contributes four symmetrically placed entries of 1 to C, while matching generators satisfy Tr(CUpq) = 2.
- Appendix: Since the number of edges is O(n^2) and N ∈ Θ(n^2), the norm of the constructed vector ĉ is bounded accordingly.