Thomas Hahn

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.

Variational techniques have been recently developed to find tighter bounds on the von Neumann entropy in a completely device-independent (DI) setting. This, in turn, has led to significantly improved key rates of DI protocols, in both the asymptotic limit as well as in the finite-size regime. In this work, we derive novel variational expressions for Petz-Rényi divergences instead. We also derive two critical applications of this result. First, we show how these variational expressions can be used to further improve the finite-size key rate of DI protocols, by developing a fully-Rényi entropy accumulation theorem that can utilize these expressions for key rate computations. Second, we derive a security condition for DI advantage distillation that is based on the pretty good fidelity. We implement these techniques to derive increased noise tolerances for DIQKD protocols, which surpass the previously known bounds.

The entropy accumulation theorem, and its subsequent generalized version, is a powerful tool in the security analysis of many device-dependent and device-independent cryptography protocols. However, it has the drawback that the finite-size bounds it yields are not necessarily optimal, and furthermore it relies on the construction of an affine min-tradeoff function, which can often be challenging to construct optimally in practice. In this work, we address both of these challenges simultaneously by deriving a new entropy accumulation bound. Our bound yields significantly better finite-size performance, and can be computed as an intuitively interpretable convex optimization, without any specification of affine min-tradeoff functions. Furthermore, it can be applied directly at the level of Renyi entropies if desired, yielding fully-Renyi security proofs. Our proof techniques are based on elaborating on a connection between entropy accumulation and the frameworks of quantum probability estimation or f-weighted Rényi entropies, and in the process we obtain some new results with respect to those frameworks as well.

Device-independent (DI) cryptography represents the highest level of security, enabling cryptographic primitives to be executed safely on untrusted hardware. Moreover, with successful proof-of-concept demonstrations in randomness expansion, randomness amplification, and quantum key distribution, the field is steadily advancing toward commercial viability. Critical to this continued progression is the development of tighter finite-size security proofs. In this work, we provide a simple method to obtain tighter finite size security proofs for protocols based on the CHSH game which is the nonlocality test used in all of the proof-of-concept experiments. We achieve this by analytically solving key-rate optimization problems based on Rényi entropies, providing a simple method to obtain tighter finite-size key rates.

The entropy accumulation theorem, and its subsequent generalized version, is a powerful tool in the security analysis of many device-dependent and device-independent cryptography protocols. However, it has the drawback that the finite-size bounds it yields are not necessarily optimal, and furthermore, it relies on the construction of an affine min-tradeoff function, which in practice can often be challenging to construct optimally. In this work, we address both of these challenges simultaneously by deriving a new entropy-accumulation bound. Our bound yields significantly better finite-size performance, and can be computed as a convex optimization without any specification of affine min-tradeoff functions. Furthermore, it can be applied directly at the level of Rényi entropies if desired, yielding fully-Rényi security proofs. Our proof techniques are based on elaborating on a connection between entropy accumulation and the framework of quantum probability estimation, and in the process we obtain some new results with respect to the latter framework as well.

Variational techniques have been recently developed to find incredibly tight bounds on the von Neumann entropy in a completely device-independent (DI) setting. This, in turn, has led to significantly improved key rates of DI protocols, in both the asymptotic limit as well as in the finite-size regime. In this paper, we discuss two approaches towards applying these variational methods for Petz-Rényi divergences instead. We then show how this can be used to further improve the finite-size key rate of DI protocols, utilizing a fully-Rényi entropy accumulation theorem developed in a partner work. Petz-Rényi divergences can also be applied to study DI advantage distillation, in which two-way communication is used to improve the noise tolerance of quantum key distribution (QKD) protocols. We implement these techniques to derive increased noise tolerances for DIQKD protocols, which surpass all previous known bounds.