Sublinear Copies Suffice for Fidelity Estimation with Pauli Measurements

1. Introduction

• The motivating question is whether Θ(d) samples are a fundamental barrier, given prior Pauli-measurement fidelity estimation with O(d) samples.Fidelity is presented as a more practical quality measure than reconstructing a complete state description.Source: §1 · p. 1
• The protocol also estimates tr(ρσ) when the target ρ is potentially mixed.Source: §1 · p. 1
• Identity-containing Pauli observables can be obtained by marginalizing full-weight Pauli outcomes, so the protocol uses 3^N measurement choices rather than 4^N.The passage attributes these observations to.Source: §1 · p. 2

1.1 Problem Setup

• The setup estimates ⟨ρ,σ⟩ from copies of σ and a description of ρ, restricting every per-copy measurement to a Pauli basis measurement.Source: §1.1 · p. 2

1.2 Results

• Uniform Pauli-basis sampling gives an unbiased fidelity estimate, while purity and positive-semidefinite constraints on ρ support a global variance bound using hypercontractivity.Source: §1.2 · p. 2
• The fidelity-estimation protocol yields robust certification by distinguishing high-fidelity from low-fidelity cases using sublinear Pauli measurements.Source: §1.2 · p. 2
• n = o(d^0.9908/ε^2·log(1/δ)) copies suffice for Pauli-basis fidelity estimation, with measurement choices independent of ρ.The result estimates tr(ρσ).Source: §1.2 · p. 2

Tomography

• Quantum state tomography reconstructs a density matrix, while related work studies its copy complexity under single-copy, adaptive, and Pauli measurement restrictions.Source: §2 · p. 3

Certification

• Certification work considers entangled and single-copy measurements, including adaptive settings and target-dependent copy-complexity results.Source: §2 · p. 3

Certification and fidelity

• For Pauli or single-qubit measurements, cited certification and fidelity-estimation results include guarantees for fractions of states and, in other settings, all-state verification.The cited works include, [HPS24], [GHO26], and.Source: §2 · p. 3

Fidelity and Distributed Inner Product Estimation

• Direct fidelity estimation and distributed inner-product estimation address related overlap-estimation tasks using Pauli sampling or other restricted measurement settings.The passages cite [FL11b] for direct fidelity estimation and for distributed inner-product estimation with limited entanglement and magic.Source: §2 · pp. 3–4

3.1 Quantum Mechanics

• Quantum states are represented by Hermitian, positive semidefinite, unit-trace density matrices, and Pauli matrices and their tensor products provide a basis for describing states.Source: §3.1 · p. 4

3.2 Quantum Measurement

• Pauli measurements include two-outcome observable measurements that reveal Pauli coefficients and basis measurements that independently measure each qubit and produce 2^N outcomes.Source: §3.2 · p. 5

3.3 Pauli Notations

• The notation section introduces Pauli weight and set operations for observables that share a measurement group, including an inclusion-exclusion identity.Source: §3.3 · pp. 5–6

3.4 Boolean Analysis and Hypercontractivity

• Boolean functions on the hypercube have Fourier representations, and the Bonami-Beckner operator dampens higher-degree coefficients, yielding the hypercontractivity property used here.Source: §3.4 · pp. 6–7

3.5 Binomial Tail Bounds

• The binomial-tail preliminaries present Chernoff concentration and anti-concentration bounds, with Stirling’s approximation used for a nearly tight lower bound.Source: §3.5 · pp. 7–8

• The warm-up protocol is target-agnostic and supports mixed target states, unlike the [FL11b] importance-sampling approach, whose sampling distribution is valid only for pure targets.Source: §4 · p. 8
• Uniformly sampled Pauli observables are measured on separate copies, and each outcome is scaled by the target’s Pauli coefficient to form an unbiased fidelity estimate.Source: §4 · p. 8
• The warm-up protocol matches the copy complexity of [FL11b], while serving as a simpler setting for understanding the sublinear protocol’s higher-level ideas.Source: §4 · pp. 8–9

5.1 The protocol and variance analysis

• Protocol P1 samples full-weight Pauli bases and postprocesses measurement outcomes into an unbiased shadow-overlap estimate; bounding its variance is the main challenge.The variance analysis depends on the σ-biased Pauli norm.Source: §5.1 · pp. 9–10, §5 · p. 9

5.5 Putting it all together

• Theorem 1 is titled “Sublinear Fidelity Estimation with Pauli Basis Measurements”; the text says Protocol P1 estimates fidelity and gives a sublinear bound on the σ-biased Pauli norm.Source: §5.1 · pp. 10–11

5.2 Reducing biased Pauli norm to random Pauli graphs

• The σ-biased Pauli norm is reduced to expected edge-weight quantities of random Pauli graphs.The graph vertices are sampled according to the squared Pauli coefficients of the target state.Source: §5.2 · p. 11

5.3 Edge weight of random Pauli graphs

• The expected edge weight of the target-induced random Pauli graph is bounded using the target state's purity constraints and hypercontractivity.The proof interprets a channel matrix through a noisy channel and compares it with a binary symmetric channel.Source: §5.3 · pp. 12–13

5.4 Bounding lab state norm

• The lab-state norm is bounded through combinatorial arguments and an optimization under the state's positive-semidefinite and purity constraints.The optimization is described as a fractional knapsack problem over Pauli-observable weights.Source: §5.4 · pp. 13–14

6 Additional proof: noisy channel symmetrization

• The stated strategy is to find the largest p for which the tensor-product binary symmetric channel condition holds.The proof first diagonalizes the channel before applying the transformed operator comparison.Source: §6 · p. 16
• Conjugating by H⊗2 reduces the operator inequality to checking that the difference matrix ∆p is positive semidefinite.The passage identifies H as the Hadamard matrix and describes the transformed inequality as equivalent up to rotation.Source: §6 · p. 16
• Generalized Sylvester’s criterion reduces the check to nonnegative principal minors, including the diagonal entries and the full determinant.The determinant condition is expanded as a cubic polynomial in p and then factored.Source: §6 · p. 17
• The scalar constraints reduce to nonnegativity conditions on two quadratics, which the proof concludes hold under a stated bound on p.The proof says one condition is vacuous given another and ends by declaring the conditions satisfied.Source: §6 · p. 17