Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1704.07309

Computational Notions of Quantum Min-Entropy

Yi-Hsiu Chen, Kai-Min Chung, Ching–Yi Lai, Salil Vadhan, Xiaodi Wu

Published Apr 24, 2017• 4 citations
arXivHTMLPDF

Abstract

We initiate the study of computational entropy in the quantum setting. We investigate to what extent the classical notions of computational entropy generalize to the quantum setting, and whether quantum analogues of classical theorems hold. Our main results are as follows. (1) The classical Leakage Chain Rule for pseudoentropy can be extended to the case that the leakage information is quantum (while the source remains classical). Specifically, if the source has pseudoentropy at least $k$, then it has pseudoentropy at least $k-\ell$ conditioned on an $\ell$-qubit leakage. (2) As an application of the Leakage Chain Rule, we construct the first quantum leakage-resilient stream-cipher in the bounded-quantum-storage model, assuming the existence of a quantum-secure pseudorandom generator. (3) We show that the general form of the classical Dense Model Theorem (interpreted as the equivalence between two definitions of pseudo-relative-min-entropy) does not extend to quantum states. Along the way, we develop quantum analogues of some classical techniques (e.g. the Leakage Simulation Lemma, which is proven by a Non-uniform Min-Max Theorem or Boosting). On the other hand, we also identify some classical techniques (e.g. Gap Amplification) that do not work in the quantum setting. Moreover, we introduce a variety of notions that combine quantum information and quantum complexity, and this raises several directions for future work.

DOI
10.48550/arxiv.1704.07309

Related papers

Quantum Computational Unpredictability Entropy and Quantum Leakage Resilience

Noam Avidan, Rotem Arnon-Friedman

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.

arXiv:2505.13710•IEEE Transactions on Information Theory•Jan 28, 2026•1 citation

Computational Entanglement Theory

Rotem Arnon-Friedman, Zvika Brakerski, Thomas Vidick

We initiate a rigorous study of computational entanglement theory, inspired by the emerging usefulness of ideas from quantum information theory in computational complexity. We define new operational computational measures of entanglement -- the computational one-shot entanglement cost and distillable entanglement. We then show that the computational measures are fundamentally different from their information-theoretic counterparts by presenting gaps between them. We proceed by refining and extending the definition of pseudo-entanglement, introduced by Aaronson et al., 2022, using the new operational measures; and we present constructions of pseudo-entangled states (for our new definition) based on post-quantum cryptographic assumptions. Finally, we discuss the relations between computational entanglement theory and other topics, such as quantum cryptography and notions of pseudoentropy, as well as the relevance of our new definitions to the study of the AdS/CFT correspondence. We believe that, in addition to the contributions presented in the current manuscript, our work opens multiple research directions, of relevance both to the theoretical quantum information theory community as well as for future applications of quantum networks and cryptography.

arXiv:2310.02783•Oct 4, 2023•0 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.15540•Apr 20, 2026•0 citations

Interactive Leakage Chain Rule for Quantum Min-entropy

Ching–Yi Lai, Kai-Min Chung

The leakage chain rule for quantum min-entropy quantifies the change of min-entropy when one party gets additional leakage about the information source. Herein we provide an interactive version that quantifies the change of min-entropy between two parties, who share an initial classical-quantum state and are allowed to run a two-party protocol. As an application, we prove new versions of lower bounds on the complexity of quantum communication of classical information.

arXiv:1809.10694•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•2 citations

Entanglement Sampling and Applications

Frédéric Dupuis, Omar Fawzi, Stephanie Wehner

A natural measure for the amount of quantum information that a physical system E holds about another system A = A1, .. . , Anis given by the min-entropy Hmin(A|E). In particular, the min-entropy measures the amount of entanglement between E and A, and is the relevant measure when analyzing a wide variety of problems ranging from randomness extraction in quantum cryptography, decoupling used in channel coding, to physical processes such as thermalization or the thermodynamic work cost (or gain) of erasing a quantum system. As such, it is a central question to determine the behavior of the minentropy after some process M. is applied to the system A. Here, we introduce a new generic tool relating the resulting min-entropy to the original one, and apply it to several settings of interest. A simple example of such a process is the one of sampling, where a subset S of the systems A1, ... , An is selected at random. Our tool allows us to quantify the entanglement that E has with the selected systems AS, i.e., Hmin(AS|ES) as a function of the original Hmin(A|E). We give two applications of this result. First, it directly provides the first local quantum-to-classical randomness extractors for use in quantum cryptography, as well as decoupling operations acting on only a small fraction AS of the input A. Moreover, it gives lower bounds on the dimension of k-out-of-n fully quantum random access encodings. Another natural example of such a process is a measurement in, e.g., BB84 bases commonly used in quantum cryptography. We establish the first entropic uncertainty relations with quantum side information that are nontrivial whenever E is not maximally entangled with A. As a consequence, we are able to prove optimality of quantum cryptographic schemes in the noisy-storage model. This model allows for the secure implementation of two-party cryptographic primitives under the assumption that the adversary cannot store quantum information perfectly. A special case is the bounded-quantum-storage model (BQSM), which assumes that the adversary's quantum memory device is noise free but limited in size. Ever since the inception of the BQSM, it has been a vexing open question to determine whether the security is possible as long as the adversary can only.

arXiv:1305.1316•IEEE Transactions on Information Theory•Nov 26, 2014•95 citations

Computational Cryptography from Pseudoentanglement

Ilia Ryzov, Manuel Goulão, Faedi Loulidi +1 more

The advent of pseudoentanglement and computational entanglement theory bootstrapped a wave of research at the intersection of computer science and information theory. In parallel, computational cryptography has undergone substantial development, prompted by the introduction of pseudorandom states and followed by the establishment of a baseline for the computational hardness required for quantum cryptography, from which EFI pairs emerge as a central primitive. We study the connection between pseudoentanglement and computational cryptography through EFI pairs. Our goal is to enable the use of resources arising from computational entanglement theory in the field of cryptography. For this, we establish the relation between operational instances of pseudoentanglement and the hierarchy of minimal assumptions for computational cryptography. We show that the existence of pseudoentanglement under two different operational definitions, with efficient state generation, is a sufficient condition for the existence of EFI pairs. Combined with a previously established result that the converse also holds under the second definition, this allows us to also demonstrate their equivalence. This places pseudoentanglement alongside other minimal assumptions in cryptography, not only offering an alternative perspective on this fundamental problem, but also building a bridge that allows insights from either area to inform the other. While proving these theorems, we introduce and demonstrate technical lemmas in quantum information and computational entanglement theory, relating the computational entanglement measures to the distance between states, establishing distinguishing conditions for mixtures of two families given pairwise distances between their states, and demonstrating the first continuity relation for a computational entanglement measure.

quant-pharXiv:2609.29917•Sep 25, 2026•0 citations
We initiate the study of computational entropy in the quantum setting. We investigate to what extent the classical notions of computational entropy generalize to the quantum setting, and whether quantum analogues of classical theorems hold. Our main results are as follows. (1) The classical Leakage Chain Rule for pseudoentropy can be extended to the case that the leakage information is quantum (while the source remains classical). Specifically, if the source has pseudoentropy at least kkk, then it has pseudoentropy at least k−ℓk-\ellk−ℓ conditioned on an ℓ\ellℓ-qubit leakage. (2) As an application of the Leakage Chain Rule, we construct the first quantum leakage-resilient stream-cipher in the bounded-quantum-storage model, assuming the existence of a quantum-secure pseudorandom generator. (3) We show that the general form of the classical Dense Model Theorem (interpreted as the equivalence between two definitions of pseudo-relative-min-entropy) does not extend to quantum states. Along the way, we develop quantum analogues of some classical techniques (e.g. the Leakage Simulation Lemma, which is proven by a Non-uniform Min-Max Theorem or Boosting). On the other hand, we also identify some classical techniques (e.g. Gap Amplification) that do not work in the quantum setting. Moreover, we introduce a variety of notions that combine quantum information and quantum complexity, and this raises several directions for future work.
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.
We initiate a rigorous study of computational entanglement theory, inspired by the emerging usefulness of ideas from quantum information theory in computational complexity. We define new operational computational measures of entanglement -- the computational one-shot entanglement cost and distillable entanglement. We then show that the computational measures are fundamentally different from their information-theoretic counterparts by presenting gaps between them. We proceed by refining and extending the definition of pseudo-entanglement, introduced by Aaronson et al., 2022, using the new operational measures; and we present constructions of pseudo-entangled states (for our new definition) based on post-quantum cryptographic assumptions. Finally, we discuss the relations between computational entanglement theory and other topics, such as quantum cryptography and notions of pseudoentropy, as well as the relevance of our new definitions to the study of the AdS/CFT correspondence. We believe that, in addition to the contributions presented in the current manuscript, our work opens multiple research directions, of relevance both to the theoretical quantum information theory community as well as for future applications of quantum networks and cryptography.
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.
A natural measure for the amount of quantum information that a physical system E holds about another system A = A1, .. . , Anis given by the min-entropy Hmin(A|E). In particular, the min-entropy measures the amount of entanglement between E and A, and is the relevant measure when analyzing a wide variety of problems ranging from randomness extraction in quantum cryptography, decoupling used in channel coding, to physical processes such as thermalization or the thermodynamic work cost (or gain) of erasing a quantum system. As such, it is a central question to determine the behavior of the minentropy after some process M. is applied to the system A. Here, we introduce a new generic tool relating the resulting min-entropy to the original one, and apply it to several settings of interest. A simple example of such a process is the one of sampling, where a subset S of the systems A1, ... , An is selected at random. Our tool allows us to quantify the entanglement that E has with the selected systems AS, i.e., Hmin(AS|ES) as a function of the original Hmin(A|E). We give two applications of this result. First, it directly provides the first local quantum-to-classical randomness extractors for use in quantum cryptography, as well as decoupling operations acting on only a small fraction AS of the input A. Moreover, it gives lower bounds on the dimension of k-out-of-n fully quantum random access encodings. Another natural example of such a process is a measurement in, e.g., BB84 bases commonly used in quantum cryptography. We establish the first entropic uncertainty relations with quantum side information that are nontrivial whenever E is not maximally entangled with A. As a consequence, we are able to prove optimality of quantum cryptographic schemes in the noisy-storage model. This model allows for the secure implementation of two-party cryptographic primitives under the assumption that the adversary cannot store quantum information perfectly. A special case is the bounded-quantum-storage model (BQSM), which assumes that the adversary's quantum memory device is noise free but limited in size. Ever since the inception of the BQSM, it has been a vexing open question to determine whether the security is possible as long as the adversary can only.
The advent of pseudoentanglement and computational entanglement theory bootstrapped a wave of research at the intersection of computer science and information theory. In parallel, computational cryptography has undergone substantial development, prompted by the introduction of pseudorandom states and followed by the establishment of a baseline for the computational hardness required for quantum cryptography, from which EFI pairs emerge as a central primitive. We study the connection between pseudoentanglement and computational cryptography through EFI pairs. Our goal is to enable the use of resources arising from computational entanglement theory in the field of cryptography. For this, we establish the relation between operational instances of pseudoentanglement and the hierarchy of minimal assumptions for computational cryptography. We show that the existence of pseudoentanglement under two different operational definitions, with efficient state generation, is a sufficient condition for the existence of EFI pairs. Combined with a previously established result that the converse also holds under the second definition, this allows us to also demonstrate their equivalence. This places pseudoentanglement alongside other minimal assumptions in cryptography, not only offering an alternative perspective on this fundamental problem, but also building a bridge that allows insights from either area to inform the other. While proving these theorems, we introduce and demonstrate technical lemmas in quantum information and computational entanglement theory, relating the computational entanglement measures to the distance between states, establishing distinguishing conditions for mixtures of two families given pairwise distances between their states, and demonstrating the first continuity relation for a computational entanglement measure.