Source-linked AI summary
Submodularity of entropy under quantum convolution
Milad M. Goodarzi
TL;DR
Classical entropic additive combinatorics uses submodularity to organize entropy growth, but quantum convolution requires comparing distinct output states and lacks a general classical input-entropy bound. This paper constructs compatible globally weighted quantum convolutions and proves that their entropy gains admit a submodular extension. The resulting framework yields quantum entropy inequalities, including sharp repeated-input growth bounds.
Problem
Quantum convolution can increase entropy even for pure inputs, and ordinary strong subadditivity does not compare the distinct convolution states needed to establish the conjectured inequalities.
Source: §1 · p. 2Method
The authors construct compatible globally weighted convolution families and represent their entropy gains through a submodular extension relative to a fixed admissible input block.
Source: §1 · p. 2, §6 · p. 17Results
The quantum doubling constant bounds multiplicative entropy growth for admissible m-fold convolutions by δq[ρ]^(m−1), and this exponent is optimal even for computational-basis-diagonal states.
Source: §1.1 · p. 3Takeaways & Limitations
The shared submodular structure yields convolutional strong subadditivity, the quantum Ruzsa triangle inequality, and entropic Plünnecke–Ruzsa inequalities for arbitrary input states.
Source: §5.2 · p. 14, §5.3 · p. 15, §6 · p. 17The main theorem does not automatically recover Tao’s difference-based triangle inequality because its three difference terms cannot arise from one assignment of global signs to the inputs.
Source: §5.2 · p. 14
Abstract
from arXiv · showhide
We develop a submodular framework for the von Neumann entropy of discrete quantum convolutions, providing a noncommutative counterpart to the direct side of entropic additive combinatorics. We first introduce globally weighted quantum convolutions, which form compatible families indexed by admissible subsets of a fixed collection of inputs. Our main theorem reveals a polymatroidal geometry underlying their entropy growth: relative to any fixed admissible input block, the entropy gains admit a normalized, monotone, submodular extension to all subsets of the remaining inputs. The theorem yields convolutional strong subadditivity, quantum Ruzsa triangle inequality, and quantum entropic Pl\"unnecke--Ruzsa inequalities for arbitrary input states. For repeated inputs, it gives sharp comparisons of entropy growth across admissible scales; in particular, the quantum doubling constant controls all higher admissible convolution entropies with optimal exponents. Together, these results bring submodular methods from additive combinatorics into the quantum setting and provide a systematic route to broad families of convolutional entropy inequalities.
1 Introduction
The paper transfers the entropy method of additive combinatorics to discrete quantum convolution, where output entropies do not obey the classical input-entropy bound and ordinary strong subadditivity does not compare different convolution states. It constructs compatible globally weighted convolutions, proves their entropy gains have a submodular extension, and derives several entropy inequalities from that structure.
1 Introduction
- Classical entropy methods organize additive growth through submodularity, but quantum convolution lacks a general input-entropy bound and direct strong subadditivity does not compare different convolution states.Earlier verifications of the conjectured inequalities were limited to stabilizer inputs and states diagonal in the computational basis [3].Source: §1 · pp. 1–2
1.1 Main results
- Fixed global weights, normalized separately on admissible subsets, produce compatible multi-input convolution families, including some unavailable through successive admissible binary convolutions.The construction extends the binary framework of [2] [4].Source: §1.1 · p. 2, §1 · p. 2
- Relative to any fixed nonempty admissible block, entropy gains extend to a normalized, monotone, submodular function on all subsets of remaining inputs, including subsets whose physical convolution is undefined.This structure yields bounds on the gain from adding all inputs by the sum of their individual gains.Source: §1.1 · pp. 2–3
- Three-input consequences include convolutional strong subadditivity and the quantum Ruzsa triangle inequality, resolving Conjectures 2 and 1 of [3] for arbitrary quantum states under their respective coefficient conditions.The higher-input results include entropic Plünnecke–Ruzsa inequalities and sharp comparisons across admissible repeated-input scales.Source: §1.1 · p. 3
1.2 Proof method
- A characteristic-kernel representation places the convolutions in one auxiliary state whose marginal entropies transfer ordinary strong subadditivity to the full family.The proof also uses entropy-preserving kernel identities and a separable auxiliary state.Source: §1.2 · p. 3
2 Preliminaries
The preliminaries fix the discrete phase-space and Weyl conventions used to define quantum convolution. Convolution applies a discrete beam-splitter unitary to two states and discards one output, with admissible coefficients chosen in the finite field.
2 Preliminaries
2.1 Weyl operators and characteristic functions
- Weyl operators form an orthonormal operator basis, and the state characteristic function is its Fourier transform, with projective phases requiring a quantum positive-definiteness criterion.The phase-space vectors lie in V^n and the Weyl representation is projective.Source: §2.1 · p. 4
2.2 Discrete quantum convolution
- For an admissible pair satisfying s^2 + t^2 = 1, quantum convolution applies a discrete beam-splitter unitary to two states and discards the second output.Its characteristic function obeys the convolution multiplication identity; multi-input bracketing and coefficients are specified explicitly because fixed-pair convolution is not assumed associative.Source: §2.2 · p. 5
3 The characteristic-kernel method
The characteristic-kernel method converts quantum convolution into entrywise kernel multiplication and relates kernel entropy to state entropy. These identities yield compatible globally weighted convolutions and support the paper's common auxiliary-state proof strategy.
3 The characteristic-kernel method
- Quantum convolution becomes entrywise multiplication of characteristic kernels, whose normalized form has the same nonzero spectrum as the state up to fixed multiplicity and an entropy shift of log D.The characteristic kernel includes a phase needed for positivity.Source: §3 · p. 5, §3.2 · p. 8
3.1 Globally weighted convolutions
- For each admissible subset, fixed global input weights normalized by a square root of their squared-weight sum define a unique convolution state and a compatible family.Each state has a channel realization, while changing the square-root sign changes the state by parity without changing entropy.Source: §3.1 · pp. 6–7
3.2 Entropy of the normalized kernel
- The normalized characteristic kernel is a density matrix whose eigenvalues are those of the input state divided by D, each repeated D times.This gives the kernel entropy as the state entropy plus log D.Source: §3.2 · pp. 8–9
4 Submodularity of quantum convolution entropy
For compatible families of globally weighted quantum convolutions, entropy gains relative to a fixed admissible input block extend to a normalized, monotone, submodular function on all subsets of the remaining inputs. This polymatroidal structure supports fractional-cover entropy inequalities for arbitrary density operators.
Main theorem
- Relative to any fixed nonempty admissible block R, the physical entropy gains extend to a normalized, monotone, submodular function on the full subset lattice of remaining inputs.The extension is defined even where the corresponding physical convolution is not.Source: §4 · pp. 9–10
Consequences
- For arbitrary density operators, singleton-cover and repeated-input bounds give quantum entropy-growth counterparts of the Plünnecke–Ruzsa principle [11] [14].For diagonal inputs, compatible convolutions reduce to ordinary weighted sums of independent variables; the finite-field square condition applies to the quantum normalization, not those classical sums.Source: §4 · p. 10
Proof
- The proof constructs an auxiliary state whose marginals exist for every input subset, then uses strong subadditivity for submodularity and separability for monotonicity.For admissible subsets, the auxiliary marginals have the same entropy as the convolution outputs up to a common log D shift.Source: §4 · pp. 10–11
Fractional-cover inequalities
- Fractional-cover bounds follow by applying diminishing returns to the extension and summing under the cover condition for the displayed admissible subsets.The argument uses intermediate auxiliary-state marginals even when they have no physical convolution interpretation.Source: §4 · pp. 9, 12
Cancellation rule
- A general cancellation rule transfers suitable inequalities for auxiliary marginals to convolution entropies when the coefficients cancel their common log D shift.This coefficient-sum condition is distinct from balance of binary convolution coefficients and from variable-by-variable balance in classical information inequalities.Source: §4 · p. 12
5 Entropy inequalities from submodularity
Submodularity of a shared auxiliary entropy function yields strong-subadditivity and triangle inequalities, fractional-cover growth bounds, and sharp comparisons across repeated-input scales. Each result applies under its stated admissibility conditions, which differ across the four subsections.
5.1 Convolutional strong subadditivity
- For admissible subset quadruples, convolution entropy is monotone and submodular, with the submodularity deficit equal to a conditional mutual information.The resulting diminishing-returns law compares the entropy gain from adding an input before and after another input is included.Source: §5.1 · p. 12
- For nested binary convolutions, weighted convolutional strong subadditivity holds for arbitrary states when the admissible coefficients satisfy lbt = ms.This condition is sufficient, not asserted necessary; the result includes unequal-coefficient choices such as the stated Z23 example.Source: §5.1 · p. 13
5.2 Quantum Ruzsa triangle inequality
- Under 2s^2 = 1, arbitrary states satisfy the quantum Ruzsa triangle inequality, without requiring a balanced three-input normalization.Over Z7, the triangle inequality applies even though the coefficient conditions for convolutional strong subadditivity cannot be instantiated.Source: §5.2 · p. 14
- The symmetrized quantum Ruzsa divergence obeys the same triangle inequality, but is generally positive on the diagonal and is not a metric.Its triangle-deficit expression follows from the deficit in the convolutional entropy inequality.Source: §5.2 · pp. 13–14
5.3 Quantum Plünnecke–Ruzsa inequalities
- Fractional-cover bounds control full convolution entropy growth from smaller-subset gains, with each inequality requiring only its displayed subsets to be admissible.If |M| = r and each singleton gain is at most log K, then κ_R(M) ≤ K^r, subject to the displayed endpoint normalizations.Source: §5.3 · p. 15
5.4 Repeated inputs and optimal coefficients
- For balanced binary convolution, every m = 2r is admissible, while other grouping schemes require tracking their coefficients.The fixed-pair iterate is not generally identified with the normalized convolution C[m](ρ).Source: §5.4 · p. 16
- For every fixed odd prime d and admissible integers 2 ≤ ℓ ≤ m, the factor (m−1)/(ℓ−1) in (5.27) cannot be replaced by any smaller universal factor, even for one-qudit diagonal states.Source: §5.4 · p. 16
- The sharp repetition-scale factor is witnessed by one-qudit diagonal states whose small-ε entropy grows as jε log(1/ε) at scale j.The proof uses independent Bernoulli inputs and requires the relevant repetition counts to be admissible.Source: §5.4 · p. 17
6 Conclusion
A characteristic-kernel construction places compatible quantum convolutions in a common entropy space, where ordinary strong subadditivity produces a submodular extension of physical entropy gains. The resulting direct-growth theory does not yet extract inverse structure from small quantum convolutional entropy growth.
6 Conclusion
- A separable auxiliary state reproduces physical convolution entropies up to explicit constants, enabling a normalized, monotone, submodular extension of entropy gains.The extension is defined relative to any fixed nonempty admissible input block, including subsets whose corresponding physical convolution is undefined.Source: §6 · p. 17
- This direct-growth framework yields convolutional strong subadditivity, the quantum Ruzsa triangle inequality, and the direct Plünnecke–Ruzsa hierarchy.The common construction relies on independent input registers, consistent inherited weights, and admissible-subset normalizations.Source: §6 · p. 17
- Whether small quantum convolutional entropy growth yields inverse structure related to stabilizer structure and magic remains an open direction.The characteristic-kernel method does not capture the additional additive structure used by inverse developments.Source: §6 · p. 17