  We propose an efficient protocol to estimate the fidelity of an $n$-qubit
entangled measurement device, requiring only qubit state preparations and
classical data post-processing. It works by measuring the eigenstates of Pauli
operators, which are strategically selected according to their importance
weights and collectively contributed by all measurement operators. We
rigorously analyze the protocol's performance and demonstrate that its sample
complexity is uniquely determined by the number of Pauli operators possessing
non-zero expectation values with respect to the target measurement. Moreover,
from a resource-theoretic perspective, we introduce the stabilizer R\'enyi
entropy of quantum measurements as a precise metric to quantify the inherent
difficulty of estimating measurement fidelity.
