Noam Avidan

Quantum information theory, particularly its entropic formulations, has made remarkable strides in characterizing quantum systems and tasks. However, a critical dimension remains underexplored: computational efficiency. While classical computational entropies integrate complexity and feasibility into information measures, analogous concepts have yet to be rigorously developed in the quantum setting. In this joint submission, we advance a quantum computational information theory through two complementary works. The first introduces the quantum computational unpredictability entropy, a natural generalization of the min entropy for classical-quantum states and of the classical unpredictability entropy that quantifies the guessing probability of classical randomness using quantum side information and bounded computational power. The second work extends this to the fully quantum setting by defining fully quantum computational min- and max-entropies. The computational min-entropy generalizes unpredictability entropy and retains essential properties, including data processing, a fully quantum leakage chain rule, and it satisfies a novel purification chain rule. The computational max-entropy is defined via a canonical duality relation and it captures a notion of efficient entanglement distillation under bounded quantum circuits. With the introduction of these computational entropies and their analysis, this work marks a critical step toward a quantum information theory that incorporates computational elements.

Computational entropy notions play a central role in classical cryptography, with well-developed frameworks for analyzing unpredictability, leakage resilience, and pseudo-randomness. In the quantum setting, however, computational analogues of entropy remain largely unexplored. While quantum information theory provides powerful tools based on information-theoretic entropy, these do not capture the limitations of computationally bounded quantum adversaries. In this work, we initiate the study of quantum computational entropy by defining \emph{quantum computational unpredictability entropy}, a natural generalization of classical unpredictability entropy to the quantum setting. Our definition is based on the operational meaning of quantum min-entropy, but restricts the adversary to efficient quantum guessing strategies. We prove that this entropy satisfies several important properties, including a leakage chain rule that holds even in the presence of prior quantum side-information. We also show that unpredictability entropy supports 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.