Efficient distributed inner product estimation via Pauli sampling

Abstract

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 pure 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.

Added numerical simulation, resembles published version

References in corpus (31)

• Efficient quantum state tomography
• Quantum advantage in learning from experiments
• Direct Fidelity Estimation from Few Pauli Measurements
• Evenly distributed unitaries: on the structure of unitary designs
• Quantum certification and benchmarking
• Practical characterization of quantum devices without tomography
• Stabilizer Rényi entropy
• Information-theoretic bounds on quantum advantage in machine learning
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Efficient quantum measurement of Pauli operators in the presence of finite sampling error
• Cross-Platform Verification of Intermediate Scale Quantum Devices
• Pseudorandom States, Non-Cloning Theorems and Quantum Money
• Stabilizer entropies and nonstabilizerness monotones
• Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
• Many-body magic via Pauli-Markov chains -- from criticality to gauge theories
• Stabilizer entropies are monotones for magic-state resource theory
• Theoretical and Experimental Perspectives of Quantum Verification
• Nonstabilizerness determining the hardness of direct fidelity estimation
• Efficient quantum algorithms for stabilizer entropies
• Overlapped grouping measurement: A unified framework for measuring quantum states
• Learning t-doped stabilizer states
• Pseudomagic Quantum States
• Cross-Platform Comparison of Arbitrary Quantum Computations
• Distributed quantum inner product estimation
• How to simulate quantum measurement without computing marginals
• Bell sampling from quantum circuits
• Improved Stabilizer Estimation via Bell Difference Sampling
• Pseudorandom unitaries are neither real nor sparse nor noise-robust
• Doped stabilizer states in many-body physics and where to find them
• Efficient learning of $t$-doped stabilizer states with single-copy measurements
• Cross-Platform Comparison of Arbitrary Quantum Processes

Cited by in corpus (6)

• Probing quantum complexity via universal saturation of stabilizer entropies
• Efficient mutual magic and magic capacity with matrix product states
• Resource-Efficient Cross-Platform Verification with Modular Superconducting Devices
• Learning unitaries with quantum statistical queries
• Estimation of multivariate traces of states given partial classical information
• Optimal randomized measurements for a family of non-linear quantum properties