Information Theory 1

Abstract: We investigate the relationship between partial traces and their dilations for general complex matrices, focusing on two main aspects: the existence of (joint) dilations and norm inequalities relating partial traces and their dilations. Throughout our analysis, we pay particular attention to rank constraints. We find that every pair of matrices of equal size and trace admits dilations of any rank larger than one. We generalize Audenaert's subadditivity inequality to encompass general matrices, multiple tensor factors, and different norms. A central ingredient for this is a novel majorization relation for Kronecker sums. As an application, we extend the interval of Werner states in which they are provably 2-undistillable in any dimension $d\geq 4$. We also prove new Schmidt-number witnesses and k-positive maps.

Abstract: The Clifford group plays a central role in quantum information science. It is the building block for many error-correcting schemes and matches the first three moments of the Haar measure over the unitary group—a property that is essential for a broad range of quantum algorithms, with applications in pseudorandomness, learning theory, benchmarking, and entanglement distillation. At the heart of understanding many properties of the Clifford group lies the Clifford commutant: the set of operators that commute with $k$-fold tensor powers of Clifford unitaries. Previous understanding of this commutant has been limited to relatively small values of $k$, constrained by the number of qubits $n$. In this work, we develop a complete theory of the Clifford commutant. Our first result provides an explicit orthogonal basis for the commutant and computes its dimension for arbitrary $n$ and $k$. We also introduce an alternative and easy-to-manipulate basis formed by isotropic sums of Pauli operators. We show that this basis is generated by products of permutations— which generate the unitary group commutant— and at most three other operators. Additionally, we develop a \emph{graphical calculus} allowing a diagrammatic manipulation of elements of this basis. These results enable a wealth of applications: among others, we characterize all \emph{measurable} magic measures and identify optimal strategies for stabilizer property testing, whose success probability also offers an operational interpretation to stabilizer entropies. Finally, we show that these results also generalize to multi-qudit systems with prime local dimension. This submission merges two of our recent works: one presenting a complete theory of the Clifford commutant with applications, and one focused on showcasing a major application to state $k$-design convergence.

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

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. Our hardness results also hold for deciding if the contraction coefficient is equal to 1. As a consequence, we show that 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.