analiza aiqbench
This research establishes that approximating the trace norm contraction coefficient for quantum channels is NP-hard, highlighting a fundamental computational gap between classical and quantum noise resilience problems. The study also provides a converging hierarchy of semidefinite programming bounds to address this complexity, offering practical tools for analyzing quantum information encoding limits.
Computational Aspects of the Trace Norm Contraction Coefficient
arXiv:2507.16737v3 Announce Type: replace Abstract: We show that approximating the trace norm contraction coefficient of a quantum channel within a constant factor is NP-hard. Equivalently, this shows that determining the optimal success probability for encoding a bit in a quantum system undergoing noise is NP-hard. This contrasts with the classical analogue of this problem that can clearly be solved efficiently. We also establish the NP-hardness of deciding if the contraction coefficient is equal to 1, i.e., the channel can perfectly preserve a bit. As a consequence, deciding if a non-commutative graph has an independence number of at least 2 is NP-hard. In addition, we establish a converging hierarchy of semidefinite programming upper bounds on the contraction coefficient.
Abstract:We show that approximating the trace norm contraction coefficient of a quantum channel within a constant factor is NP-hard. Equivalently, this shows that determining the optimal success probability for encoding a bit in a quantum system undergoing noise is NP-hard. This contrasts with the classical analogue of this problem that can clearly be solved efficiently. We also establish the NP-hardness of deciding if the contraction coefficient is equal to 1, i.e., the channel can perfectly preserve a bit. As a consequence, deciding if a non-commutative graph has an independence number of at least 2 is NP-hard. In addition, we establish a converging hierarchy of semidefinite programming upper bounds on the contraction coefficient.
35 pages, 2 figures; minor improvements and corrections. Computational model added. Accepted for publication in IEEE Transactions on Information Theory, DOI: https://doi.org/10.1109/TIT.2026.3743741
Quantum Physics (quant-ph); Computational Complexity (cs.CC)
arXiv:2507.16737 [quant-ph]
(or arXiv:2507.16737v3 [quant-ph] for this version)
https://doi.org/10.1109/TIT.2026.3743741 DOI(s) linking to related resources
Text integral sub licența deschisă a publicației · 154 cuvinte
Subiecte conexe
DI Series: Serving Kimi-K3 MXFP4 Wide-EP Disaggregated on AMD Instinct MI300X and MI325X
AMD · 8 oct. 2026
State of the Field: AI for Epistemics and Coordination
LessWrong · 2 oct. 2026
A Sum-of-Squares Hierarchy with Quadratic Convergence for Quantum Channel Coding
arXiv · 10 sept. 2026
Tech to Replace Animal Testing Is Almost Ready. Scientists Are Not
IEEE Spectrum · 29 sept. 2026