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.
Comments
This version adds cryptographic constructions achieving the separations using efficiently generated states. Theorem III.1 and its proof have been removed
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.
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.
Quantum information theory has provided the formal framework for describing how information is stored, transmitted, and transformed in physical quantum systems [6, 7, 9]. Its entropic formulations underpin our understanding of quantum computation, communication, and cryptography. Yet this theory traditionally treats all quantum operations as freely available, ignoring computational restrictions. In practice, however, any manipulation of quantum information must be performed by devices of bounded complexity and runtime. Capturing such realistic constraints requires extending quantum information theory to include computational efficiency as a fundamental component.This work takes a first step toward building a computational version of quantum information theory, one that treats efficiency as part of the theory itself. The goal is to understand how the behavior of quantum information changes when the parties involved can only perform computationally efficient operations. This approach bridges the abstract, ideal setting of quantum information theory with the practical limitations of real quantum devices, offering a means to study information processing under realistic resource constraints.At the center of this work are two new quantities: the quantum computational min-entropy and the quantum computational max-entropy. These entropies extend standard quantum entropies by explicitly limiting the computational power of the observer or adversary. The quantum computational min-entropy captures how unpredictable a quantum system A remains to an observer holding system B, when that observer is restricted to quantum circuits of bounded size. Formally, for a bipartite state rho AB, we define(c) H-s (min)(A|B)rho := - log d(A) max (epsilon s) B > A' F ((parallel to(A)circle times epsilon(s))(rho(AB)),|Phi (AA')> Quantum information theory; Theory of computation -> Quantum complexity theory
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.
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.
Abstract The max-relative entropy and the conditional min-entropy of a quantum state plays a central role in one-shot and zero-error quantum information theory. One attractive feature of this quantity is that it can be expressed as an optimization over the cone of positive semidefinite operators. Recently, it was shown that when replacing this cone with the cone of separable operators, a new type of conditional min-entropy emerges that admits an operational interpretation in terms of communicating classical information over a quantum channel. In this work, we explore more deeply the idea of building information-theoretic quantities from different base cones and determine which results in quantum information theory rely upon the positive semidefinite cone and which can be generalized. In terms of asymptotic information processing, we find that the standard equipartition properties break down if a given cone fails to approximate the positive semidefinite cone sufficiently well. We also show that the near-equivalence of the smooth max and Hartley entropies breaks down in this setting. We present parallel results for the extended conditional min-entropy, which requires extending the notion of k-superpositive channels to superchannels. On the other hand, we show that for classical-quantum states the separable cone is sufficient to re-cover the asymptotic theory, thereby drawing a strong distinction between the fully and partial quantum settings. We also present operational uses of this framework. We show that the cone restricted min-entropy of a Choi operator captures a measure of entanglement-assisted noiseless classical communication using restricted measurements. We also introduce a novel min-entropy-like quantity that captures the conditions for when one quantum channel can be transformed into another using bistochastic pre-processing. Lastly, we relate this framework to general conic norms and their non-additivity. Throughout this work, we concretely study generalized entropies in resource theories that capture locality and resource theories of coherence/Abelian symmetries.
Computational entropies provide a framework for quantifying uncertainty and randomness under computational constraints. They play a central role in classical cryptography, underpinning the analysis and construction of primitives such as pseudo-random generators, leakage-resilient cryptography, and randomness extractors. However, in the quantum setting, computational analogs of entropy remain largely unexplored. In this work, we initiate the study of quantum computational entropy by definingquantum computational unpredictability entropy, a natural generalization of classical unpredictability entropy to the quantum setting. Our definition builds on the operational interpretation of quantum min-entropy as the optimal guessing probability, while restricting the adversary to efficient guessing strategies. We prove that this entropy satisfies several fundamental properties, including a leakage chain rule that holds even in the presence of unbounded prior quantum side-information. We also show that unpredictability entropy enables pseudo-randomness extraction against quantum adversaries with bounded computational power. Together, these results lay a foundation for developing cryptographic tools that rely on min-entropy in the quantum computational setting.