Entanglement theory is at the heart of quantum information science, and any quantum advantage of any of its applications can be traced back to entanglement being present. For this reason, quantitative entanglement theory was developed concomitantly with the early steps in quantum information theory. In this work, we add a new computational twist to the study of entanglement: we investigate bipartite pure-state entanglement theory under computational constraints, focusing on two key figures of merit: the computational distillable entanglement and the computational entanglement cost. Assuming access to only polynomially many input copies of the state and to local quantum protocols running in at most polynomial time, the computational distillable entanglement quantifies the maximal rate of ebits that can be distilled across the bipartition A|B, while the computational entanglement cost measures the minimal rate of ebits required to efficiently dilute the state across A|B. We demonstrate that these quantities fundamentally differ from their information-theoretic counterparts, as they are no longer characterized by the von Neumann entropy, which becomes entirely inaccessible under computational constraints. Instead, a strikingly different form of entanglement assumes a pivotal role: We rigorously establish the existence of states with computational distillable entanglement proportional to the min-entropy S_{\min}. This is achieved by proving achievability, exhibiting a protocol attaining this rate, and establishing optimality, thereby providing a novel operational interpretation of the min-entropy S_{\min}. For the converse task of entanglement dilution, we prove the optimality of the simplest state-agnostic protocol: quantum teleportation. Specifically, we demonstrate the existence of pure states with a computational entanglement cost of \Omega(n) but an actual entanglement cost of o(1). As a corollary, we prove an exponential lower bound on the sample complexity for estimating the von Neumann entropy to a constant additive precision, even in scenarios with constant entanglement entropy.

Authors: LL, Jacopo Rizzo, Sofiene Jerbi, Jens Eisert