Joseph M. Renes

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.

Abstract Noise in quantum metrology reduces the sensitivity to which one can determine an unknown parameter in the evolution of a quantum state, such as time. Here, we consider a probe system prepared in a pure state that evolves according to a given Hamiltonian. We study the resulting local sensitivity of the probe to time after the application of a given noise channel. We show that the decrease in sensitivity due to the noise is equal to the sensitivity that the environment gains with respect to the energy of the probe. We obtain necessary and sufficient conditions for when the probe does not suffer any sensitivity loss; these conditions are analogous to, but weaker than, the Knill-Laflamme quantum error correction conditions. New upper bounds on the sensitivity of the noisy probe are obtained via our uncertainty relation, by applying known sensitivity lower bounds on the environments system. Our time-energy uncertainty relation also generalizes to any two arbitrary parameters whose evolutions are generated by Hermitian operators. This uncertainty relation asserts a general trade-off between the sensitivities that two parties can achieve for any two respective parameters of a single quantum system, in terms of the commutator of the associated generators. We consider applications to strongly interacting many-body probes. We find probe states for general interaction graphs of Ising and Heisenberg interactions that are robust to any single located error. For a 1D spin chain with nearest-neighbor interactions subject to amplitude damping noise on each site, we verify numerically that our probe state does not lose any sensitivity to first order in the noise parameter.