Deterministic Minimum-Output-Entropy Nonadditivity via Haagerup's Inequality and Near-Free Permutation Representations

• URL: http://arxiv.org/abs/2608.31081v1
• Date: Mon, 31 Aug 2026 16:53:42 GMT
• Title: Deterministic Minimum-Output-Entropy Nonadditivity via Haagerup's Inequality and Near-Free Permutation Representations
• Abstract summary: We give a realization of the finite-dimensional quadratic certificate underlying Collins's mixed-unitary proof of minimum-output-entropy nonadditivity.
• Score: 6.9022592726569085
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give a deterministic realization of the finite-dimensional quadratic certificate underlying Collins's mixed-unitary proof of minimum-output-entropy nonadditivity. For every fixed integer $K\ge 2$ and rational $η>0$ satisfying $\log K>2(3+η)^2$, a deterministic polynomial-time algorithm, for every sufficiently large target size $N$, outputs $K$ permutations on $N'=N+o_{K,η}(N)$ points. Restricting their permutation matrices to the nontrivial standard representation yields real orthogonal Stinespring blocks and a channel $Φ_{N'}:M_{N'-1}(\mathbb{C})\to M_K(\mathbb{C})$ such that \[ 2H_{\min}(Φ_{N'}) -H_{\min}(Φ_{N'}^{\otimes 2}) \ge \frac{\log K}{K} -2\log\left(1+\frac{(3+η)^2}{K}\right) >0. \] The construction combines Haagerup's length-two inequality with the simultaneous deterministic spectral approximation of O'Donnell and Wu. We further show that the constant $3$ is asymptotically sharp on the relevant Hermitian zero-diagonal coefficient class and that the finite spectral transfer is nearly saturated, thereby isolating the finer geometry of the full output body as the natural next level of refinement beyond the scalar-radius method. Finally, a standard covariant extension converts the same deterministic entropy gap exactly into self-tensor superadditivity of the one-shot Holevo quantity.

Related papers

• Exact quantum splitting and the structure of finite algebras [1.7277199466514768]
  Berlekamp's algorithm factors a squarefree $finmathbbF_q[x]$ by deterministic linear algebra.<n>We give an unconditional exact quantum implementation in a circuit model permitting single-qubit rotations through efficiently computable angles.
  arXiv  Detail & Related papers  (2026-08-31T06:56:14Z)
• Research Report on Noise-Shaped One-Bit Coefficients in Discrete Polynomial Fourier Extension [0.0]
  This report studies noise-shaped one-bit coefficients in normalized discrete Fourier extension.<n>For first-order Sigma- quantization, the error is written as $e_k=u_k-q_k=v_k$ with a uniformly bounded state.<n>For the parabolic $_x,t()=x+t2$, the bound is expressed through $J(x,t)=int_01 |x+2t|d$, and the uniform $N-1$ rate is shown to be sharp.
  arXiv  Detail & Related papers  (2026-07-26T21:51:41Z)
• Exponential Reduction of Mesh Dependence in Quantum Estimation of Parabolic PDE Observables [3.3636842548621275]
  We develop a quantum PDE algorithm that estimates linear and quadratic observables and places fine-coarse cancellation inside the circuit before measurement.<n>We also give a non-Fourier realization based on energyorthogonal dyadic midpoint details in one dimension.
  arXiv  Detail & Related papers  (2026-07-20T16:09:24Z)
• Tikhonov-regularised projected gradient flow for equality-constrained bilinear quantum control [0.0]
  We study a projection-type gradient flow for equality-constrained control objective on $mathcalH=L(0,T;mathbbR)$.<n>We replace $$ with $_varepsilon:=+varepsilon2I$ and prove: (i) an exact spectral identity giving $(_varepsilon)=(_min2+varepsilon2)$; (ii) objective monotonicity $mathrmdJ/
  arXiv  Detail & Related papers  (2026-04-29T12:53:58Z)
• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  We study entrywise scalar quantization of two matrices prior to multiplication.<n>We obtain a closed-form optimal point density [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X,, and prove a correlation-driven phase transition.
  arXiv  Detail & Related papers  (2026-03-20T01:53:44Z)
• The Spectral Dimension of NTKs is Constant: A Theory of Implicit Regularization, Finite-Width Stability, and Scalable Estimation [0.0]
  We prove a constant-limit law $lim_ntoinfty mathbbE[r_texteff(K_n)] = mathbbE[k(x, x)]2.<n>We further establish finite-width stability: if the finite-width NTK deviates in operator norm by $O_p(m-1/2)$, then $r_texteff$ changes by $O_p(m-1/2)$.<n>We design a scalable estimator using random
  arXiv  Detail & Related papers  (2025-11-30T12:14:21Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  We study the problem of clustering $T$ trajectories of length $H$, each generated by one of $K$ unknown ergodic Markov chains over a finite state space of size $S$.<n>We derive an instance-dependent, high-probability lower bound on the clustering error rate, governed by the weighted KL divergence between the transition kernels of the chains.<n>We then present a novel two-stage clustering algorithm.
  arXiv  Detail & Related papers  (2025-06-02T05:10:40Z)
• Overcomplete Tensor Decomposition via Koszul-Young Flattenings [56.82556231289414]
  We give a new algorithm for decomposing an $n_times n times n_3$ tensor as the sum of a minimal number of rank-1 terms.<n>We show that an even more general class of degree-$d$s cannot surpass rank $Cn$ for a constant $C = C(d)$.
  arXiv  Detail & Related papers  (2024-11-21T17:41:09Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  We show a new way to relate functions on the hypergrid to their harmonic extensions over the polytorus. We show the supremum of a function $f$ over products of the cyclic group $exp(2pi i k/K)_k=1K$. We extend to new spaces a recent line of work citeEI22, CHP, VZ22 that gave similarly efficient methods for learning low-degrees on hypercubes and observables on qubits.
  arXiv  Detail & Related papers  (2023-01-04T04:15:40Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  "Statistical-computational gaps" occur in many statistical inference tasks. We consider a model for random order-3 decomposition where one component is slightly larger in norm than the rest. We show that tensor entries can accurately estimate the largest component when $ll n3/2$ but fail to do so when $rgg n3/2$.
  arXiv  Detail & Related papers  (2022-11-10T00:40:37Z)

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.