Qi Ye

Estimating nonlinear properties of quantum states, such as $\mathrm{tr}(\rho^{k} O)$, is fundamental in quantum information but challenging due to the intrinsic linearity of quantum mechanics. Typical approaches such as generalized swap test rely on joint access to $k$ replicas to convert nonlinear functions in $\rho$ into linear functions in $\rho^{\otimes k}$. In this work, we prove that this conversion is not only sufficient but also necessary: any protocol that can only perform $(k-1)$-replica joint measurements require exponentially many samples to estimate $\mathrm{tr}(\rho^{k}O)$ with nonzero $\tr(O)$, while $k$-replica joint measurements allow efficient estimation. This establishes, for the first time, an exponential separation between $(k-1)$- and $k$-replica protocols for general $k$, thereby defining a fine-grained hierarchy for replica quantum advantage and solving an open question in the literature. The workhorse of our proofs is a general indistinguishability principle showing that any ensemble assembled from Haar-random states is hard to distinguish from its average. We also leverage this principle in spectrum testing, proving that $k$-replica joint measurements are also necessary to efficiently distinguish two spectra that match on all moments up to degree $k-1$. Our work draws sharp boundaries on the power of joint measurements, shedding light on resource-complexity tradeoffs in quantum learning theory.

We introduce a mixed-state magic criterion, the Triangle Criterion, which plays a role for magic analogous to the Positive Partial Transposition (PPT) criterion for entanglement: it combines strong detection capability, a clear geometric interpretation, and an operational link to magic distillation. Using this criterion, we uncover several new features of multi-qubit magic distillation and detection. We prove that genuinely multi-qubit magic distillation protocols are strictly more powerful than all single-qubit schemes by showing that the Triangle Criterion is not stable under tensor products, in sharp contrast to the PPT criterion. Moreover, we show that, with overwhelming probability, multi-qubit magic states with relatively low rank cannot be distilled by any single-qubit distillation protocol. We derive an upper bound on the minimal purity of magic states, which is conjectured to be tight with both numerical and constructive evidences. Using this minimal-purity result, we predict the existence of unfaithful magic states, namely states that cannot be detected by any fidelity-based magic witness, and reveal fundamental limitations of mixed-state magic detection in any single-copy scheme.