pith. sign in

arxiv: 2509.20472 · v2 · submitted 2025-09-24 · 🪐 quant-ph · cs.CC· cs.CR· cs.IT· math.IT

Computational relative entropy

Johannes Jakob Meyer , Asad Raza , Jacopo Rizzo , Lorenzo Leone , Sofiene Jerbi , Jens Eisert This is my paper

Pith reviewed 2026-05-18 13:39 UTC · model grok-4.3

classification 🪐 quant-ph cs.CCcs.CRcs.ITmath.IT
keywords computational relative entropyquantum hypothesis testingStein's lemmacomputational information theoryquantum complexityPinsker's boundquantum entanglementcomputational smoothing
0
0 comments X

The pith

The computational relative entropy measures how well polynomially bounded quantum observers can distinguish states and satisfies a version of Stein's lemma.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines the computational relative entropy as the optimal error exponent achievable in asymmetric hypothesis testing when an observer is restricted to polynomially many copies and polynomially many quantum gates. It proves that this quantity obeys a computational analogue of Stein's lemma, along with versions of Pinsker's bound and a smoothing property for states that look the same to efficient observers. A reader would care because everyday quantum information tasks are performed by devices with limited computational power, so the usual unbounded information measures can give misleading predictions about what is actually achievable.

Core claim

The paper establishes that the computational relative entropy, defined as the optimal error exponent in asymmetric hypothesis testing restricted to polynomially many copies and quantum gates, admits a computational analogue of Stein's lemma. It further establishes computational versions of Pinsker's bound and a smoothing property under which computationally indistinguishable states yield equivalent computational information measures, and extends the framework to a computational entropy that characterizes optimal compression rates and to a computational version of the Rains bound in entanglement theory.

What carries the argument

The computational relative entropy, defined as the optimal error exponent in asymmetric hypothesis testing when restricted to polynomially many copies and quantum gates.

If this is right

  • A computational Stein's lemma holds, relating the new quantity to the usual relative entropy under polynomial restrictions.
  • Computational versions of Pinsker's bound and other fundamental inequalities remain valid.
  • Computationally indistinguishable states produce the same values for the derived computational entropy and other measures.
  • The framework yields a computational Rains bound that limits entanglement measures under computational constraints.
  • Separations appear between computational and unbounded information measures, including gaps that rely on cryptographic assumptions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same definition could be applied to analyze the security of quantum cryptographic protocols against computationally bounded adversaries.
  • Small-scale numerical simulations of restricted quantum circuits could test whether the predicted error exponents match explicit calculations for simple state pairs.
  • Optimal compression rates for quantum data may turn out lower when the decoder must also run in polynomial time.
  • The approach opens a route to import tools from complexity theory to prove lower bounds on achievable rates in quantum information tasks.

Load-bearing premise

The choice that limiting observers to polynomially many copies and polynomially many quantum gates correctly captures what it means to be computationally bounded for information-theoretic tasks.

What would settle it

A concrete counterexample in which the optimal error exponent for distinguishing two fixed families of quantum states with polynomially many copies and gates deviates from the value assigned by the defined computational relative entropy.

read the original 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 beauty and 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 build a new foundation for a 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 fundamental 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper defines the computational relative entropy as the optimal error exponent in asymmetric hypothesis testing restricted to polynomially many copies and polynomially many quantum gates. It proves a computational analogue of Stein's lemma, computational versions of Pinsker's inequality and smoothing, an operational characterization of a computational entropy for compression rates, and a computational Rains bound for entanglement. The framework exhibits separations from the unbounded case, including quantum-classical gaps that rely on cryptographic assumptions.

Significance. If the central claims hold, the work supplies a rigorous foundation for complexity-bounded quantum information theory that preserves the asymptotic character of the classical theory. Strengths include the explicit operational definition, the derivation of multiple computational analogues to standard results, and the identification of separations grounded in cryptographic assumptions. These elements position the manuscript as a potential bridge between quantum information and complexity theory.

major comments (3)
  1. [Definition of computational relative entropy] Definition section (computational relative entropy): the modeling choice of polynomially many copies and gates is presented as capturing computational boundedness, yet the manuscript does not demonstrate that the resulting error exponent remains invariant under reasonable changes in the polynomial degree (e.g., n^k versus n^{k+1}) for states that are otherwise efficiently distinguishable. This invariance is load-bearing for the subsequent claims that the quantity is a stable foundation for computational Stein, Pinsker, and Rains results.
  2. [Computational analogue of Stein's lemma] Computational Stein's lemma section: the proof sketch asserts an asymptotic exponent under the polynomial restriction, but the error-term analysis and the precise dependence on the gate set are not fully expanded; without these details it is unclear whether the claimed equality to the computational relative entropy holds without additional modeling assumptions.
  3. [Computational Rains bound] Computational Rains bound section: the reduction from the unbounded Rains bound to the computational version relies on the computational relative entropy being well-defined and continuous under the polynomial resource cutoff; if the definition is sensitive to the precise polynomial, the bound may not transfer directly.
minor comments (2)
  1. [Notation and definitions] Notation for the polynomial resource bound is introduced without an explicit symbol; a dedicated definition (e.g., Eq. (X)) would improve readability.
  2. [Introduction] Several long sentences in the introduction and abstract could be split to enhance clarity.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments, which have helped us strengthen the presentation of our results. We address each major comment below and indicate the revisions made to the manuscript.

read point-by-point responses

  1. Referee: [Definition of computational relative entropy] Definition section (computational relative entropy): the modeling choice of polynomially many copies and gates is presented as capturing computational boundedness, yet the manuscript does not demonstrate that the resulting error exponent remains invariant under reasonable changes in the polynomial degree (e.g., n^k versus n^{k+1}) for states that are otherwise efficiently distinguishable. This invariance is load-bearing for the subsequent claims that the quantity is a stable foundation for computational Stein, Pinsker, and Rains results.

    Authors: We agree that establishing invariance under changes in the polynomial degree is essential for the robustness of the definition. In the revised manuscript we have added a new lemma in the definition section, together with a short proof, showing that the computational relative entropy is invariant under replacement of the polynomial bound p(n) by any q(n) = O(p(n)^c) for constant c. The argument proceeds by observing that any additional polynomial resources can be absorbed into the existing bound without changing the asymptotic error exponent for states that admit efficient distinguishers; for states outside this regime the quantity is not intended to be used. This addition directly supports the stability of the subsequent results. revision: yes

  2. Referee: [Computational analogue of Stein's lemma] Computational Stein's lemma section: the proof sketch asserts an asymptotic exponent under the polynomial restriction, but the error-term analysis and the precise dependence on the gate set are not fully expanded; without these details it is unclear whether the claimed equality to the computational relative entropy holds without additional modeling assumptions.

    Authors: We thank the referee for noting the need for greater detail. The revised manuscript now contains an expanded proof of the computational Stein lemma that includes explicit bounds on the error terms, showing they vanish in the asymptotic regime under the polynomial-copy and polynomial-gate constraints. We also clarify that the result holds for any universal gate set that can approximate arbitrary unitaries to inverse-polynomial precision in polynomial time; the exponent itself is independent of the concrete choice of universal gate set up to factors that do not affect the leading asymptotic term. These expansions remove the need for additional modeling assumptions. revision: yes

  3. Referee: [Computational Rains bound] Computational Rains bound section: the reduction from the unbounded Rains bound to the computational version relies on the computational relative entropy being well-defined and continuous under the polynomial resource cutoff; if the definition is sensitive to the precise polynomial, the bound may not transfer directly.

    Authors: We have strengthened the argument in the computational Rains bound section by explicitly invoking the invariance lemma added to the definition section. Because the computational relative entropy is continuous (in the appropriate sense) under changes to the polynomial resource cutoff, the reduction from the standard Rains bound carries over directly. A short remark has been inserted to make this dependence transparent. revision: yes

Circularity Check

0 steps flagged

Computational relative entropy introduced by direct definition as error exponent; no reduction of theorems to self-referential fitting or load-bearing self-citation.

full rationale

The paper defines the central quantity explicitly as the optimal error exponent under polynomial-copy and polynomial-gate restrictions in asymmetric hypothesis testing. It then derives computational analogues of Stein's lemma, Pinsker's bound, and smoothing properties from this definition. No quoted equations or steps show a claimed prediction or uniqueness result reducing by construction to a fitted parameter or prior self-citation whose validity depends on the present work. The modeling choice of polynomial bounds is stated as an assumption rather than derived from the results themselves, leaving the derivation chain self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The framework rests on standard quantum information axioms plus the modeling decision to use polynomial resources as the computational bound; no free parameters or new physical entities are introduced.

axioms (1)
  • standard math Standard axioms of quantum mechanics and asymptotic information theory
    Background for defining relative entropy and hypothesis testing.
invented entities (1)
  • computational relative entropy no independent evidence
    purpose: Captures optimal error exponent under polynomial copy and gate limits
    Newly defined mathematical quantity; no independent physical evidence supplied in abstract.

pith-pipeline@v0.9.0 · 5790 in / 1314 out tokens · 47845 ms · 2026-05-18T13:39:27.977830+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Accessible Quantum Correlations Under Complexity Constraints

    quant-ph 2026-04 unverdicted novelty 7.0

    Computational constraints exponentially suppress accessible entanglement for some highly entangled quantum states and can make mixed-state min-entropy appear maximal when the information-theoretic version is negative.

Reference graph

Works this paper leans on

57 extracted references · 57 canonical work pages · cited by 1 Pith paper · 2 internal anchors

  1. [1]

    Aaronson, A

    S. Aaronson, A. Bouland, B. Fefferman, S. Ghosh, U. Vazirani, C. Zhang, and Z. Zhou. Quantum pseudoentanglement. 2022

    work page 2022

  2. [2]

    A. Acin, I. Bloch, H. Buhrman, T. Calarco, C. Eichler, J. Eisert, J. Esteve, N. Gisin, S. J. Glaser, F. Jelezko, S. Kuhr, M. Lewenstein, M. F. Riedel, P. O. Schmidt, R. Thew, A. Wallraff, I. Walmsley, and F. K. Wilhelm. The European quantum technologies roadmap . New J. Phys. , 20:080201, 2018

    work page 2018

  3. [3]

    Arnon, Z

    R. Arnon, Z. Brakerski, and T. Vidick. Computational entanglement theory, 2023

    work page 2023

  4. [4]

    Avidan and R

    N. Avidan and R. Arnon. Quantum computational unpredictability entropy and quantum leakage resilience, 2025

    work page 2025

  5. [5]

    Avidan, T

    N. Avidan, T. A. Hahn, J. M. Renes, and R. Arnon. Fully quantum computational entropies, 2025

    work page 2025

  6. [6]

    Bansal, W.-K

    N. Bansal, W.-K. Mok, K. Bharti, D. E. Koh, and T. Haug. Pseudorandom density matrices. PRX Quantum , 6(2), May 2025

    work page 2025

  7. [7]

    Barak, R

    B. Barak, R. Shaltiel, and A. Wigderson. Computational Analogues of Entropy . In G. Goos, J. Hartmanis, J. Van Leeuwen, S. Arora, K. Jansen, J. D. P. Rolim, and A. Sahai, editors, Approximation, Randomization , and Combinatorial Optimization .. Algorithms and Techniques , volume 2764, pages 200--215. Springer Berlin Heidelberg, Berlin, Heidelberg, 2003. S...

    work page 2003

  8. [8]

    Barenco, C

    A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo , N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter. Elementary gates for quantum computation. Phys. Rev. A , 52(5):3457--3467, 1995

    work page 1995

  9. [9]

    C. H. Bennett, G. Brassard, C. Cr\'epeau, R. Jozsa, A. Peres, and W. K. Wootters. Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels . Phys. Rev. Lett. , 70:1895--1899, Mar 1993

    work page 1993

  10. [10]

    C. H. Bennett and S. J. Wiesner. Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states . Phys. Rev. Lett. , 69:2881--2884, Nov 1992

    work page 1992

  11. [11]

    Chen, K.-M

    Y.-H. Chen, K.-M. Chung, C.-Y. Lai, S. P. Vadhan, and X. Wu. Computational notions of quantum min-entropy, 2017

    work page 2017

  12. [12]

    Computational Notions of Quantum Min-Entropy

    Y.-H. Chen, K.-M. Chung, C.-Y. Lai, S. P. Vadhan, and X. Wu. Computational Notions of Quantum Min - Entropy , Oct. 2017. arXiv:1704.07309

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  13. [13]

    T. M. Cover and J. A. Thomas. Elements of information theory . Wiley series in telecommunications. Wiley, 1991

    work page 1991

  14. [14]

    C. M. Dawson and M. A. Nielsen. The solovay–kitaev algorithm. Quantum Information and Computation , 6(1):81--95, 2006

    work page 2006

  15. [15]

    Dehaene and B

    J. Dehaene and B. De Moor. Clifford group, stabilizer states, and linear and quadratic operations over GF (2). Phys. Rev. A , 68(4):042318, 2003

    work page 2003

  16. [16]

    D. Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer . Proc. Roy. Soc. A , 400:97--117, 1985

    work page 1985

  17. [17]

    Dziembowski and K

    S. Dziembowski and K. Pietrzak. Leakage- Resilient Cryptography in the Standard Model , 2008. Publication info: Published elsewhere. Unknown where it was published

    work page 2008

  18. [18]

    K. Fang, X. Wang, M. Tomamichel, and R. Duan. Non-asymptotic entanglement distillation. IEEE Trans. Inform. Theory , 65(10):6454--6465, 2019

    work page 2019

  19. [19]

    R. P. Feynman. Quantum mechanical computers. Found. Phys. , 16:507--531, 1986

    work page 1986

  20. [20]

    Fuller, A

    B. Fuller, A. O'Neill, and L. Reyzin. A Unified Approach to Deterministic Encryption : New Constructions and a Connection to Computational Entropy , 2012. Publication info: A major revision of an IACR publication in TCC 2012

    work page 2012

  21. [21]

    Gottesman

    D. Gottesman. Theory of fault-tolerant quantum computation. Phys. Rev. A , 57(1):127--137, 1998

    work page 1998

  22. [22]

    The primes contain arbitrarily long arithmetic progressions

    B. Green and T. Tao. The primes contain arbitrarily long arithmetic progressions, Sept. 2007. arXiv:math/0404188

    work page internal anchor Pith review Pith/arXiv arXiv 2007

  23. [23]

    A. Gu, L. Leone, S. Ghosh, J. Eisert, S. F. Yelin, and Y. Quek. Pseudomagic quantum states. Phys. Rev. Lett. , 132:210602, May 2024

    work page 2024

  24. [24]

    A. Gu, Y. Quek, S. Yelin, J. Eisert, and L. Leone. Simulating quantum chaos without chaos, 2024

    work page 2024

  25. [25]

    Haitner, O

    I. Haitner, O. Reingold, S. Vadhan, and H. Wee. Inaccessible Entropy I : Inaccessible Entropy Generators and Statistically Hiding Commitments from One - Way Functions , Aug. 2021. arXiv:2010.05586

    work page arXiv 2021

  26. [26]

    He, M.-X

    Y. He, M.-X. Luo, E. Zhang, H.-K. Wang, and X.-F. Wang. Decompositions of n-qubit toffoli gates with linear circuit complexity. Int J Theor Phys , 56(7):2350--2361, 2017

    work page 2017

  27. [27]

    A. S. Holevo. Bounds for the quantity of information transmitted by a quantum communication channel. Prob. Inf. Tr. , 9:177, 1973

    work page 1973

  28. [28]

    Hsiao, C.-J

    C.-Y. Hsiao, C.-J. Lu, and L. Reyzin. Conditional Computational Entropy , or Toward Separating Pseudoentropy from Compressibility . In Advances in Cryptology - EUROCRYPT 2007 , volume 4515. Springer Berlin Heidelberg, Berlin, Heidelberg, 2007

    work page 2007

  29. [29]

    Håstad, R

    J. Håstad, R. Impagliazzo, L. A. Levin, and M. Luby. A Pseudorandom Generator from any One -way Function . SIAM Journal on Computing , 28(4):1364--1396, Jan. 1999

    work page 1999

  30. [30]

    Impagliazzo

    R. Impagliazzo. Hard-core distributions for somewhat hard problems. In Proceedings of IEEE 36th Annual Foundations of Computer Science , pages 538--545, 1995

    work page 1995

  31. [31]

    B. J., Y. Efron, T. Metger, A. Poremba, L. Qian, and H. Yuen. Unitary complexity and the Uhlmann transformation problem . 2015

    work page 2015

  32. [32]

    Khatri and M

    S. Khatri and M. M. Wilde. Principles of quantum communication theory: A modern approach, 2024

    work page 2024

  33. [33]

    Leone, J

    L. Leone, J. Rizzo, J. Eisert, and S. Jerbi. Entanglement theory with limited computational resources, 2025

    work page 2025

  34. [34]

    O. B. Lupanov. Ob odnom métodé sintéza shém (on a method of circuit synthesis). Izvéstiá vysših učébnyh zavédénij, Radiofizika , 1:120–140, 1958

    work page 1958

  35. [35]

    A. A. Mele. Introduction to haar measure tools in quantum information: A beginner's tutorial. Quantum , 8:1340, 2024

    work page 2024

  36. [36]

    Mosonyi and F

    M. Mosonyi and F. Hiai. Test-measured rényi divergences. IEEE Trans. Inform. Theory , 69(2):1074--1092, 2023

    work page 2023

  37. [37]

    Munson, N

    A. Munson, N. B. T. Kothakonda, J. Haferkamp, N. Yunger Halpern, J. Eisert, and P. Faist. Complexity-constrained quantum thermodynamics. PRX Quantum , 6(1):010346, 2025

    work page 2025

  38. [38]

    M. A. Nielsen and I. L. Chuang. Quantum computation and quantum information . Cambridge Series on Information and the Natural Sciences. Cambridge University Press, 2000

    work page 2000

  39. [39]

    O'Donnell and R

    R. O'Donnell and R. Venkateswaran. The quantum union bound made easy, 2021

    work page 2021

  40. [40]

    O'Donnell and J

    R. O'Donnell and J. Wright. Efficient quantum tomography, 2015

    work page 2015

  41. [41]

    Pirandola, U

    S. Pirandola, U. L. Andersen, L. Banchi, M. Berta, D. Bunandar, R. Colbeck, D. Englund, T. Gehring, C. Lupo, C. Ottaviani, J. Pereira, M. Razavi, J. S. Shaari, M. Tomamichel, V. C. Usenko, G. Vallone, P. Villoresi, and P. Wallden. Advances in quantum cryptography. Adv. Opt. Photon. , 12:1012--1236, 2020

    work page 2020

  42. [42]

    Pirandola, U

    S. Pirandola, U. L. Andersen, L. Banchi, M. Berta, D. Bunandar, R. Colbeck, D. Englund, T. Gehring, C. Lupo, C. Ottaviani, J. L. Pereira, M. Razavi, J. Shamsul Shaari, M. Tomamichel, V. C. Usenko, G. Vallone, P. Villoresi, and P. Wallden. Advances in quantum cryptography. Adv. Opt. Phot. , 12(4):1012, Dec. 2020

    work page 2020

  43. [43]

    Preskill

    J. Preskill. Quantum computing and the entanglement frontier. Bull. Am. Phys. Soc. , 58, 2013

    work page 2013

  44. [44]

    E. Rains. A semidefinite program for distillable entanglement. 47(7):2921--2933, 2001

    work page 2001

  45. [45]

    E. M. Rains. Bound on distillable entanglement. Phys. Rev. A , 60(1):179--184, 1999

    work page 1999

  46. [46]

    Rubinfeld

    R. Rubinfeld. Lecture 25: One‑way permutations and pseudorandom generators. Lecture notes, 6.842 Randomness and Computation, MIT, 2012

    work page 2012

  47. [47]

    C. E. Shannon. A mathematical theory of communication. 27(3):379--423, 1948

    work page 1948

  48. [48]

    Tomamichel

    M. Tomamichel. Quantum Information Processing with Finite Resources -- Mathematical Foundations , volume 5. 2016

    work page 2016

  49. [49]

    van den Berg

    E. van den Berg. A simple method for sampling random clifford operators, 2021

    work page 2021

  50. [50]

    J. Watrous. The Theory of Quantum Information . Cambridge University Press, 1 edition, 2018

    work page 2018

  51. [51]

    H. Wee. On pseudoentropy versus compressibility. In Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004. , pages 29--41, 2004. ISSN : 1093-0159

    work page 2004

  52. [52]

    M. M. Wilde. Quantum information theory. 2013

    work page 2013

  53. [53]

    M. M. Wilde. Second law of entanglement dynamics for the non-asymptotic regime. In 2021 IEEE Information Theory Workshop ( ITW ) , pages 1--6, 2021

    work page 2021

  54. [54]

    Y \'a ng \"u ez, T

    \'A . Y \'a ng \"u ez, T. A. Hahn, and J. Kochanowski. Efficient quantum measurements: Computational max- and measured rényi divergences and applications. In preparation , 2025

    work page 2025

  55. [55]

    A. C. Yao. Theory and application of trapdoor functions. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science , SFCS '82, page 80–91, USA, 1982. IEEE Computer Society

    work page 1982

  56. [56]

    A. C. Yao. Computational information theory. In Y. S. Abu-Mostafa, editor, Complexity in Information Theory , pages 1--15. Springer, 1988

    work page 1988

  57. [57]

    H. Zhao, L. Lewis, I. Kannan, Y. Quek, H.-Y. Huang, and M. C. Caro. Learning quantum states and unitaries of bounded gate complexity. PRX Quantum , 5(4):040306, 2024

    work page 2024