Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2611.10827

Quantum channel bounds for constant-composition codes

A. R. Akhiiarov, Peter Boyvalenkov, Danila Dmitrievich Cherkashin, Andrei Raigorodskii

Published Nov 7, 2026• 0 citations
arXivHTMLPDF

Abstract

We extend the quantum-channel optimization of Alrabiah and Guruswami to $q$-ary constant-composition codes. We study explicit channel and flag constructions that recover selected classical asymptotic upper bounds, including the Ben-Haim--Litsyn, moving-subspace and Horn-channel bounds. We give two equivalent formulations, Gram and flag, and prove stability of the obtained upper bounds under permutation transport and generalized shortening. A hierarchy defined by bounding the output-state ranks within each flag improves strictly between consecutive levels at every composition and every positive distance below the Plotkin threshold. We provide finite matrix parametrizations of these bounds (i.e., the number of variables does not depend on the length of codes under consideration). Numerical optimization rapidly produces improvements over the known asymptotic upper bounds throughout all tested nonbinary parameter ranges. For rational input data, each finite level admits near-optimal feasible rational descriptions of polynomial length. Their feasibility can be checked exactly and their objective values computed to any prescribed accuracy in polynomial time; the associated threshold problem with a prescribed gap belongs to $\mathsf{PromiseNP}$.

DOI
10.48550/arxiv.2611.10827

Related papers

Binary code rate bounds via classical--quantum channels

Omar Alrabiah, Venkatesan Guruswami

We derive the four principal asymptotic rate-distance tradeoffs for binary codes---Plotkin, Elias--Bassalygo, and the two McEliece--Rodemich--Rumsey--Welch (MRRW) bounds---from one theorem, the ``pretty good criterion.'' If the bit error rate under the pretty good measurement (PGM)---the quantum analog of posterior sampling---of a binary-input output-symmetric classical--quantum (cq) channel lies below $δ$, then every length-$n$ binary code, linear or nonlinear, of relative distance $δ$ has rate at most the channel's capacity, up to an $O(n^{-1/2})$ correction. Rate--distance bounds thereby reduce to a channel design problem, wherein the task is to minimize channel capacity subject to the posterior bit error rate constraint. Via the pretty good criterion, the binary erasure channel (BEC) yields Plotkin, the binary symmetric channel (BSC) yields Elias--Bassalygo, the pure-state channel (PSC) yields the first MRRW bound, and a masked PSC yields the second MRRW bound exactly. This framework is then instantiated with new channels to improve upon the MRRW bounds. Specifically, the mixed-qubit channel (MQC), a mixed-state version of PSC, strictly improves the first MRRW bound at every $0 < δ< \frac{1}{2}$, while the masked mixed-qubit channel (2MQC) strictly improves the second MRRW bound throughout the same interval.

cs.ITCross-listedarXiv:2608.09347•Aug 11, 2026•8 citations

Quantum Sphere-Packing Bounds With Polynomial Prefactors

Hao-Chung Cheng, Min-Hsiu Hsieh, Marco Tomamichel

We study lower bounds on the optimal error probability in classical coding over classical-quantum channels at rates below the capacity, commonly termed quantum sphere-packing bounds. Winter and Dalai have derived such bounds for classical-quantum channels; however, the exponents in their bounds only coincide when the channel is classical. In this paper, we show that these two exponents admit a variational representation and are related by the Golden-Thompson inequality, reaffirming that Dalai's expression is stronger in general classical-quantum channels. Second, we establish a finite blocklength sphere-packing bound for classical-quantum channels, which significantly improves Dalai's prefactor from the order of subexponential to polynomial. Furthermore, the gap between the obtained error exponent for constant composition codes and the best known classical random coding exponent vanishes in the order of o(logn/n), indicating our sphere-packing bound is almost exact in the high rate regime. Finally, for a special class of symmetric classical-quantum channels, we can completely characterize its optimal error probability without the constant composition code assumption. The main technical contributions are two converse Hoeffding bounds for quantum hypothesis testing and the saddle-point properties of error exponent functions.

arXiv:1704.05703•IEEE Transactions on Information Theory•Jan 8, 2019•53 citations

Convergence Without Finite Exactness in the Eigenstate Quantum Bootstrap

Ye Zhou, Daniel Keren

The eigenstate quantum-mechanical bootstrap can converge to the physical moment set while remaining nonexact at every finite order. We prove this for a one-dimensional quasi-exactly solvable sextic oscillator at explicitly known eigenvalues, including excited levels. At every finite order, the lower and upper bounds on $u^2$ remain strictly below and above its physical value, even after adjoining arbitrary finite polynomial Gram tests and all eigenstate-annihilator relations visible in the retained moment space. Hence neither side of the centered observable admits a finite sum-of-squares certificate modulo the eigenstate annihilator. The gap persists under any finite set of additional localizing constraints whose weights are strictly positive on polynomial vectors. We then prove convergence for polynomial Schrödinger operators satisfying explicit sum-of-squares confinement and derivative bounds. The eigenstate relations give moment estimates uniform in the truncation order; these yield a regular Schrödinger representation supported on the prescribed eigenspace. Finally, a four-mode extension combines this fixed-observable obstruction with feasible position moments having no positive representing measure at every finite order. At level three, this construction yields nonphysical feasible points with strictly positive definite moment matrices.

math-phCross-listedarXiv:2610.07775•Oct 7, 2026•1 citation

Pursuing the Fundamental Limits for Quantum Communication

Xin Wang

The quantum capacity of a noisy quantum channel determines the maximal rate at which we can code reliably over asymptotically many uses of the channel, and it characterizes the channel's ultimate ability to transmit quantum information coherently. In this paper, we derive single-letter upper bounds on the quantum and private capacities of quantum channels. The quantum capacity of a quantum channel is always no larger than the quantum capacity of its extended channels, since the extensions of the channel can be considered as assistance from the environment. By optimizing the parametrized extended channels with specific structures such as the flag structure, we obtain new upper bounds on the quantum capacity of the original quantum channel. Furthermore, we extend our approach to estimating the fundamental limits of private communication and one-way entanglement distillation. As notable applications, we establish improved upper bounds to the quantum and private capacities for fundamental quantum channels of interest in quantum information, some of which are also the sources of noise in superconducting quantum computing. In particular, our upper bounds on the quantum capacities of the depolarizing channel and the generalized amplitude damping channel are strictly better than previously best-known bounds for certain regimes.

arXiv:1912.00931•IEEE Transactions on Information Theory•Mar 24, 2021•24 citations

Quantum ordinal selection with two comparisons

Hongyu Wu

We study the optimal probability of selecting an object within a prescribed rank threshold using at most two noiseless coherent pairwise comparisons of an unknown strict order. Polynomial degree bounds alone can overestimate the success attainable with two comparisons. We develop a comparison-specific semidefinite model that completely characterizes attainable success. Computer-assisted proofs establish the exact optimum for every rank threshold at seven objects and for minimum selection at eight. For minimum selection, we construct an explicit algorithm family and determine its exact optimum. Bounds for all admissible two-comparison algorithms show that the family's asymptotic success is within 0.016% of the unrestricted optimum. We also prove that this relative gap has a strictly positive limit. The optimal quantum-to-classical success ratio for minimum selection converges to approximately 2.48 under the same two-comparison budget.

quant-pharXiv:2610.34762•Oct 27, 2026•0 citations

Sphere-packing bound for classical-quantum channels

Hao–Chung Cheng, Min-Hsiu Hsieh, Marco Tomamichel

We study lower bounds on the optimal error probability in channel coding at rates below capacity, commonly termed sphere-packing bounds. In this work, we establish a sphere-packing bound for classical-quantum channels, which significantly improves previous prefactor from the order of subexponential to polynomial. Furthermore, the gap between the obtained error exponent for constant composition codes and the best known classical random coding exponent vanishes in the order of o(log n/n), indicating our sphere-packing bound is almost exact in the high rate regime. The main technical contributions are two converse Hoeffding bounds for quantum hypothesis testing and the saddle-point properties of error exponent functions.

IEEE Information Theory Workshop (ITW)•Nov 1, 2017•1 citation
We extend the quantum-channel optimization of Alrabiah and Guruswami to qqq-ary constant-composition codes. We study explicit channel and flag constructions that recover selected classical asymptotic upper bounds, including the Ben-Haim--Litsyn, moving-subspace and Horn-channel bounds. We give two equivalent formulations, Gram and flag, and prove stability of the obtained upper bounds under permutation transport and generalized shortening. A hierarchy defined by bounding the output-state ranks within each flag improves strictly between consecutive levels at every composition and every positive distance below the Plotkin threshold. We provide finite matrix parametrizations of these bounds (i.e., the number of variables does not depend on the length of codes under consideration). Numerical optimization rapidly produces improvements over the known asymptotic upper bounds throughout all tested nonbinary parameter ranges. For rational input data, each finite level admits near-optimal feasible rational descriptions of polynomial length. Their feasibility can be checked exactly and their objective values computed to any prescribed accuracy in polynomial time; the associated threshold problem with a prescribed gap belongs to PromiseNP\mathsf{PromiseNP}PromiseNP.
We derive the four principal asymptotic rate-distance tradeoffs for binary codes---Plotkin, Elias--Bassalygo, and the two McEliece--Rodemich--Rumsey--Welch (MRRW) bounds---from one theorem, the ``pretty good criterion.'' If the bit error rate under the pretty good measurement (PGM)---the quantum analog of posterior sampling---of a binary-input output-symmetric classical--quantum (cq) channel lies below δδδ, then every length-nnn binary code, linear or nonlinear, of relative distance δδδ has rate at most the channel's capacity, up to an O(n−1/2)O(n^{-1/2})O(n−1/2) correction. Rate--distance bounds thereby reduce to a channel design problem, wherein the task is to minimize channel capacity subject to the posterior bit error rate constraint. Via the pretty good criterion, the binary erasure channel (BEC) yields Plotkin, the binary symmetric channel (BSC) yields Elias--Bassalygo, the pure-state channel (PSC) yields the first MRRW bound, and a masked PSC yields the second MRRW bound exactly. This framework is then instantiated with new channels to improve upon the MRRW bounds. Specifically, the mixed-qubit channel (MQC), a mixed-state version of PSC, strictly improves the first MRRW bound at every 0<δ<120 < δ< \frac{1}{2}0<δ<21​, while the masked mixed-qubit channel (2MQC) strictly improves the second MRRW bound throughout the same interval.
We study lower bounds on the optimal error probability in classical coding over classical-quantum channels at rates below the capacity, commonly termed quantum sphere-packing bounds. Winter and Dalai have derived such bounds for classical-quantum channels; however, the exponents in their bounds only coincide when the channel is classical. In this paper, we show that these two exponents admit a variational representation and are related by the Golden-Thompson inequality, reaffirming that Dalai's expression is stronger in general classical-quantum channels. Second, we establish a finite blocklength sphere-packing bound for classical-quantum channels, which significantly improves Dalai's prefactor from the order of subexponential to polynomial. Furthermore, the gap between the obtained error exponent for constant composition codes and the best known classical random coding exponent vanishes in the order of o(logn/n), indicating our sphere-packing bound is almost exact in the high rate regime. Finally, for a special class of symmetric classical-quantum channels, we can completely characterize its optimal error probability without the constant composition code assumption. The main technical contributions are two converse Hoeffding bounds for quantum hypothesis testing and the saddle-point properties of error exponent functions.
The eigenstate quantum-mechanical bootstrap can converge to the physical moment set while remaining nonexact at every finite order. We prove this for a one-dimensional quasi-exactly solvable sextic oscillator at explicitly known eigenvalues, including excited levels. At every finite order, the lower and upper bounds on u2u^2u2 remain strictly below and above its physical value, even after adjoining arbitrary finite polynomial Gram tests and all eigenstate-annihilator relations visible in the retained moment space. Hence neither side of the centered observable admits a finite sum-of-squares certificate modulo the eigenstate annihilator. The gap persists under any finite set of additional localizing constraints whose weights are strictly positive on polynomial vectors. We then prove convergence for polynomial Schrödinger operators satisfying explicit sum-of-squares confinement and derivative bounds. The eigenstate relations give moment estimates uniform in the truncation order; these yield a regular Schrödinger representation supported on the prescribed eigenspace. Finally, a four-mode extension combines this fixed-observable obstruction with feasible position moments having no positive representing measure at every finite order. At level three, this construction yields nonphysical feasible points with strictly positive definite moment matrices.
The quantum capacity of a noisy quantum channel determines the maximal rate at which we can code reliably over asymptotically many uses of the channel, and it characterizes the channel's ultimate ability to transmit quantum information coherently. In this paper, we derive single-letter upper bounds on the quantum and private capacities of quantum channels. The quantum capacity of a quantum channel is always no larger than the quantum capacity of its extended channels, since the extensions of the channel can be considered as assistance from the environment. By optimizing the parametrized extended channels with specific structures such as the flag structure, we obtain new upper bounds on the quantum capacity of the original quantum channel. Furthermore, we extend our approach to estimating the fundamental limits of private communication and one-way entanglement distillation. As notable applications, we establish improved upper bounds to the quantum and private capacities for fundamental quantum channels of interest in quantum information, some of which are also the sources of noise in superconducting quantum computing. In particular, our upper bounds on the quantum capacities of the depolarizing channel and the generalized amplitude damping channel are strictly better than previously best-known bounds for certain regimes.
We study the optimal probability of selecting an object within a prescribed rank threshold using at most two noiseless coherent pairwise comparisons of an unknown strict order. Polynomial degree bounds alone can overestimate the success attainable with two comparisons. We develop a comparison-specific semidefinite model that completely characterizes attainable success. Computer-assisted proofs establish the exact optimum for every rank threshold at seven objects and for minimum selection at eight. For minimum selection, we construct an explicit algorithm family and determine its exact optimum. Bounds for all admissible two-comparison algorithms show that the family's asymptotic success is within 0.016% of the unrestricted optimum. We also prove that this relative gap has a strictly positive limit. The optimal quantum-to-classical success ratio for minimum selection converges to approximately 2.48 under the same two-comparison budget.
We study lower bounds on the optimal error probability in channel coding at rates below capacity, commonly termed sphere-packing bounds. In this work, we establish a sphere-packing bound for classical-quantum channels, which significantly improves previous prefactor from the order of subexponential to polynomial. Furthermore, the gap between the obtained error exponent for constant composition codes and the best known classical random coding exponent vanishes in the order of o(log n/n), indicating our sphere-packing bound is almost exact in the high rate regime. The main technical contributions are two converse Hoeffding bounds for quantum hypothesis testing and the saddle-point properties of error exponent functions.