arXiv:2609.35547
Sublinear Copies Suffice for Fidelity Estimation with Pauli Measurements
Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu, Nengkun Yu
Abstract
We present a protocol that estimates the quantum fidelity, up to precision $\varepsilon$, between a known target state and unknown lab-prepared state with sublinear, $o(d^{0.9908}/\varepsilon^2)$, number of Pauli basis measurements.
AI Summary
The paper asks whether estimating the overlap $\operatorname{tr}(\rho\sigma)$ between a classically specified target state $\rho$ and an unknown laboratory state $\sigma$ requires $\Theta(d)$ copies when measurements are restricted to local Pauli bases, where $d=2^k$ for $k$ qubits. For pure targets, this overlap is the fidelity; for mixed targets, the quantity estimated remains the Hilbert–Schmidt overlap rather than general mixed-state fidelity. The protocol samples each measurement basis uniformly from $\{X,Y,Z\}^{\otimes k}$, independently of the target. It combines all outcome parities with the corresponding target Pauli coefficients, weighting them to compensate for how often each Pauli string appears across bases. The resulting estimator is unbiased. The main guarantee is worst-case copy complexity $o(d^{0.9908}/\varepsilon^2)$ for additive error $\varepsilon$ and constant success probability, applicable to arbitrary target and laboratory states. Confidence amplification adds a $\log(1/\delta)$ factor. A corollary gives robust certification distinguishing overlap at least $1-\varepsilon/C$ from overlap at most $1-\varepsilon$, for constant $C>1$. The analysis bounds the estimator’s variance using purity and Pauli-coefficient constraints. A Hölder-inequality reduction separates a weighted Pauli-compatibility graph quantity from a laboratory-state quantity. These are bounded through Boolean hypercontractivity after comparison with a binary symmetric channel, and through a fractional-knapsack relaxation with binomial tail bounds, respectively. The result establishes sublinear dependence on dimension but remains exponential in qubit count; no matching lower bound is provided.
Error found: The global biased-Pauli-norm theorem states γ=(1+√3)/8, whereas its proof and the main theorem use γ=(1+√33)/8. The graph reduction uses noninteger powers of potentially negative Pauli coefficients without absolute values, requiring an absolute-value correction and a triangle-inequality step to make the proof valid.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.