Pith. sign in

REVIEW 2 major objections 4 minor 2 cited by

In the small-error limit, quantum learning sample complexity is governed by the inverse Fisher information matrix

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-02 21:02 UTC pith:3XLQX3JZ

load-bearing objection The inverse-Fisher framework is a real contribution, but the l2 Pauli application overclaims polynomial scaling: Corollary 1 drops a term that is exponential in n for fixed ε. the 2 major comments →

arxiv 2602.21510 v4 pith:3XLQX3JZ submitted 2026-02-25 quant-ph

Universal Sample Complexity Bounds in Quantum Learning Theory via Fisher Information Matrix

Hyukgun Kwon , Seok Hyung Lie , Liang Jiang This is my paper
classification quant-ph MSC 81P5062F1262B10 PACS 03.67.-a
keywords quantum learning theorysample complexityFisher information matrixquantum metrologymaximum likelihood estimationPauli channel learningPauli expectation valuesquantum memory advantage
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper establishes that, in the small-error asymptotic regime, the sample complexity of maximum-likelihood parameter estimation for a quantum system is governed by the inverse Fisher information matrix: the worst-case number of measurements needed to learn d parameters to additive error ε with confidence 1−δ scales like a logarithmic factor times the largest diagonal entry of the inverse Fisher matrix, divided by ε², with a matching lower bound from any diagonal entry. The claim is task-independent: it applies to any quantum learning protocol that estimates parameters by MLE, provided the standard regularity conditions hold. The paper uses this single quantity to explain, in a unified way, why Pauli channel learning becomes exponentially cheaper with entanglement and why Pauli expectation-value learning becomes exponentially cheaper with quantum memory: in each resource-restricted setting, some inverse-Fisher diagonal entry necessarily grows exponentially with qubit number. It also derives analogous ℓ²-norm bounds controlled by the largest eigenvalue of the inverse Fisher matrix. A sympathetic reader should care because the result connects learning-theoretic sample complexity to the central quantity of quantum metrology, potentially replacing task-specific proofs with one universal calculation.

Core claim

The paper's central claim is that the minimal sample complexity M needed for the maximum-likelihood estimator to satisfy Pr[||θ̂_ML − θ||∞ ≤ ε] ≥ 1−δ is asymptotically sandwiched between W0(δ^{-2}/2π)[F_θ^{-1}]_{aa} ε^{-2} and W0(8π^{-1}δ^{-2}d^2) sup_θ max_a [F_θ^{-1}]_{aa} ε^{-2}, so the inverse Fisher information matrix—not any task-specific quantity—controls the learning rate. For ℓ² error, the same statement holds with the largest eigenvalue of F^{-1} in the lower bound and a d-factor in the upper bound. In the applications, the paper recovers previously known exponential separations from this single principle: without entanglement, the purity constraint forces some Pauli component of a

What carries the argument

The central object is the inverse Fisher information matrix F_θ^{-1}, the asymptotic covariance of the maximum-likelihood estimator normalized by sample size. The proof machinery decomposes the MLE error via a Taylor expansion of the empirical score into a linear term plus Hessian fluctuation and third-derivative remainder, uses Berry–Esseen to control the Gaussian tail of the projected score, Mills-ratio to bound the tail, and Lambert W to invert the resulting exponential inequality; Brouwer fixed-point theorem upgrades the local bounds to a guaranteed fixed point inside the ε-cube. In the applications, the decisive step is comparing classical FIMs of restricted strategies with the QFIM: fo

Load-bearing premise

The whole argument rests on the maximum-likelihood regularity conditions—a unique interior maximizer that is also the unique stationary point, C³ smoothness—together with invertibility of the Fisher information matrix on the whole parameter space; at points where the FIM is singular (zero error rates, pure or degenerate probe states) the main theorems do not directly apply and the paper must fall back on the pseudoinverse treatment of Appendix G.

What would settle it

Take the entangled-probe Pauli eigenvalue model: the estimator is the empirical Walsh–Hadamard transform of Bell-outcome frequencies, so for a fixed λ and finite M one can exactly compute Pr[||λ̂−λ||∞ ≤ ε]. If, at small ε, the required M deviates from W0(8π^{-1}δ^{-2}4^{2n})ε^{-2} by more than a constant/log factor—or if a regular exponential-family model with finite inverse-FIM diagonals exhibits MLE sample complexity that does not converge to the predicted bound—the universal claim would be refuted.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • In the ε→0 regime, a single calculation—the largest diagonal entry of the inverse FIM—gives both an upper and a lower bound on sample complexity for any MLE-based learning protocol, so task-specific proofs become unnecessary for asymptotic scaling.
  • Pauli channel learning with a maximally entangled probe needs at most polynomially many samples in n, whereas any entanglement-free protocol (even with control and ancillas) needs exponentially many; the exponential is traced to a purity-imposed, exponentially small probe Pauli component.
  • Learning Pauli expectation values with quantum memory needs at most polynomial samples (with ε^{-4} for absolute values via Bell measurements), while without quantum memory it requires exponentially many samples; the exponent is traced to measurement incompatibility rather than state sensitivity.
  • Under ℓ² error, entangled-probe Pauli channel learning is no longer efficient: the lower bound contains 4^n p_(2), the second-largest Pauli error rate, so exponential cost persists even with entanglement when that rate is not exponentially small.
  • The comparison with the Cramér–Rao mean-squared-error bound shows that uniform (ε,δ) guarantees cost a strict logarithmic factor over merely bounding the MSE, quantifying the price of high-probability uniform control.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the inverse-FIM characterization is tight beyond MLE, one would expect the lower bound to hold for any estimator via the Cramér–Rao bound; the paper's MLE-specific proof would then be part of a broader learning–metrology duality.
  • A direct testable extension is to finite ε: compute exact MLE concentration for the Pauli-eigenvalue multinomial model at moderate ε and check whether the sup-max inverse-FIM expression still predicts the threshold or whether the logarithmic W0 factor overestimates.
  • The same diagonal-inverse-Fisher analysis could be applied to Hamiltonian learning or shadow tomography by computing the FIM of random measurements, potentially predicting query-complexity separations analogous to the quantum-memory one.
  • When the FIM is singular, the paper's pseudoinverse reduction suggests that only the estimable subspace matters; a natural extension is to characterize when parameter directions become unestimable under resource constraints as rank deficiency of the FIM.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper proposes a general sample-complexity framework for quantum parameter estimation with maximum likelihood estimation (MLE) under (ε,δ)-criteria. It derives upper and lower bounds for ℓ∞- and ℓ2-error criteria that are asymptotically characterized by the inverse Fisher information matrix (Theorems 1–4, Corollaries 1–4), and applies them to Pauli eigenvalue learning and Pauli expectation value learning. The main advertised results are a unified inverse-FIM characterization of sample complexity and a recovery of known exponential-to-polynomial separations for entangled versus unentangled quantum learning protocols.

Significance. If the bounds were uniform in the number of parameters, the framework would constitute a useful unification of quantum metrology and quantum learning theory. The proofs are detailed and the fixed-d, ε→0 asymptotic structure is a genuine attempt to explain sample complexity through the inverse FIM. The paper also reproduces some known qualitative separations in a streamlined form. However, the dimension-uniformity of the corollaries is not established, and one of the ℓ2 claims is actually not implied by the derived bound. These issues affect the central applications, so the current version overstates its contributions.

major comments (2)
  1. [Theorem 1 / Corollary 1; Eqs. (23)–(32), (62)] The passage from Theorem 1 to Corollary 1 is not uniform in the parameter dimension d, and this invalidates the claimed polynomial sample complexity for entangled Pauli channel learning. In the Bell-measurement Pauli model at λ=0, the single-sample Hessian deviation is B(x)=I−w_x w_x^T, where ‖w_x‖²=d=4^n−1, so V_H=E[Tr(B²)]=d(d−1) and ‖F^{-1}‖_op=1. Substituting into D in Theorem 1 gives (D/τ0^-)^2 ≈ 4d³/δ, which is independent of ε and exponential in n. For any fixed ε>0, this constant term dominates the claimed O(W0(d²)ε^{-2}) bound, so Eq. (62) does not follow unless ε is taken to scale as ε≲d^{-3/2} (or smaller). The paper never states such a joint ε–n scaling. Thus the central exponential-separation claim in Sec. III.C.2 is not supported by the theorems as written.
  2. [Sec. IV.C, Eqs. (135)–(142)] The lower bound in Eq. (142), M≳W0(δ^{-2}/2π)ε^{-2}4^n p^{(2)}, does not imply the sentence that follows it: “when entanglement is employed, the estimation protocol still requires an exponentially large number of samples.” The bound is exponential only if p^{(2)} is not exponentially small, but p^{(2)} can be 4^{-n}; e.g., the valid Pauli channel with p_0=1−4^{-n} and p_a=4^{-n} for a≠0. In that case Eq. (142) gives only O(ε^{-2}). Meanwhile the upper bound in Eq. (135) is O(4^n W0(4^{2n})ε^{-2}), so the two bounds are consistent with a constant lower bound. An additional assumption on p^{(2)} is required to justify an exponential ℓ2 lower bound.
minor comments (4)
  1. [Sec. III, first paragraph] The text says the upper bound is governed by the “minimum diagonal entry of the FIM”; this should be “supremum of the largest diagonal entry of the inverse FIM,” matching Corollary 1.
  2. [Corollaries 1–4] The use of “≲” is not defined with respect to dimension dependence. Since Theorem 1 contains model-dependent constants V_H, V_R, μ_R, ρ that can depend on d, the corollaries should explicitly state whether the hidden constants are uniform in d or not.
  3. [Appendix H.1] For the Bernoulli model, assumption (A1) fails when S=0 or S=M, since the maximizer is on the boundary. A standard measure-zero or interior-sample caveat should be stated.
  4. [General notation] The reuse of symbols τ0±, D, and η with different definitions in Theorems 1–4 is acknowledged, but it makes the paper harder to follow. A table of definitions would help.

Circularity Check

0 steps flagged

No significant circularity: the main bounds are derived from MLE asymptotics, and prior results are used only as comparisons, not as premises.

full rationale

The central theorems are proven from first principles in Appendices C–F: Taylor expansion of the score, concentration via Markov/Chebyshev, Berry–Esseen, Mills-ratio tail bounds, Lambert-W manipulations, and Brouwer fixed-point arguments. The inverse Fisher information matrix enters as the score variance E[ℓ^(1) ℓ^(1)T] = F and E[ℓ^(2)] = −F (Eqs. A9–A11), not as an assumed sample-complexity formula. Corollaries 1–4 are the stated ε→0 limits of these theorems. The Pauli applications compute the FIM/QFIM from independent, standard ingredients (Bell measurement, purity constraint, data-processing inequality) and then invoke Corollaries 1–2; the results of Refs. [16,18,22] are cited as prior benchmarks to be recovered, not as assumptions used in the derivations. The only overlapping-author citation, Ref. [45], appears in the secondary singular-FIM appendix for a standard estimable-subspace criterion and is not needed for the central invertible-FIM claims. The reviewer's concern about the discarded (D/τ0^-)^2 term in Corollary 1 is a question of uniformity in d and ε, i.e., a correctness/rigor issue, not circularity: it does not make the derived bound equal to its input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 10 axioms · 0 invented entities

No free parameters are fitted to data. The central claim relies on standard MLE regularity, finite-moment, and invertibility assumptions, plus standard statistical theorems and known quantum estimation facts. The exponential lower bounds additionally lean on the purity constraint and QCRB. No invented entities are introduced.

axioms (10)
  • domain assumption Regularity (A1): log-likelihood has unique maximizer in the interior of Θ, and it is the unique stationary point
    Stated at start of Sec. III; used in Theorems 1-4 and to identify the Brouwer fixed point with the MLE.
  • domain assumption Regularity (A2): log-likelihood is C^3 on Θ
    Stated at start of Sec. III; needed for Taylor expansion with third-order remainder and for moment finiteness in Berry-Esseen.
  • domain assumption FIM F_θ is invertible on Θ
    Stated in Sec. V; the main theorems use F^{-1}; singular cases are treated separately in Appendix G via pseudoinverse.
  • domain assumption Finite moment assumptions V_H, V_R, ρ and uniform remainder bound r(x) (Eq. C34)
    Introduced in Appendix C; needed for Markov/Chebyshev concentration of the Hessian and third-derivative remainder.
  • standard math Berry-Esseen theorem with universal constant
    Appendix B; used to bound Gaussian approximation error of the projected score in Theorems 1-4.
  • standard math Brouwer fixed-point theorem
    Appendix C; used to prove existence of a stationary point within the l∞ error cube.
  • standard math Quantum Cramér-Rao inequality F^{-1} ⪰ J^{-1}
    Eq. (7); used in no-entanglement lower bounds to pass from QFIM to FIM.
  • domain assumption Formula [J^{-1}]_{ii} = 1 - θ_i^2 for Pauli expectation-value parameterization
    Eq. (17), cited to Ref. [39]; used for entangled Pauli-channel upper bound and QFIM comparisons.
  • standard math Purity constraint: Σ_{a≠0} r_a^2 ≤ 2^n - 1 for any n-qubit state
    Eq. (70); load-bearing for the exponential lower bounds without entanglement.
  • standard math Data-processing inequality and additivity of QFIM for separable operations
    Eqs. (80)-(81); used to bound QFIM in entanglement-free multi-use protocols.

pith-pipeline@v1.3.0-alltime-deepseek · 37373 in / 25836 out tokens · 222710 ms · 2026-08-02T21:02:36.321983+00:00 · methodology

0 comments
read the original abstract

We show that the sample complexity required in quantum learning theory within a general parametric framework is fundamentally governed by the inverse Fisher information matrix. More specifically, we derive upper and lower bounds on the number of samples required to estimate the parameters of a quantum system within a prescribed small additive error, with high success probability under maximum-likelihood estimation. Notably, both the upper and lower bounds are determined by the supremum of the maximum diagonal entry of the inverse Fisher information matrix. We then apply the general bounds to Pauli channel learning and Pauli expectation value learning, which serve as representative tasks in quantum channel and state learning, respectively, in the asymptotic small-error regime. Furthermore, we identify the structural origin of exponential sample complexity in Pauli channel learning without entanglement and in Pauli expectation value learning without quantum memory by comparing the quantum Fisher information matrix and the classical Fisher information matrix. We then extend the analysis to an error criterion based on the Euclidean distance between the true parameter values and their estimators, deriving the corresponding upper and lower bounds on the sample complexity, which are likewise characterized by the inverse Fisher information matrix. As an application, we consider Pauli channel learning with entangled probes. We highlight two fundamental contributions to quantum learning theory. First, we establish a systematic framework that determines the task-independent sample complexity under maximum-likelihood estimation. Second, we show that, in the small-error regime, the learning sample complexity is governed by the inverse Fisher information matrix, which is the central quantity in quantum metrology that determines the ultimate achievable mean squared error.

Figures

Figures reproduced from arXiv: 2602.21510 by Hyukgun Kwon, Liang Jiang, Seok Hyung Lie.

Figure 1
Figure 1. Figure 1: FIG. 1. Schematic of parameter estimation [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. Schematic of Pauli channel learning. Colors [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Precision Limits of Multiparameter Markovian-Noise Metrology

    quant-ph 2026-04 unverdicted novelty 7.0

    Ultimate precision bounds for multiparameter Markovian noise metrology show average variance scaling as Ω(1/(T R²)) with Heisenberg scaling in dissipative channels R when using entangled probes and high-rank signal co...

  2. Absent, Not Faint: Fisher-Information Limits and a Logarithmic Measurement-Design Cure for Passive Characterization of Coherent Qubit Noise

    quant-ph 2026-07 conditional novelty 6.0

    Coherent over-rotation angles are Fisher-null (CRB infinite) in a single fixed-basis histogram at zero angle; adding ⌈log2(n+1)⌉ extra product-Pauli settings restores identifiability, with conditioning, not coverage, ...

Reference graph

Works this paper leans on

83 extracted references · 3 linked inside Pith · cited by 2 Pith papers

  1. [1]

    Pauli error rates and eigenvalues We first introduce a notation for then-qubit Pauli operators. Anyn-qubit Pauli operator can be expressed as ˆPa = nO k=1 (i)ax,kaz,k ˆX ax,k ˆZ az,k ,(45) where the index 0≤a≤4 n −1 uniquely labels the Pauli operator, and [a] 2 := (ax,1, ax,2,· · ·, ax,n, az,1, az,2,· · ·, az,n) denotes the binary representation ofa. Base...

  2. [2]

    (See Fig

    Entanglement-assisted scheme We first analyze the learning of Pauli eigenvalues assisted by entanglement with a noiseless ancilla mode. (See Fig. 2 (a) for the schematic of the description.) To estimate the Pauli eigenvaluesλ, let us consider the maximally entangled state ˆρ0 :=|Ψ⟩ ⟨Ψ|=1 4n 4n−1X a=0 ˆP S a ⊗ ˆP A a (50) as a quantum probe. Here, the supe...

  3. [3]

    (See Fig

    Separable scheme with single use of Pauli channel without ancilla We next investigate learning the Pauli eigenvalues using a single use of the Pauli channel, without entanglement. (See Fig. 2 (b) for the schematic of the description.) Anyn-qubit quantum state can be expanded in the Pauli basis as ˆρ0 = 1 2n 4n−1X a=0 ra ˆPa,(66) where the coefficientsr a ...

  4. [4]

    (See Fig

    Separable scheme with multiple uses of Pauli channel with unbounded classical register We now show that learning the Pauli eigenvalues without entanglement still requires a number of samples that scales exponentially with the number of qubitsn, even though one permits concatenated uses of the Pauli channel together with arbitrarily large ancilla modes 9 a...

  5. [5]

    Realizing this scenario requires quantum memory

    Quantum memory and Collective measurement We first consider the setting in which multiple copies of the state ˆρ c can be prepared simultaneously and arbitrary collective measurements across these copies are allowed. Realizing this scenario requires quantum memory. The estimation procedure proposed there proceeds in two stages. In the first stage, the abs...

  6. [6]

    Let { ˆΠx}x be a general POVM satisfying P x ˆΠx = ˆI

    Single copy of the state Next, we consider the setting in which only a single copy of the state is available per measurement. Let { ˆΠx}x be a general POVM satisfying P x ˆΠx = ˆI. We analyze the estimation problem at the maximally mixed state, i.e.,c=0. Since each POVM element is positive semidefinite, it admits a spectral decomposition ˆΠx = X j λxj |ϕx...

  7. [7]

    Entanglement assisted scheme In Sec. III C 2, we already find that sup λ max a∈[d] [F−1 λ ]aa = 1.(134) Combining this with Corollary 3, to learnλunder (ϵ, ℓ2, δ)-criteria, the minimal sample complexityMis upper bounded as M≲4 nW0(8π−1δ−242n)ϵ−2.(135) Next, let us find the lower bound. As shown in Sec. III C 2, when a maximally entangled state is employed...

    2025

  8. [8]

    We begin by introducing the log-likelihood function associated with a single measurement outcomex

    Single-sample derivatives and sample averages. We begin by introducing the log-likelihood function associated with a single measurement outcomex. For a given parameter vectorϑ∈R d, the log-likelihood is 15 defined as ℓϑ(x) := logp ϑ(x).(A1) We then denote first-, second-, and third-order derivatives of the log-likelihood function with respect to the param...

  9. [9]

    We first recall the operator norm for linear maps

    Norm conventions Throughout the manuscript,⟨u,v⟩:=u Tvdenotes the standard inner product onR d, and∥v∥ 2 := p ⟨v,v⟩ denotes the corresponding Euclidean norm. We first recall the operator norm for linear maps. For a matrixB∈R d×d, the operator norm induced by∥ · ∥2 is defined as ∥B∥op := sup v∈Rd:∥v∥ 2=1 ∥Bv∥2.(A16) This norm quantifies the maximal amplifi...

  10. [10]

    Berry-Esseen Theorem For the details, see Refs. [48–50]. The Berry-Esseen theorem is a quantitative refinement of the central limit theorem: it provides an explicit rate at which the distribution of a normalized sum of independent random variables approaches the standard normal distribution. LetX:= (X 1, X2,· · ·, XM ) be i.i.d. random variables with E[X1...

  11. [11]

    For allx >0, one has x 1 +x 2 ϕ(x)<1−Φ(x)< ϕ(x) x .(B5)

    Mills Ratio Inequality The Mills ratio inequality provides sharp bounds on the Gaussian tail [51–54]. For allx >0, one has x 1 +x 2 ϕ(x)<1−Φ(x)< ϕ(x) x .(B5)

  12. [12]

    Definition See Refs

    LambertW 0 F unction a. Definition See Refs. [40, 41] for the details. In mathematics, the LambertWfunction is defined as the inverse relation of the map f(w) =we w,(B6) wherewis a complex number. The principal branch, denoted byW 0(z), is the single-valued branch that is real-valued on its maximal real domain. By definition, W0(z) satisfies W0(z)e W0(z) ...

  13. [13]

    Proof sketch Let us denoteA(ϵ) := n ˜θML −θ ∞ ≤ϵ o . Our goal is to determine the minimal sample sizeM 0(ϵ, δ, d) such that, for prescribed accuracyϵ >0 and confidence level 18 1−δwith 0< δ≤1, the MLE ˜θML satisfies ∀M≥M 0(ϵ, δ, d) : Pr[A(ϵ)]≥1−δ,(C6) or equivalently ∀M≥M 0(ϵ, δ, d) : Pr[A(ϵ)c]≤δ.(C7) In this section, we find the upper bound onM 0 by foll...

  14. [14]

    We begin by introducing the maximum likelihood estimator (MLE) associated with the observed sample x

    T aylor expansion of the score function. We begin by introducing the maximum likelihood estimator (MLE) associated with the observed sample x. Let ˜θML(x) := arg max ϑ ℓϑ(x) (C11) denote the MLE, which we assume to be the unique maximizer of the log-likelihood function from (A1) in the main text. Throughout the proof, we express the true parameter value a...

  15. [15]

    Forϵ >0, let us consider the closed cube C(∞) ϵ :={∆∈R d :∥∆∥ ∞ ≤ϵ}.(C19) Controlling the estimation error∥∆ ML∥∞, therefore reduces to showing that the fixed-point equation Eq

    Application of Chebyshev’s inequality to bound the norm. Forϵ >0, let us consider the closed cube C(∞) ϵ :={∆∈R d :∥∆∥ ∞ ≤ϵ}.(C19) Controlling the estimation error∥∆ ML∥∞, therefore reduces to showing that the fixed-point equation Eq. (C17) derived in Sec. C admits a solution insideC (∞) ϵ . Equivalently, it suffices to verify that the maximum likelihood ...

  16. [16]

    We now combine the bounds obtained in Sec

    Brouwer fixed-point theorem. We now combine the bounds obtained in Sec. C 3 to conclude the proof. To this end, we introduce the finite- sample margin τ− :=ϵ− ∥F−1∥op cH √ d ϵ−1 2 ∥F−1∥op cR d ϵ2,(C42) which quantifies the residual budget available for the score term after accounting for the linear and nonlinear correction terms. We next define the event ...

  17. [17]

    (C54), we invoke the Berry–Esseen theorem, which quantifies the rate of convergence in the central limit theorem

    Application of Berry-Esseen Theorem To refine the upper bound in Eq. (C54), we invoke the Berry–Esseen theorem, which quantifies the rate of convergence in the central limit theorem. Specifically, it provides a uniform bound order ofO(M −1/2) on the deviation between the cumulative distribution function of a normalized sum of independent random variables ...

  18. [18]

    (D7) In this section, we derive a lower bound on the required sample size by the following procedure

    Proof sketch Our goal is to determine the minimal sample size M0(ϵ, δ, d) such that, for prescribed accuracyϵ >0 and confidence level 1−δwith 0< δ≤1, the MLE ˜θML satisfies ∀M≥M 0(ϵ, δ, d) : Pr h ˜θML −θ ∞ ≤ϵ i ≥1−δ. (D7) In this section, we derive a lower bound on the required sample size by the following procedure. Define the accuracy event A(ϵ) := n ˜θ...

  19. [19]

    (D12) Taking the inner product with the basis vectore a, we obtain eT a F−1 θ Sθ =∆ ML a −e T a F−1 θ (Hθ +F θ)∆ ML −e T a F−1 θ rθ(∆ML)

    T aylor expansion of score function We begin with the expansion ∆ML =F −1 θ Sθ +F −1 θ (Hθ +F θ)∆ ML +F −1 θ rθ(∆ML). (D12) Taking the inner product with the basis vectore a, we obtain eT a F−1 θ Sθ =∆ ML a −e T a F−1 θ (Hθ +F θ)∆ ML −e T a F−1 θ rθ(∆ML). (D13) By taking absolute values and applying the triangle inequality, we obtain eT a F−1 θ Sθ ≤ ∆ML a...

  20. [20]

    B, we obtain Pr " √ M eT a F−1 θ Sθ σθ,a ≤x # ≤1−2 Z ∞ x 1√ 2π e− t2 2 dt+ 2Cρ σ3 θ,a √ M , (D22) where we definex:= √ M τ+/σθ,a for notational simplicity

    Application of Berry-Esseen Theorem By application of Berry-Esseen theorem in Sec. B, we obtain Pr " √ M eT a F−1 θ Sθ σθ,a ≤x # ≤1−2 Z ∞ x 1√ 2π e− t2 2 dt+ 2Cρ σ3 θ,a √ M , (D22) where we definex:= √ M τ+/σθ,a for notational simplicity. To upper bound the Gaussian tail integral, we invoke the Mills ratio inequality in Sec. B: for all x >0, x x2 + 1 1√ 2...

  21. [21]

    (D32) Using LambertW-function in Sec

    LambertW-function Our goal is to determineM 1(ϵ, δ, d) such that ∀M≥M 1(ϵ, δ, d) : 1√ 2π 1 x e− x2 2 ≤δ ′ ⇔x 2ex2 ≥ 1 2πδ ′2 . (D32) Using LambertW-function in Sec. B, Eq. (D32) can be reduced to M≥W 0 δ′−2/2π τ −2 + σ2 θ,a.(D33) We note that by definition,W 0(x=e) = 1. In principle, one could determineM 1 by solving Eq. (D33). However, sinceδ ′ itself is...

  22. [22]

    F urther lower bound using concavity of Lambert W-function Forz≥0,W 0(z) is concave (see Sec. B). Therefore, sinceδ ′ ≥δby definition, we have W0 δ′−2/2π ≥ δ2 δ′2 W0 δ−2/2π .(D34) Consequently, letM 2(ϵ, δ, d) denote the minimal value such that ∀M≥M 2(ϵ, δ, d) :M≥ δ2 δ′2 W0 δ−2/2π τ −2 + σ2 θ,a. (D35) Here, we note thatδ ′ ≥0 andτ + ≥0. Therefore, Eq. (D3...

  23. [23]

    Asymptotic unbiased estimator We establish asymptotic unbiasedness under mild concentration and moment assumptions. Theorem 5.Assume that there existsϵ 0 >0such that for anyδ∈(0,1]and anyϵ∈(0, ϵ 0]there exists an integerM 0 =M 0(δ, ϵ)satisfying, for allM≥M 0, Pr h |˜θ(x)−θ| ≤ϵ i ≥1−δ.(G1) Moreover, assume there existsη >0such that sup M≥1 E h |˜θ−θ| 1+η i...

  24. [24]

    Biased estimator By Theorem 5, for any scalar estimator ˜θthat satisfies the moment condition (G2), failure of asymptotic unbiasedness implies failure of the concentration property (G1). Equivalently, there existδ∈(0,1] and ϵ∈(0, ϵ 0] such that for every integerM 0, there exists M≥M 0 satisfying Pr h |˜θ(x)−θ| ≤ϵ i <1−δ.(G8) In the singular-FIM setting, t...

  25. [25]

    , xM ∈ {0,1}be i.i.d

    Bernoulli model Letx 1, . . . , xM ∈ {0,1}be i.i.d. Bernoulli random variables with parameterθ∈(0,1), and defineS:=PM i=1 xi. The log-likelihood function is given by ℓθ(x) =Slogθ+ (M−S) log(1−θ), θ∈Θ := (0,1). (H1) (A1).The first derivative is ℓ′ θ(x) = S θ − M−S 1−θ .(H2) Settingℓ ′ θ(x) = 0 yields the unique solution θML = S M ,(H3) provided 0< S < M. (...

  26. [26]

    ,yM ∈R d be i.i.d

    Gaussian model with known variance Lety 1, . . . ,yM ∈R d be i.i.d. Gaussian random vectors distributed asN(θ,Σ), where the covariance matrixΣ≻ 0 is known andθ∈R d is unknown. Up to an additive constant, the log-likelihood is ℓθ(x) =− 1 2 MX i=1 (yi −θ) TΣ−1(yi −θ) T), µ∈Θ :=R d. (H4) (A1).The gradient ofl M is ∇µℓθ(x) =MΣ −1( ¯y−θ), ¯y:= 1 M MX i=1 yi.(H...

  27. [27]

    , nK) be multinomial counts with total countM= PK k=1 nk and parameter vectorθ= (θ1,· · ·, θK), whereθ k >0 and PK k=1 θk = 1

    Multinomial model Let (n 1, . . . , nK) be multinomial counts with total countM= PK k=1 nk and parameter vectorθ= (θ1,· · ·, θK), whereθ k >0 and PK k=1 θk = 1. The log- likelihood is ℓθ(x) = KX k=1 nk logθ k,(H6) defined on the probability simplex. (A1).Its derivative is ℓ′ θ(x) = KX k=1 nk θk .(H7) The unique stationary point isθ ML = 1 M P i xi. Moreov...

  28. [28]

    , xM be i.i.d

    Poisson model Letx 1, . . . , xM be i.i.d. Poisson random variables with meanθ >0. The log-likelihood is ℓθ(x) = MX i=1 xi logθ−θ + const, θ∈Θ := (0,∞). (H8) (A1).Its derivative is ℓ′ θ(x) = MX i=1 xi θ −1.(H9) The unique stationary point isθ ML = 1 M P i xi. (A2).The functionℓ θ(x) is infinitely differentiable in the range Θ

  29. [29]

    , xM be i.i.d

    General exponential family (canonical parameterization) Letx 1, . . . , xM be i.i.d. samples from aregular exponential family with canonical parameterθ∈Θ⊂R d and density pθ(x) =h(x) exp θTt(x)−A(θ) ,θ∈Θ,(H10) wheret(x)∈R d is the sufficient statistic andA(θ) is the log-partition function. Define the aggregated statistic T:= MX i=1 t(xi)∈R d.(H11) 31 The l...

  30. [30]

    Throughout, we impose the conditionλ 0 = 1

    Pauli Eigenvalue Estimation In this subsection, we verify that assumptions (A1)– (A2) hold for Pauli eigenvalue estimation under the standard measurement model. Throughout, we impose the conditionλ 0 = 1. For simpler expression, let us denotep λ(x) in Eq. (64) pλ(x) :=p x.(H15) Here,{p x}4n−1 x=0 are the measurement outcome probabilities. These probabilit...

  31. [31]

    Erhard, J

    A. Erhard, J. J. Wallman, L. Postler, M. Meth, R. Stricker, E. A. Martinez, P. Schindler, T. Monz, J. Emerson, and R. Blatt, Characterizing large-scale quantum computers via cycle benchmarking, Nature communications10, 5347 (2019)

    2019

  32. [32]

    Hashim, L

    A. Hashim, L. B. Nguyen, N. Goss, B. Marinelli, R. K. Naik, T. Chistolini, J. Hines, J. Marceaux, Y. Kim, P. Gokhale, T. Tomesh, S. Chen, L. Jiang, S. Ferracin, K. Rudinger, T. Proctor, K. C. Young, I. Siddiqi, and R. Blume-Kohout, Practical introduction 32 to benchmarking and characterization of quantum computers, PRX Quantum6, 030202 (2025)

    2025

  33. [33]

    Harper, S

    R. Harper, S. T. Flammia, and J. J. Wallman, Efficient learning of quantum noise, Nat. Phys.16, 1184 (2020)

    2020

  34. [34]

    S. Chen, Z. Zhang, L. Jiang, and S. T. Flammia, Efficient self-consistent learning of gate set pauli noise, PRX Quantum7, 010305 (2026)

    2026

  35. [35]

    D. K. Tuckett, S. D. Bartlett, and S. T. Flammia, Ultrahigh error threshold for surface codes with biased noise, Phys. Rev. Lett.120, 050505 (2018)

    2018

  36. [36]

    E. H. Chen, T. J. Yoder, Y. Kim, N. Sundaresan, S. Srinivasan, M. Li, A. D. C´ orcoles, A. W. Cross, and M. Takita, Calibrated decoders for experimental quantum error correction, Phys. Rev. Lett.128, 110504 (2022)

    2022

  37. [37]

    Van Den Berg, Z

    E. Van Den Berg, Z. K. Minev, A. Kandala, and K. Temme, Probabilistic error cancellation with sparse pauli–lindblad models on noisy quantum processors, Nat. Phys.19, 1116 (2023)

    2023

  38. [38]

    Y. Kim, A. Eddins, S. Anand, K. X. Wei, E. Van Den Berg, S. Rosenblatt, H. Nayfeh, Y. Wu, M. Zaletel, K. Temme,et al., Evidence for the utility of quantum computing before fault tolerance, Nature618, 500 (2023)

    2023

  39. [39]

    Quantum error correction below the surface code threshold, Nature638, 920 (2025)

    2025

  40. [40]

    Huang, R

    H.-Y. Huang, R. Kueng, and J. Preskill, Predicting many properties of a quantum system from very few measurements, Nat. Phys.16, 1050 (2020)

    2020

  41. [41]

    S. Chen, J. Cotler, H.-Y. Huang, and J. Li, Exponential separations between learning with and without quantum memory, in2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)(IEEE, 2022) pp. 574–585

    2022

  42. [42]

    J. Haah, R. Kothari, R. O’Donnell, and E. Tang, Query-optimal estimation of unitary channels in diamond distance, in2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)(IEEE, 2023) pp. 363–390

    2023

  43. [43]

    H.-Y. Hu, M. Ma, W. Gong, Q. Ye, Y. Tong, S. T. Flammia, and S. F. Yelin, Ansatz-free hamiltonian learning with heisenberg-limited scaling, PRX Quantum 6, 040315 (2025)

    2025

  44. [44]

    Huang, Y

    H.-Y. Huang, Y. Tong, D. Fang, and Y. Su, Learning many-body hamiltonians with heisenberg-limited scaling, Phys. Rev. Lett.130, 200403 (2023)

    2023

  45. [45]

    Y. Wu, Y. Zhang, C. Wang, and X. Yuan, Hamiltonian dynamics learning: A scalable approach to quantum process characterization (2025), arXiv:2503.24171

    Pith/arXiv arXiv 2025

  46. [46]

    Huang, R

    H.-Y. Huang, R. Kueng, and J. Preskill, Information- theoretic bounds on quantum advantage in machine learning, Phys. Rev. Lett.126, 190505 (2021)

    2021

  47. [47]

    Z.-H. Liu, R. Brunel, E. E. Østergaard, O. Cordero, S. Chen, Y. Wong, J. A. Nielsen, A. B. Bregnsbo, S. Zhou, H.-Y. Huang,et al., Quantum learning advantage on a scalable photonic platform, Science389, 1332 (2025)

    2025

  48. [48]

    S. Chen, S. Zhou, A. Seif, and L. Jiang, Quantum advantages for pauli channel estimation, Phys. Rev. A 105, 032435 (2022)

    2022

  49. [49]

    Huang, M

    H.-Y. Huang, M. Broughton, J. Cotler, S. Chen, J. Li, M. Mohseni, H. Neven, R. Babbush, R. Kueng, J. Preskill,et al., Quantum advantage in learning from experiments, Science376, 1182 (2022)

    2022

  50. [50]

    Coroi and C

    E. Coroi and C. Oh, Exponential advantage in continuous-variable quantum state learning (2025), arXiv:2501.17633

    arXiv 2025

  51. [51]

    M. C. Caro, Learning quantum processes and hamiltonians via the pauli transfer matrix, ACM Transactions on Quantum Computing5, 1 (2024)

    2024

  52. [52]

    S. Chen, C. Oh, S. Zhou, H.-Y. Huang, and L. Jiang, Tight bounds on pauli channel learning without entanglement, Phys. Rev. Lett.132, 180805 (2024)

    2024

  53. [53]

    A. Seif, S. Chen, S. Majumder, H. Liao, D. S. Wang, M. Malekakhlagh, A. Javadi-Abhari, L. Jiang, and Z. K. Minev, Entanglement-enhanced learning of quantum processes at scale (2024), arXiv:2408.03376

    Pith/arXiv arXiv 2024

  54. [54]

    Kim and C

    M. Kim and C. Oh, On the fundamental resource for exponential advantage in quantum channel learning (2025), arXiv:2507.11089

    arXiv 2025

  55. [55]

    C. Oh, S. Chen, Y. Wong, S. Zhou, H.-Y. Huang, J. A. H. Nielsen, Z.-H. Liu, J. S. Neergaard-Nielsen, U. L. Andersen, L. Jiang, and J. Preskill, Entanglement- enabled advantage for learning a bosonic random displacement channel, Phys. Rev. Lett.133, 230604 (2024)

    2024

  56. [56]

    Giovannetti, S

    V. Giovannetti, S. Lloyd, and L. Maccone, Quantum- enhanced measurements: beating the standard quantum limit, Science306, 1330 (2004)

    2004

  57. [57]

    Giovannetti, S

    V. Giovannetti, S. Lloyd, and L. Maccone, Quantum metrology, Phys. Rev. Lett.96, 010401 (2006)

    2006

  58. [58]

    Giovannetti, S

    V. Giovannetti, S. Lloyd, and L. Maccone, Advances in quantum metrology, Nat. Photon.5, 222 (2011)

    2011

  59. [59]

    T. J. Proctor, P. A. Knott, and J. A. Dunningham, Multiparameter Estimation in Networked Quantum Sensors, Phys. Rev. Lett.120, 080501 (2018)

    2018

  60. [60]

    Gessner, L

    M. Gessner, L. Pezz` e, and A. Smerzi, Sensitivity bounds for multiparameter quantum metrology, Phys. Rev. Lett. 121, 130503 (2018)

    2018

  61. [61]

    Albarelli, J

    F. Albarelli, J. F. Friel, and A. Datta, Evaluating the holevo cram´ er-rao bound for multiparameter quantum metrology, Phys. Rev. Lett.123, 200503 (2019). [32]Quantum Detection and Estimation Theory(Academic Press, 1976)

    2019

  62. [62]

    S. L. Braunstein and C. M. Caves, Statistical distance and the geometry of quantum states, Phys. Rev. Lett. 72, 3439 (1994)

    1994

  63. [63]

    M. G. Paris, Quantum estimation for quantum technology, Int. J. Quantum Inf7, 125 (2009)

    2009

  64. [64]

    J. Liu, H. Yuan, X.-M. Lu, and X. Wang, Quantum fisher information matrix and multiparameter estimation, J. Phys. A: Math. Theor.53, 023001 (2020)

    2020

  65. [65]

    S. Ragy, M. Jarzyna, and R. Demkowicz-Dobrza´ nski, Compatibility in multiparameter quantum metrology, Phys. Rev. A94, 052108 (2016)

    2016

  66. [66]

    J. S. Sidhu, Y. Ouyang, E. T. Campbell, and P. Kok, Tight bounds on the simultaneous estimation of incompatible parameters, Phys. Rev. X11, 011028 (2021)

    2021

  67. [67]

    Albarelli and R

    F. Albarelli and R. Demkowicz-Dobrza´ nski, Probe incompatibility in multiparameter noisy quantum metrology, Phys. Rev. X12, 011039 (2022)

    2022

  68. [68]

    Watanabe, T

    Y. Watanabe, T. Sagawa, and M. Ueda, Optimal measurement on noisy quantum systems, Phys. Rev. Lett.104, 020401 (2010)

    2010

  69. [69]

    R. M. Corless, G. H. Gonnet, D. E. Hare, D. J. Jeffrey, and D. E. Knuth, On the lambert w function, Adv. Comput. Math.5, 329 (1996). 33

    1996

  70. [70]

    F. W. Olver,NIST handbook of mathematical functions hardback and CD-ROM(Cambridge university press, 2010)

    2010

  71. [71]

    R. A. Horn and C. R. Johnson,Matrix Analysis (Cambridge University Press, 1985)

    1985

  72. [72]

    Zhang and D

    D.-J. Zhang and D. M. Tong, Inferring physical properties of symmetric states from the fewest copies, Phys. Rev. Lett.133, 040202 (2024)

    2024

  73. [73]

    S. Zhou, M. Zhang, J. Preskill, and L. Jiang, Achieving the Heisenberg limit in quantum metrology using quantum error correction, Nat. Commun.9, 78 (2018)

    2018

  74. [74]

    H. Kwon, K. Tsubouchi, C.-T. Chu, and L. Jiang, Criteria for unbiased estimation: applications to noise- agnostic sensing and learnability of quantum channel (2025), arXiv:2503.17362

    Pith/arXiv arXiv 2025

  75. [75]

    Tsang, F

    M. Tsang, F. Albarelli, and A. Datta, Quantum semiparametric estimation, Phys. Rev. X10, 031023 (2020)

    2020

  76. [76]

    S. Chen, W. Gong, and S. Zhou, Instance-optimal high-precision shadow tomography with few-copy measurements: A metrological approach (2026), arXiv:2602.04952

    arXiv 2026

  77. [77]

    A. C. Berry, The accuracy of the gaussian approximation to the sum of independent variates, Trans. Amer. Math. Soc.49, 122 (1941)

    1941

  78. [78]

    Durrett,Probability: theory and examples, Vol

    R. Durrett,Probability: theory and examples, Vol. 49 (Cambridge university press, 2019)

    2019

  79. [79]

    Feller,An introduction to probability theory and its applications, Volume 2, Vol

    W. Feller,An introduction to probability theory and its applications, Volume 2, Vol. 2 (John Wiley & Sons, 1991)

    1991

  80. [80]

    Z. W. Birnbaum, An inequality for mill’s ratio, Ann. Math. Stat.13, 245 (1942)

    1942

Showing first 80 references.