Efficient Distributed Inner-Product Estimation via Pauli Sampling

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 impractical even for intermediate-scale quantum systems. In this work, we propose a novel protocol for this task based on Pauli sampling, a subroutine that 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 pure states with low magic and entanglement [i.e., of the order O(log n)]. Conversely, we show superpolynomial lower bounds on the complexity of both tasks for states with co (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.