Computable Entanglement Cost under Positive Partial Transpose Operations

Quantum information theory is plagued by the problem of regularizations, which require the evaluation of formidable asymptotic quantities. This makes it computationally intractable to gain a precise quantitative understanding of the ultimate efficiency of key operational tasks such as entanglement manipulation. Here, we consider the problem of computing the asymptotic entanglement cost of preparing noisy quantum states under quantum operations with positive partial transpose (PPT). By means of an analytical example, a previously claimed solution to this problem is shown to be incorrect. Building on a previous characterization of the PPT entanglement cost in terms of a regularized formula, we construct instead a hierarchy of semidefinite programs that bypasses the issue of regularization altogether, and converges to the true asymptotic value of the entanglement cost. Our main result establishes that this convergence happens exponentially fast, thus yielding an efficient algorithm that approximates the cost up to an additive error epsilon in time poly(D, log(1/epsilon)), where D is the underlying Hilbert space dimension. To our knowledge, this is the first time that an asymptotic entanglement measure is shown to be efficiently computable despite no closed-form formula being available.