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.

Quantum information processing is limited, in practice, to efficiently implementable operations. This motivates the study of quantum divergences and entropies that preserve their operational meaning while faithfully capturing computational constraints. In this joint submission, we introduce a mathematical framework for computational quantum information theory from which computational divergences and established computational entropies naturally arise. Within this framework, we define a computational max-divergence and computational measured Rényi divergences. We relate these quantities to efficient hypothesis testing and use them to analyze computational resource theories such as entanglement. We further connect the new computational max-divergence to the previously established computational min-entropy and computational hypothesis testing relative entropy. In particular, we show that the computational max-divergence serves as a parent quantity for the computational min-entropy, thereby endowing the computational max-divergence with an operational meaning. Moreover, we prove that the computational hypothesis testing relative entropy is approximately characterized by a smoothed version of the computational max-divergence. Together, these results extend well-known information-theoretic relationships to the computational setting and unify several operationally-motivated computational quantities.