  Cross-platform verification is the task of comparing the output states
produced by different physical platforms using solely local quantum operations
and classical communication. While protocols have previously been suggested for
this task, their exponential sample complexity renders them unpractical even
for intermediate-scale quantum systems. In this work, we propose a novel
protocol for this task based on Pauli sampling, a subroutine which generates
Paulis distributed according to their weight in the expansion of a quantum
state in the Pauli basis. We show that our protocols for both Pauli sampling
and cross-platform verification are efficient for quantum states with low magic
and entanglement (i.e., of the order $O(\log n)$). Conversely, we show
super-polynomial lower bounds on the complexity of both tasks for states with
$\omega(\log n)$ magic and entanglement. Interestingly, when considering states
with real amplitudes the requirements of our protocol for cross-platform
verification can be significantly weakened.
