Quantum information · Theory
Witnessing Magic (and other Quantum Resources)
arXiv:2611.19017v1 ↗PDF ↗Submitted 13 November 2026
- Question
- Robustness measures of magic, entanglement and coherence equal the largest expectation value of a witness operator, so in principle they can be measured. But even when an optimal witness is known, estimating its expectation to error \(\epsilon\) takes about \(\mathrm{Var}(W)/\epsilon^2\) shots. How large must that variance be, and for which states and tasks is robustness efficiently measurable?
- Result
- For mixed states, any optimal witness has \(\mathrm{Var}(W)\ge(\mathcal R-1)^2/(\mathrm{Tr}(\rho^{-1}\phi^2)-1)\) for a free state \(\phi\) in the support of \(\rho\), so the shot count grows at least quadratically with robustness. For the generalized robustness of pure states the bound is \(\mathcal R^+(\sqrt{\mathcal R^+F}-1)^2/(1-F)\), with \(F\) the best overlap with a free state. A geometric bound, \(\mathcal R^+(1/F_r-\mathcal R^+)\), is tight for coherence and bipartite entanglement. Along any path of states, the integrated variance is at least the squared robustness gain over the path's Fisher length, so an exponential gain along a path generated by local terms must pass through states needing exponentially many shots, unless only relative error is required.
The paper in detail
A resource theory splits states into free ones (stabilizer states for magic, separable states for entanglement, incoherent states for coherence) and resourceful ones. The robustness \(\mathcal R(\rho)\) measures how much free noise a state can absorb before becoming free; by duality it equals the largest value of \(\mathrm{Tr}(W\rho)\) over witnesses \(W\) with \(|\mathrm{Tr}(W\phi)|\le1\) on every free state. Generalized robustness \(\mathcal R^+\) restricts to positive witnesses, and the free-state fidelity \(F\), the best overlap of a pure state with a free state, gives \(1/F\le\mathcal R^+\le\mathcal R\).
The paper assumes an optimal witness is known and asks only for the sampling cost. Danskin's theorem makes the optimal witness a locally unbiased estimator of robustness wherever robustness is differentiable: moving the state changes \(\mathcal R\) exactly as it changes \(\mathrm{Tr}(W\rho)\) with \(W\) held fixed. The quantum Cramér–Rao inequality then bounds \(\mathrm{Var}(W)\) from below for any perturbation of the state, and the authors choose perturbations towards or away from a nearby free state.
For mixed states with a free state inside their support, the bound grows quadratically with \(\mathcal R-1\), so highly resourceful mixed states are expensive to certify to fixed absolute error, while the relative variance bound does not grow with \(\mathcal R\). For pure states and generalized robustness the bound vanishes when \(\mathcal R^+=1/F\), as for the magic state \(\ket T\), which is its own optimal witness and can be measured with zero variance. When \(\mathcal R^+\) and \(1/F\) grow together at a fixed ratio, the relative-variance bound shrinks.
For pure states one can always take a rank-one optimal witness \(\ket\omega\bra\omega/F(\omega)\), and then the variance equals \((\mathcal R^+)^2\tan^2\theta\), with \(\theta\) the angle between the state and \(\ket\omega\). Bounding how close \(\ket\omega\) can be to free states, using the free states in an optimal decomposition, bounds \(\theta\). For coherence and bipartite entanglement, where those free states are orthogonal, the resulting bound is attained.
The last result concerns paths. If robustness rises from \(\mathcal R(\rho_0)\) to \(\mathcal R(\rho_1)\) along a path whose quantum Fisher information is polynomial, as for evolution under a local Hamiltonian for polynomial time, the integrated witness variance is at least \((\Delta\mathcal R)^2\) over the Fisher length. An exponential gain therefore forces a stretch of exponential variance even if both ends are easy to measure. For relative error the bound involves only \(\log^2\) of the robustness ratio. Where the hard region lies, and whether it separates easy regions, is left open.
Transferable methods
Danskin's theorem plus the Cramér–Rao bound for witnesses
Bounding the variance of an optimal witness needs the derivative of its expectation along a perturbation of the state. Danskin's theorem says that where the robustness is differentiable this derivative equals the derivative with the witness held fixed, so the witness acts as a locally unbiased estimator and the Cramér–Rao inequality applies.
For a family \(\rho_x\) with symmetric logarithmic derivative \(\mathcal L_x\), \(\partial_x\langle M\rangle=\mathrm{Tr}(M\partial_x\rho_x)=\mathrm{Cov}(M,\mathcal L_x)\), and Cauchy–Schwarz gives \[\mathrm{Var}(M)\ge\frac{|\partial_x\langle M\rangle|^2}{I_x},\qquad I_x=\mathrm{Var}(\mathcal L_x).\] With \(\rho_c=\rho+c(\rho-\phi)\) for a free \(\phi\) in the support of \(\rho\), \(\partial_c\mathrm{Tr}(W\rho_c)=\mathcal R-\mathrm{Tr}(W\phi)\ge\mathcal R-1\), and the left logarithmic derivative \((\rho-\phi)\rho^{-1}\) has Fisher information \(\mathrm{Tr}(\rho^{-1}\phi^2)-1\). Hence \[\mathrm{Var}(W)\ge\frac{(\mathcal R-1)^2}{\mathrm{Tr}(\rho^{-1}\phi^2)-1}.\]
Integrating \(|\partial_x\mathcal R|\le\sqrt{I_x\,\mathrm{Var}(W_x)}\) along a path and applying Cauchy–Schwarz to the integral gives \[\int_0^1\mathrm{Var}(W_x)\,dx\ge\frac{(\Delta\mathcal R)^2}{\int_0^1I_x\,dx},\qquad\int_0^1\frac{\mathrm{Var}(W_x)}{\mathcal R(\rho_x)^2}\,dx\ge\frac{\log^2\bigl(\mathcal R(\rho_1)/\mathcal R(\rho_0)\bigr)}{\int_0^1I_x\,dx}.\]
In the example of \(n\) qubits where one qubit turns from \(\ket+\) into \(\ket T\) and the others are already \(\ket T\), \(\Delta\mathcal R^+=\mathcal R^+(T)^{n-1}(\mathcal R^+(T)-1)\) is exponential while the log ratio is constant. Editorial check: with \(F(T)=\cos^2(\pi/8)\approx0.854\), a semidefinite program over the six single-qubit stabilizer states gives \(\mathcal R^+(T)=1.17157\approx1/F(T)\), so \(\ket T\bra T/F(T)\) is optimal and measuring it on \(\ket T\) has zero variance.
How to reuse it
For any quantity defined as a maximum of linear functionals of the state (robustness, Bell values, fidelity-based measures), Danskin's theorem plus the Cramér–Rao inequality gives shot-count lower bounds that need only a well-chosen perturbation, not the witness itself.
Witness variance as an angle
For a pure state, an optimal witness for generalized robustness can be taken rank-one, and then its variance depends only on the angle between the state and the witness vector. Showing that the witness vector cannot be too close to free states bounds that angle and hence the variance.
With \(W=\ket\omega\bra\omega/F(\omega)\) and \(\langle W\rangle=|\langle\psi|\omega\rangle|^2/F(\omega)=\mathcal R^+\), \[\mathrm{Var}(W)=\frac{|\langle\psi|\omega\rangle|^2-|\langle\psi|\omega\rangle|^4}{F(\omega)^2}=(\mathcal R^+)^2\tan^2\theta_{\psi\omega}.\]
If an optimal decomposition \(\ket\psi=\sum_ic_i\ket{\phi_i}\) into \(r\) free states with pairwise overlaps at most \(\cos\theta_f\) is used, optimality forces \(|\langle\omega|\phi_i\rangle|^2=F(\omega)\) for each \(i\). Setting \(\ket v=\sum_i\ket{\phi_i}\) with suitable phases and applying Cauchy–Schwarz, \(r^2F(\omega)\le\langle v|v\rangle\le r(1+(r-1)\cos\theta_f)\), so \[F(\omega)\le F_r=\frac{1+(r-1)\cos\theta_f}{r},\qquad\mathrm{Var}(W)\ge\mathcal R^+\Bigl(\frac1{F_r}-\mathcal R^+\Bigr).\]
For coherence the free states are basis vectors, \(F_r=1/r\), and \(W^*=\ket v\bra v\) with \(\ket v=\sum_ie^{i\arg c_i}\ket i\) satisfies \(W^{*2}=rW^*\), so its variance is \(\mathcal R(r-\mathcal R)\) and the bound is attained. Editorial check: for random five-dimensional states the semidefinite program returns \(\mathcal R^+=(\sum_i|c_i|)^2\) and the variance of \(W^*\) equals \(\mathcal R(r-\mathcal R)\) exactly, while the Cramér–Rao bound of Theorem 2 is several times smaller (0.44 against 1.89 in one sample). For magic, \(\theta_f=\pi/4\), so the bound says something only for \(\mathcal R^+<\sqrt2\).
How to reuse it
When an optimal witness can be chosen rank-one, the cost of certifying a resource becomes a question of angles between the state and the possible witness states. This suggests designing certification measurements by bounding how close witness states can come to free states, and checking first whether the state is its own optimal witness.
Context & limitations
Why it matters. It separates the computational problem of finding a witness from the statistical cost of using it, and it identifies the task that avoids most obstacles: estimating generalized robustness to low relative error on highly resourceful pure states. This guides which resource measures are realistic benchmarks for quantum devices.
Limitations. The bounds are lower bounds and need not be tight; the geometric bound for magic is informative only when \(\mathcal R^+<\sqrt2\). The path theorem proves that hard states exist along a path but not where they are. The paper does not address the cost of finding an optimal witness, which can itself be hard for magic. The acknowledgements state that ChatGPT-6 Astra was used for editing, literature search and to ensure the accuracy and novelty of the results.