Computational Relative Entropy

• URL: http://arxiv.org/abs/2509.20472v1
• Date: Wed, 24 Sep 2025 18:41:05 GMT
• Title: Computational Relative Entropy
• Authors: Johannes Jakob Meyer, Asad Raza, Jacopo Rizzo, Lorenzo Leone, Sofiene Jerbi, Jens Eisert,
• Abstract summary: We go beyond the prevailing single-shot approach and take a new direction in computational quantum information theory.<n>We define the computational relative entropy as the optimal error exponent in asymmetric hypothesis testing.<n>We derive a computational entropy that operationally characterizes optimal compression rates for quantum states under computational limitations.
• Score: 0.29555437538581053
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Our capacity to process information depends on the computational power at our disposal. Information theory captures our ability to distinguish states or communicate messages when it is unconstrained with unrivaled elegance. For computationally bounded observers the situation is quite different. They can, for example, be fooled to believe that distributions are more random than they actually are. In our work, we go beyond the prevailing single-shot approach and take a new direction in computational quantum information theory that captures the essence of complexity-constrained information theory while retaining the look and feel of the unbounded asymptotic theory. As our foundational quantity, we define the computational relative entropy as the optimal error exponent in asymmetric hypothesis testing when restricted to polynomially many copies and quantum gates, defined in a mathematically rigorous way. Building on this foundation, we prove a computational analogue of Stein's lemma, establish computational versions of fundamental inequalities like Pinsker's bound, and demonstrate a computational smoothing property showing that computationally indistinguishable states yield equivalent information measures. We derive a computational entropy that operationally characterizes optimal compression rates for quantum states under computational limitations and show that our quantities apply to computational entanglement theory, proving a computational version of the Rains bound. Our framework reveals striking separations between computational and unbounded information measures, including quantum-classical gaps that arise from cryptographic assumptions, demonstrating that computational constraints fundamentally alter the information-theoretic landscape and open new research directions at the intersection of quantum information, complexity theory, and cryptography.

Related papers

• Efficient Quantum Measurements: Computational Max- and Measured Rényi Divergences and Applications [0.0]
  We study two new types of computational divergences, which we term computational max-divergence and computational measured R'enyi divergences.<n>We prove that, in the infinite-order limit, the computational measured R'enyi divergence coincides with the computational max-divergence.<n>For the many-copy regime, we introduce regularized versions and establish a one-sided computational Stein bound on achievable hypothesis-testing exponents.<n>We further define resource measures induced by our computational divergences and prove an continuity bound for the computational measured relative entropy of resource.
  arXiv  Detail & Related papers  (2025-09-25T15:22:23Z)
• Fully Quantum Computational Entropies [1.8749305679160362]
  We introduce two innovative entropies: quantum computational min- and max-entropies.<n>We establish a series of essential properties for this new entropy, including data processing and a chain rule.<n>This work marks a critical step toward a quantum information theory that incorporates computational elements.
  arXiv  Detail & Related papers  (2025-06-16T23:56:19Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Efficient Representation of Gaussian Fermionic Pure States in Non-Computational Bases [0.0]
  This paper introduces an innovative approach for representing Gaussian fermionic states, pivotal in quantum spin systems and fermionic models. We focus on transitioning these states from the conventional computational (sigmaz) basis to more complex bases, such as (phi, fracpi2, alpha) We present a novel algorithm that not only simplifies the basis transformation but also reduces computational complexity.
  arXiv  Detail & Related papers  (2024-03-05T19:43:33Z)
• Computational Entanglement Theory [11.694169299062597]
  computational entanglement theory is inspired by the emerging usefulness of ideas from quantum information theory in computational complexity. We show that the computational measures are fundamentally different from their information-theoretic counterparts by presenting gaps between them. We discuss the relations between computational entanglement theory and other topics, such as quantum cryptography and notions of pseudoentropy.
  arXiv  Detail & Related papers  (2023-10-04T12:53:04Z)
• Calculating the many-body density of states on a digital quantum computer [58.720142291102135]
  We implement a quantum algorithm to perform an estimation of the density of states on a digital quantum computer. We use our algorithm to estimate the density of states of a non-integrable Hamiltonian on the Quantinuum H1-1 trapped ion chip for a controlled register of 18bits.
  arXiv  Detail & Related papers  (2023-03-23T17:46:28Z)
• General quantum algorithms for Hamiltonian simulation with applications to a non-Abelian lattice gauge theory [44.99833362998488]
  We introduce quantum algorithms that can efficiently simulate certain classes of interactions consisting of correlated changes in multiple quantum numbers. The lattice gauge theory studied is the SU(2) gauge theory in 1+1 dimensions coupled to one flavor of staggered fermions. The algorithms are shown to be applicable to higher-dimensional theories as well as to other Abelian and non-Abelian gauge theories.
  arXiv  Detail & Related papers  (2022-12-28T18:56:25Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• No-signalling constrains quantum computation with indefinite causal structure [45.279573215172285]
  We develop a formalism for quantum computation with indefinite causal structures. We characterize the computational structure of higher order quantum maps. We prove that these rules, which have a computational and information-theoretic nature, are determined by the more physical notion of the signalling relations between the quantum systems.
  arXiv  Detail & Related papers  (2022-02-21T13:43:50Z)
• Numerical Simulations of Noisy Quantum Circuits for Computational Chemistry [51.827942608832025]
  Near-term quantum computers can calculate the ground-state properties of small molecules. We show how the structure of the computational ansatz as well as the errors induced by device noise affect the calculation.
  arXiv  Detail & Related papers  (2021-12-31T16:33:10Z)
• Computation in a general physical setting [0.0]
  This paper reviews and extends some results on the computational ability of quantum theory. It provides a refined version of the conjecture that a quantum computer can simulate the computation in any theory. It ends by describing an important relation between this conjecture and delegated computation, similar to the relation between quantum non-locality and device-independent cryptography.
  arXiv  Detail & Related papers  (2021-08-25T20:00:20Z)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing. We show that entropy estimation for distributions or states produced by either log-depth circuits or constant-depth circuits with gates of bounded fan-in and unbounded fan-out is at least as hard as the Learning with Errors problem.
  arXiv  Detail & Related papers  (2020-02-27T15:32:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.