arXiv:2502.12284 · Nature Physics

Entanglement theory with limited computational resources

Lorenzo Leone, J. Douglas Rizzo, Jens Eisert, Sofiène Jerbi

Published Oct 22, 2025• 6 citations

Abstract

Abstract The precise quantification of the limits to manipulating quantum resources lies at the core of quantum information theory. However, standard information-theoretic analyses do not consider the actual computational complexity involved in performing certain tasks. Here we address this issue within the realm of entanglement theory, finding that accounting for computational efficiency substantially changes what can be achieved using entangled resources. We consider two key figures of merit: the computational distillable entanglement and the computational entanglement cost. These measures quantify the optimal rates of entangled bits that can be extracted from or used to dilute many identical copies of n -qubit bipartite pure states, using computationally efficient local operations and classical communication. We demonstrate that computational entanglement measures diverge considerably from their information-theoretic counterparts. Whereas the information-theoretic distillable entanglement is determined by the von Neumann entropy of the reduced state, we show that the min-entropy governs the computationally efficient setting. On the other hand, computationally efficient entanglement dilution requires maximal consumption of entangled bits, even for nearly unentangled states. Furthermore, in the worst-case scenario, even when an efficient description of the state exists and is fully known, one gains no advantage over state-agnostic protocols. Our findings establish sample-complexity bounds for measuring and testing the von Neumann entropy, fundamental limitations on efficient state compression and efficient local tomography protocols.

DOI: 10.1038/s41567-025-03048-8

Related papers

Computational entanglement distillation beyond pure states: efficient protocols and fundamental limitations

Takeru Utsumi, Jacopo Rizzo, Ryuji Takagi +1 more

The information-theoretic approach to entanglement typically relies on arbitrarily many input copies and unboundedly complex operations; however, the available resources are constrained in reality. This motivates the study of entanglement theory with limited resources. One of its central questions is which quantities characterize entanglement manipulations, and so far, only the idealized case of pure states has been well explored. In this work, we address entanglement distillation from mixed states and identify the Rényi coherent information as the quantity determining the optimal rate in the worst case under two distinct resource constraints. We first characterize the sample-efficient regime, in which unbounded computational power is allowed. Our universal protocol achieves this rate without knowledge of the input state under certain polynomial rank constraints. This rate is optimal among universal protocols: we construct states whose distillable entanglement is nearly extensive, yet from which no universal sample-efficient protocol attains a rate above their Rényi coherent information. We then push this characterization to the computationally efficient frontier: the same bound holds for any efficient protocol even when the input state is known, and another universal protocol achieves this rate efficiently under additional polynomial constraints on the marginal ranks. Overall, our results give the Rényi coherent information a novel operational meaning in two computational settings: universal distillation with limited copies and efficient distillation even with knowledge of the input state.

quant-pharXiv:2610.06787Oct 6, 20260 citations

Accessible Quantum Correlations Under Complexity Constraints

Álvaro Yángüez, Noam Avidan, Jan Kochanowski +1 more

Quantum systems may contain underlying correlations which are inaccessible to computationally bounded observers. We capture this distinction through a framework that analyses bipartite states only using efficiently implementable quantum channels. This leads to a complexity-constrained max-divergence and a corresponding computational min-entropy. The latter quantity recovers the standard operational meaning of the conditional min-entropy: in the fully quantum case, it quantifies the largest overlap with a maximally entangled state attainable via efficient operations on the conditional subsystem. For classical-quantum states, it further reduces to the optimal guessing probability of a computationally bounded observer with access to side information. Lastly, in the absence of side information, the computational min-entropy simplifies to a computational notion of the operator norm. We then establish strong separations between the information-theoretic and complexity-constrained notions of min-entropy. For pure states, there exist highly entangled families of states with extremal min-entropy whose efficiently accessible entanglement in terms of computational min-entropy is exponentially suppressed. For mixed states, the separation is even sharper: the information-theoretic conditional min-entropy can be highly negative while the complexity-constrained quantity remains nearly maximal. Under the cryptographic Learning with Errors hardness assumption, we construct efficiently preparable states exhibiting both separations, even when their preparation circuits are fully known. Overall, our results demonstrate that computational constraints can fundamentally limit the quantum correlations that are observable in practice.

quant-pharXiv:2604.15540Apr 20, 20260 citations

Accessible Quantum Correlations Under Complexity Constraints

Álvaro Yángüez, Noam Avidan, Jan Kochanowski +1 more

Quantum systems may contain underlying correlations which are inaccessible to computationally bounded observers. We capture this distinction through a framework that analyses bipartite states only using efficiently implementable quantum channels. This leads to a complexity-constrained max-divergence and a corresponding computational min-entropy. The latter quantity recovers the standard operational meaning of the conditional min-entropy: in the fully quantum case, it quantifies the largest overlap with a maximally entangled state attainable via efficient operations on the conditional subsystem. For classical-quantum states, it further reduces to the optimal guessing probability of a computationally bounded observer with access to side information. Lastly, in the absence of side information, the computational min-entropy simplifies to a computational notion of the operator norm. We then establish strong separations between the information-theoretic and complexity-constrained notions of min-entropy. For pure states, there exist highly entangled families of states with extremal min-entropy whose efficiently accessible entanglement in terms of computational min-entropy is exponentially suppressed. For mixed states, the separation is even sharper: the information-theoretic conditional min-entropy can be highly negative while the complexity-constrained quantity remains nearly maximal. Overall, our results demonstrate that computational constraints can fundamentally limit the quantum correlations that are observable in practice.

Sep 28, 20260 citations

Efficient Entanglement Manipulation Cookbook: From Mixing to a Computational Second Law

Ilia Ryzov, Faedi Loulidi, David Elkouss

Quantum entanglement is an essential resource for implementing practical quantum devices. However, for the resource to be useful in large-scale applications, it must be accessible to parties with limited computational resources. Computational entanglement measures quantify the usefulness of entanglement in the presence of limited computational resources in the practical setting of non-asymptotic manipulations. In this paper, we build a framework of non-asymptotic efficient entanglement manipulations by systematically analyzing a wide range of properties of two recently introduced computational entanglement measures: the computational one-shot distillable entanglement and cost. To do so, we adapt definitions of some common properties of scalar entanglement measures to the case in which only lower or upper function bounds are available. Using the developed framework, we then proceed to investigate the mathematical behavior of the newly introduced entanglement measures under probabilistic state mixing and tensor-product operations. Furthermore, we analyze how the values of both measures change under local unitary and LOCC transformations. For this, we derive an explicit quantitative connection between the geometry of projective-net-generated families of states and their computational one-shot distillable entanglement, and use this connection to establish an unconditional separation between computational and information-theoretic one-shot distillable entanglement. Furthermore, we investigate the robustness of efficiently accessible entanglement against noise and derive the first quantitative continuity bound on computational distillable entanglement. Finally, as an application of the developed "dictionary" of properties, we establish a fundamental relation between computational entanglement measures that we call the "Second Law of Efficient Entanglement Manipulation".

arXiv:2509.21988Sep 26, 20250 citations

The computational two-way quantum capacity

Johannes Jakob Meyer, Jacopo Rizzo, Asad Raza +3 more

Quantum channel capacities are fundamental to quantum information theory. Their definition, however, does not limit the computational resources of sender and receiver. In this work, we initiate the study of computational quantum capacities. These quantify how much information can be reliably transmitted when imposing the natural requirement that en- and decoding have to be computationally efficient. We focus on the computational two-way quantum capacity and showcase that it is closely related to the computational distillable entanglement of the Choi state of the channel. This connection allows us to show a stark computational capacity separation. Under standard cryptographic assumptions, there exists a quantum channel of polynomial complexity whose computational two-way quantum capacity vanishes while its unbounded counterpart is nearly maximal. More so, we show that there exists a sharp transition in computational quantum capacity from nearly maximal to zero when the channel complexity leaves the polynomial realm. Our results demonstrate that the natural requirement of computational efficiency can radically alter the limits of quantum communication.

quant-pharXiv:2601.15393Jan 23, 20260 citations

Distillable entanglement under dually non-entangling operations

Ludovico Lami, Bartosz Regula

Computing the exact rate at which entanglement can be distilled from noisy quantum states is one of the longest-standing questions in quantum information. We give an exact solution for entanglement distillation under the set of dually non-entangling (DNE) operations—a relaxation of the typically considered local operations and classical communication, comprising all channels which preserve the sets of separable states and measurements. We show that the DNE distillable entanglement coincides with a modified version of the regularised relative entropy of entanglement in which the arguments are measured with a separable measurement. Ours is only the second known regularised formula for the distillable entanglement under any class of free operations in entanglement theory, after that given by Devetak and Winter for (one-way) local operations and classical communication. An immediate consequence of our finding is that, under DNE, entanglement can be distilled from any entangled state. As our second main result, we construct a general upper bound on the DNE distillable entanglement, using which we prove that the separably measured relative entropy of entanglement can be strictly smaller than the regularisation of the standard relative entropy of entanglement, solving an open problem posed by Li and Winter. Finally, we study also the reverse task of entanglement dilution and show that the restriction to DNE operations does not change the entanglement cost when compared with the larger class of non-entangling operations. This implies a strong form of irreversiblility of entanglement theory under DNE operations: even when asymptotically vanishing amounts of entanglement may be generated, entangled states cannot be converted reversibly. Computing how much entanglement can be extracted from imperfect quantum states is a long-standing problem in quantum resource theory. Here, Lami and Regula move away from the usual case in which the operations considered free to implement are local operations and classical communication, and find instead a solution for the case of dually non-entangling operations.

arXiv:2307.11008Nature CommunicationsNov 22, 202412 citations