A Sum-of-Squares Hierarchy with Quadratic Convergence for Quantum Channel Coding

• URL: http://arxiv.org/abs/2609.09629v1
• Date: Wed, 09 Sep 2026 02:40:37 GMT
• Title: A Sum-of-Squares Hierarchy with Quadratic Convergence for Quantum Channel Coding
• Abstract summary: An existing programming hierarchy based on symmetric extensions provides convergent upper bounds with an a priori error estimate that decays as the inverse square root of the extension level.<n>We construct a Hermitian sum-of-squares hierarchy for an arbitrary number of messages and prove quadratic convergence in its level.<n>For binary messages, the resulting bounds give a multiplicative approximation from above of the trace-norm-norm coefficient.
• Score: 0.8594140167290097
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Computing the optimal success probability for transmitting classical messages through a single use of a quantum channel is NP-hard, even for two messages. An existing semidefinite programming hierarchy based on symmetric extensions provides convergent upper bounds with an a priori error estimate that decays as the inverse square root of the extension level. In this work, we construct a Hermitian sum-of-squares hierarchy for an arbitrary number of messages and prove quadratic convergence in its level. The error bound is proportional to the advantage over random guessing. Our approach combines state-discrimination duality with positive polynomial kernels on products of spheres to construct feasible polynomial dual certificates. For binary messages, the resulting bounds give a multiplicative approximation from above of the trace-norm contraction coefficient.

Related papers

• Fixed points in de Finetti hierarchies [0.0]
  We study de Finetti hierarchies in which the feasible states are constrained to be fixed points of quantum channels.<n>We derive several de Finetti theorems, including a double-sided extension theorem with $Oleft(sqrtlog n/nright)$ convergence.<n>Exploiting Schur-Weyl duality and Gelfand-Tsetlin, we show that the rounding scheme producing certifiably good separable inner approximations can be implemented in time in $1/$ for fixed local dimensions.
  arXiv  Detail & Related papers  (2026-07-26T14:35:48Z)
• Entanglement Quantification via Symmetric Extensions: A Resource Theory Hierarchy [3.662037602213926]
  We introduce a hierarchy of entanglement measures Ek based on k-symmetric PPT extensions.<n>Each Ek, defined via a minimal eigenvalue shift, is faithful, convex, and monotone under free operations.<n>The hierarchy strictly refines PPT-robustness at k = 1, detects bound entanglement at k = 2, and converges exactly to the separability measure as k -> infinity.
  arXiv  Detail & Related papers  (2026-07-18T20:39:35Z)
• Hysteretic squashed entanglement in many-body quantum systems [42.085941481155295]
  Entanglement in many-body quantum systems is distributed across spatial regions.<n>We propose hysteretic entanglement $T_sq$, a conditional entanglement that measures the genuine quantum correlations between two subregions.<n>We show that $T_sq$ can detect genuine quantum correlations across both adjacent and long-range subsystems.
  arXiv  Detail & Related papers  (2026-03-10T17:00:49Z)
• Polynomial-time certification of fidelity for many-body mixed states and mixed-state universality classes [23.9304612104967]
  We introduce a-time algorithm to compute certified lower and upper bounds for fidelity between matrix product density operators.<n>Our results offer an exponential improvement in precision over known moment-based bounds.
  arXiv  Detail & Related papers  (2026-01-19T19:13:28Z)
• A Posteriori Certification Framework for Generalized Quantum Arimoto-Blahut Algorithms [41.15017547767954]
  We introduce an a posteriori certification viewpoint for the generalized quantum Arimoto-Blahut (QAB) algorithm.<n>We prove a global convergence theorem showing that, under convexity and a substantially weaker numerically verifiable condition, the QAB iteration converges to the global minimizer.<n>As an application, we develop a certified iterative scheme for computing the quantum relative entropy of channels.
  arXiv  Detail & Related papers  (2026-01-14T09:10:41Z)
• Error exponents of quantum state discrimination with composite correlated hypotheses [40.82628972269358]
  We study the error exponents in quantum hypothesis testing between two sets of quantum states.<n>We introduce and compare two natural extensions of the quantum Hoeffding divergence and anti-divergence to sets of quantum states.
  arXiv  Detail & Related papers  (2025-08-18T13:04:06Z)
• A Unified Approach to Quantum Contraction and Correlation Coefficients [10.128808054306187]
  We introduce a family of non-commutative $L2(p)$ spaces induced by operator monotone functions.<n>We identify families of quantum maximal correlation coefficients and the quantum $chi2$-divergences.
  arXiv  Detail & Related papers  (2025-05-21T08:58:45Z)
• Quantum Lifting for Invertible Permutations and Ideal Ciphers [47.33103206862089]
  We derive the first lifting theorems for establishing security in the quantum random permutation and ideal cipher models.<n>These theorems relate the success probability of an arbitrary quantum adversary to that of a classical algorithm making only a small number of classical queries.
  arXiv  Detail & Related papers  (2025-04-25T09:07:55Z)
• Barycentric bounds on the error exponents of quantum hypothesis exclusion [7.812210699650153]
  We study the optimal error probability of quantum state exclusion from an information-theoretic perspective.<n>We extend our analysis to the more complicated task of quantum channel exclusion.
  arXiv  Detail & Related papers  (2024-07-18T17:27:36Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• 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)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
  arXiv  Detail & Related papers  (2021-07-13T12:31:06Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
  arXiv  Detail & Related papers  (2019-09-04T11:46:26Z)

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.