Exploiting permutation invariance to reduce the exponential scaling of semidefinite programs in quantum information has emerged as a powerful computational technique. In this work, we develop a systematic framework for using this reduction via Schur-Weyl duality for optimization problems, and establish methods that allow one to work fully inside the permutation invariant subspace while performing operations such as (partially) applying channels and taking (partial) traces, or computing expressions like the quantum relative entropy. We then apply our techniques to the problem of computing efficient lower bounds on the channel fidelity over
n parallel uses of a quantum channel. The algorithm, which we call symmetric seesaw method, exploits permutation-invariant codes to yield improved lower bounds on the channel fidelity over
n uses of the depolarizing and amplitude-damping channel in the regime of tens of channel uses, and was used in [arxiv:2604.27042] to demonstrate non-asymptotic superactivation of quantum capacity for
n=17. An implementation of our methods, aimed at being suitable for various quantum information theoretic optimization problems, is also available as an open-source Python package.
The
ε-approximate degree of a function
f:X→{0,1} is the least degree of a multivariate real polynomial
p such that
∣p(x)−f(x)∣≤ε for all
x∈X. We determine the
ε-approximate degree of the element distinctness function, the surjectivity function, and the permutation testing problem, showing they are
Θ(n2/3log1/3(1/ε)),
Θ~(n3/4log1/4(1/ε)), and
Θ(n1/3log2/3(1/ε)), respectively. Previously, these bounds were known only for constant
ε. We also derive a connection between vanishing-error approximate degree and quantum Merlin--Arthur (QMA) query complexity. We use this connection to show that the QMA complexity of permutation testing is
Ω(n1/4). This improves on the previous best lower bound of
Ω(n1/6) due to Aaronson (Quantum Information & Computation, 2012), and comes somewhat close to matching a known upper bound of
O(n1/3).
We study unbiased estimation of scalar-valued polynomial functionals of quantum states from independent copies. We establish an equivalence between the first-order marginal of a permutation-invariant finite-copy observable and the functional gradient. We then prove that, among unbiased permutation-invariant estimators, the quantum U-statistic is the unique extension to an arbitrary number of copies. We further derive a universal variance expansion in which the leading
1/n term is determined by the variance of the functional gradient, while higher-order contributions are of order
O(1/n2). This leading variance coincides with the multiparameter quantum Cramér--Rao limit, establishing asymptotic efficiency of quantum U-statistics. We also characterize the higher-order scaling at points where the variance of the first-order gradient vanishes. As an application, we analyze the Bures
χ2-divergence and show that a spectral lower bound on the reference state is sufficient but not necessary for bounded-variance estimation. Beyond asymptotic variance, we establish variance-sensitive exponential concentration bounds, deriving a closed-form Bernstein-type inequality to capture finite-sample tail behaviour, and establish the Moderate Deviation Principle to characterize the intermediate asymptotic regime.