Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.16737 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916959634849792 |
|---|---|
| author | Delsol, Idris Fawzi, Omar Kochanowski, Jan Ramachandran, Akshay |
| author_facet | Delsol, Idris Fawzi, Omar Kochanowski, Jan Ramachandran, Akshay |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_16737 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computational aspects of the trace norm contraction coefficient Delsol, Idris Fawzi, Omar Kochanowski, Jan Ramachandran, Akshay Quantum Physics Computational Complexity 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. |
| title | Computational aspects of the trace norm contraction coefficient |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2507.16737 |