Complexity of mixed Schatten norms of quantum maps

2025/07/11 by Jan Kochanowski, Omar Fawzi, Kochanowski, Jan +3 · 1 voice
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Mathematical Physics (math-ph) #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum many-body systems #math-ph #quant-ph

paper · pdf · doi:10.48550/arxiv.2507.08358

openalex publication_date 2025/07/11 · arxiv published 2025/07/11 · openalex created_date 2025/10/10 · arxiv updated 2026/01/23 · openalex updated_date 2026/07/28

Abstract

We study the complexity of computing the mixed Schatten ‖Φ‖_{q→ p} norms of linear maps Φ between matrix spaces. When Φ is completely positive, we show that ‖ Φ‖_{q → p} can be computed efficiently when q ≥ p. The regime q ≥ p is known as the non-hypercontractive regime and is also known to be easy for the mixed vector norms ℓ_q → ℓ_p [Boyd, 1974]. However, even for entanglement-breaking completely-positive trace-preserving maps Φ, we show that computing ‖ Φ‖_{1 → p} is NP-complete when p>1. Moving beyond the completely-positive case and considering Φ to be difference of entanglement breaking completely-positive trace-preserving maps, we prove that computing ‖ Φ‖⁺_{1 → 1} is NP-complete. In contrast, for the completely-bounded (cb) case, we describe a polynomial-time algorithm to compute ‖Φ‖_{cb,1→ p} and ‖Φ‖⁺_{cb,1→ p} for any linear map Φ and p≥1.

Citations

• Additivity and chain rules for quantum entropies via multi-index Schatten norms
• Computing mixed Schatten norm of completely positive maps
• The modified logarithmic Sobolev inequality for quantum spin systems: classical and commuting nearest neighbour interactions
• Computing the norm of nonnegative matrices and the log-Sobolev constant\n of Markov chains
• Optimal Analysis of Subset-Selection Based L_p Low Rank Approximation
• The Theory of Quantum Information
• Hypercontractivity and logarithmic Sobolev Inequality for non-primitive quantum Markov semigroups and estimation of decoherence rates
• Inapproximability of Matrix p→ q Norms
• Estimating operator norms using covering nets
• Mixed-norm Regularization for Brain Decoding
• Concavity of certain matrix trace and norm functions. II
• Simpler semidefinite programs for completely bounded norms
• Approximating Matrix p-norms
• Computing Stabilized Norms for Quantum Operations via the Theory of Completely Bounded Maps
• On the Complexity of Computing Zero-Error and Holevo Capacity of Quantum Channels
• Notes on super-operator norms induced by Schatten norms
• Logarithmic Sobolev inequalities for finite Markov chains

Discussions

• Happy to see that two of my works were accepted to QIP next year! "Complexity of mixed Schatten norms of quantum maps“: arxiv.org/abs/2507.08358 "Computational aspects of the trace norm contraction co [bsky, 4 points, 0 comments]

Related

• The Quantum Complexity of Computing Schatten p-norms
• Computing Stabilized Norms for Quantum Operations via the Theory of Completely Bounded Maps
• Computing mixed Schatten norm of completely positive maps
• Estimating operator norms using covering nets
• Norms and Cones in the Theory of Quantum Entanglement