Toward Instance-Optimal State Certification With Incoherent Measurements

1 Introduction

• Non-adaptive incoherent certification requires O(d^3/2/ε^2) copies in the worst case, while coherent measurements achieve O(d/ε^2) and learning requires Θ(d^2/ε^2).For maximally mixed σ, the non-adaptive incoherent bound is necessary and sufficient.Source: §1 · p. 3, §1.1 · p. 4
• The paper asks whether certification complexity can improve for approximately low-rank σ and whether a simple instance-dependent functional characterizes the optimal copy complexity.A maximally mixed state over a known r-dimensional subspace already admits an O(r^3/2/ε^2) upper bound.Source: §1 · pp. 3–4

1.1 Our Results

• The main result gives an instance-optimal characterization for non-adaptive incoherent measurements, up to logarithmic factors, using effective ranks and fidelity with the maximally mixed state.The construction projects away eigenvectors carrying at most Θ(ε^2) or Θ(ε) mass, then normalizes.Source: §1.1 · p. 4
• Unless σ concentrates 1−poly(ε) mass on o(d) dimensions, complexity equals the worst-case complexity multiplied by its fidelity with the maximally mixed state.Unlike classical instance-optimal testing, the quantum bound has no clean dimension-independent controlling functional and does not remove the largest eigenvalue.Source: §1.1 · p. 4
• Quantum complexity can increase with dimension even when the classical analogue becomes easier, because ρ may differ through off-diagonal entries while sharing σ's diagonal.Theorem 1.1 gives eΘ(d^1/2/ε^2) in the highlighted example, attributed to extra off-diagonal degrees of freedom.Source: §1.1 · pp. 4–5
• Adaptive incoherent measurements still face a dimensional curse, although the resulting lower bound is not instance-optimal and leaves tight characterization open.For maximally mixed σ, the adaptive lower bound recovers the best known mixedness-testing lower bound, with a remaining d^1/2 versus d^1/3 gap.Source: §1.1 · p. 5

1.2 Related Work

• The work extends prior quantum testing results while focusing on the non-asymptotic dependence on d and ε, unlike asymptotic discrimination studies.Related classical work established instance-optimal identity-testing bounds, especially, which motivates the comparison.Source: §1 · p. 3, §1.2 · pp. 5–6

2 Overview of Techniques

• Lower bounds reduce certification to distinguishing σ from a mixture of ε-far alternatives, assuming without loss of generality that σ is diagonal.The framework builds on lower-bound analyses for mixedness testing with entangled and incoherent measurements [OW15] [BCL20].Source: §2 · p. 6

2.1 Instance-Optimal Lower Bounds for Identity Testing

• [VV17] obtains classical instance-optimal lower bounds by bucketing q’s probabilities, applying Paninski perturbations within each scale, and combining the resulting sign-pattern alternatives.Moment bounds recover the bound up to poly-logarithmic factors in d/ε; unlike the classical proof, the quantum analysis cannot straightforwardly use Poissonization.Source: §2.1 · p. 7

2.2 Passing to the Quantum Setting

• Quantum Paninski alternatives require scale-sensitive perturbations and block-diagonal Haar rotations, but the generalized construction alone can fail to yield the right lower bound.It gives roughly eΩ(∥σ′∥2/5/ε2), which may be much weaker than the target bound; off-diagonal perturbations supply the missing hard instances, including an Ω(d1√d2/ε2) bound in the stated two-bucket regime.Source: §2.2 · pp. 8–10

2.3 Upper Bound

• The upper bound buckets σ’s eigenvalues, uses BasicCertify within non-negligible principal or paired off-diagonal blocks, and handles the negligible bucket with a projector measurement requiring O(1/ε2) copies.An averaging argument ensures that an ε-far ρ falls into one of these cases, while the negligible bucket contains eigenvalues totaling O(ε2).Source: §2.3 · pp. 10–11

Why Do the Upper and Lower Bounds “Line Up”?

• The bounds line up because principal- and off-diagonal block lower-bound constructions match the hardest subproblems isolated by the upper-bound case analysis.Truncation removes only small eigenmass because complexity is dominated by non-negligible buckets, although the lower-bound truncation gap Θ(ε2) versus Θ(ε) remains a conjectured technical artifact.Source: Why Do the Upper and Lower Bounds… · pp. 11–12
• Diagonal and off-diagonal eigenvalue-bucket cases each yield measurement bounds that combine, up to logarithmic factors, into the effective-dimension and Schatten-norm dependence.For diagonal blocks, Lemma 6.10 supplies the detection bound; off-diagonal blocks are handled by Lemma 6.11, with j = j′ representing case (A) and j ≠ j′ representing case (B).Source: Why Do the Upper and Lower Bounds… · p. 12
• The bucket calculation identifies the resulting dependence, up to log factors, with d_eff^1/2 · ∥σ∥_1/2, where ∥·∥_1/2 is the Schatten 1/2-quasinorm.There are logarithmically many nonempty non-negligible eigenvalue buckets of σ.Source: Why Do the Upper and Lower Bounds… · p. 12
• The lower-bound constructions parallel the upper-bound cases, causing matching ∥·∥_2/5 and ∥·∥_1/2 terms to arise for essentially the same reasons.The generalized quantum Paninski and off-diagonal constructions mirror cases (A) and (B) of the upper-bound analysis.Source: Why Do the Upper and Lower Bounds… · p. 12
• The paper reviews testing tools in Section 3, develops the incoherent-measurement lower-bound framework in Section 4, and proves the lower and upper bounds in Sections 5 and 6.Theorem 1.3 is proved in Appendix A, while Appendix B collects deferred proofs.Source: Why Do the Upper and Lower Bounds… · p. 13

3.1 Quantum Property Testing

• Quantum property testing distinguishes two disjoint sets of mixed states using a POVM schedule and post-processing with success probability at least 2/3.A schedule may be adaptive, while a nonadaptive schedule chooses each POVM based only on the measurement index.Source: §3.1 · p. 13
• State certification tests whether an unknown state equals a specified mixed state or is more than ε away in trace norm; maximally mixed certification is mixedness testing.Source: §3.1 · p. 13
• Point-versus-mixture lower bounds compare transcript distributions under a null state and alternatives randomly drawn from a distribution, with total-variation closeness implying a copy lower bound.The framework applies to both nonadaptive and adaptive POVM schedules.Source: §3.1 · p. 14

3.2 Tail Bounds

• The preliminaries establish sub-exponential moment and moment-generating-function bounds, together with concentration for Lipschitz functions of Haar-random unitaries.Source: §3.2 · pp. 14–15

3.3 Weingarten Calculus

• Weingarten calculus expresses Haar-unitary integrals through permutations, cycle traces, and Weingarten functions, providing the identities needed for later calculations.Source: §3.3 · pp. 15–16

3.4 Block Matrices; 3.5 Instance-Optimal Distribution Testing; 3.6 Miscellaneous Facts

• The section also records Schur-complement and block-matrix facts, the classical instance-optimal identity-testing lower bound, and auxiliary norm inequalities.The classical result is transferred to a quantum state-certification lower bound, and separated eigenvalues motivate near-low-rank instances with complexity eTheta(1/ε2).Source: §3.4 · p. 16, §3.5 · p. 17, §3.6 · p. 17

4 General Lower Bound Framework

• The general framework reduces quantum testing lower bounds to distinguishing a null state from a Haar-random mixture of alternative states using unentangled POVM schedules.The analysis tracks transcript distributions generated under the null and mixture hypotheses.Source: §4 · pp. 17–18

4.1 Sufficient Conditions on gU

• The single-copy likelihood-ratio conditions require zero first moments, bounded second moments, and Lipschitz control, preventing any repeatedly measured observable from easily distinguishing null and alternatives.Concentration of Haar-random unitaries then yields sub-exponential control of pairwise likelihood-ratio correlations.Source: §4.1 · pp. 18–19

4.2 Non-adaptive Lower Bounds

• For nonadaptive measurements, chi-squared, KL, and total-variation bounds show that transcript distributions remain close below the threshold implied by the single-copy parameters.The framework recovers the mixedness-testing lower bound Ω(d3/2/ε2) from [BCL20].Source: §4.2 · pp. 19–20

4.3 Adaptive Lower Bounds

• For adaptive measurements, an additional almost-sure likelihood-ratio bound enables a chain-rule argument, recovering the mixedness-testing lower bound Ω(d4/3/ε2) from [BCL20].The result applies when N=o(d/L2) and the likelihood-ratio conditions hold for every measurement.Source: §4.3 · p. 20

5 Nonadaptive Lower Bound for State Certification

• Nonadaptive, unentangled state certification requires instance-dependent copy complexity lower bounds, established through two complementary lower-bound instances.The section’s theorem applies for sufficiently small constant ε, with the analysis yielding an unoptimized constant near 1/3.Source: §5 · pp. 20–21

5.1 Bucketing and Mass Removal

• The bucketing scheme removes at most O(ε) mass to form σ**, while retaining Tr(σ**) ≥ 1 − O(ε).Entries are grouped by dyadic eigenvalue ranges, and additional low-probability entries are removed before constructing the lower-bound instances.Source: §5 · p. 20, §5.1 · p. 21

5.2 Lower Bound Instance I: General Quantum Paninski

• A generalized quantum Paninski construction perturbs diagonal entries within buckets and yields an Ω(∥σ′∥2/5/(ε^2 log(d/ε))) lower bound.The perturbations use balanced positive and negative entries in buckets of size at least two, with random block-diagonal Haar unitaries; measurements can be reduced to respect the bucket structure.Source: §5.2 · p. 22

5.2.1 Bound Under General Perturbations

• The generic perturbation analysis reduces the distinguishing problem to independent bucket subproblems and controls their moments under arbitrary nonadaptive, unentangled POVMs.The argument verifies the required assumptions for each bucket and bounds perturbation sensitivity using the Hilbert–Schmidt distance between unitaries.Source: §5.2.1 · pp. 23–25

5.2.2 Tuning the Perturbations

• Tuning the bucket perturbations gives an Ω(∥σ′∥2/5/ε^2) lower bound when singleton buckets dominate, and otherwise preserves the logarithmic-factor bound.The singleton-dominated case is handled using classical identity-testing lower bounds, while the chosen perturbation magnitudes maintain positivity and trace-distance scale.Source: §5.2.2 · pp. 25–26
• The perturbation-tuning argument bounds the normalization constant and completes the proof of the preceding lower-bound lemma.It chooses the perturbation parameters by bucket, using inequalities for bucket dimensions, the tail ordering, and the stated auxiliary facts.Source: §5.2.2 · pp. 27–28

5.3 Lower Bound Instance II: Perturbing Off-Diagonals

• Off-diagonal perturbations remain valid when ε ≤ d_j′ · 2^(-j/2-j′/2), producing density matrices at trace distance at least ε and a nonadaptive-measurement lower bound.The construction perturbs a diagonal state on two bucket blocks using a Haar-random orthonormal-column matrix, with j = j′ allowed when d_j > 1.Source: §5.3 · pp. 28–29

5.4 Lower Bound Instance III: Corner Case

• If σ has a maximum entry at least 3/4, the corner construction yields an Ω(1/ε^2) lower bound even for adaptive unentangled measurements.For ε ≤ 1/2, the two alternatives are valid density matrices separated by trace distance at least ε; the proof directly controls total variation because the KL divergence may be arbitrarily large.Source: §5.4 · pp. 31–32

5.5 Putting Everything Together

• The proof combines the lower-bound instances by separating cases according to whether some relevant bucket has dimension greater than one.When all dimensions equal one, the argument uses either the corner instance or the off-diagonal instance; otherwise it also invokes the earlier perturbation bound and relates the resulting norms through Lemma 5.26.Source: §5.5 · pp. 32–33
• The remaining case analysis contradicts the assumption that the first scenario of Lemma 5.26 fails, unless d_j∗ is polylogarithmic; this still yields the claimed lower bound because d_eff is polylogarithmic.The argument uses d_j2−j ≥ Ω(ε/log(d/ε)) for j ∈ J∗ and bounds d_eff by O(log(d/ε)·d_j∗).Source: §5.5 · p. 34
• When the first scenario of Lemma 5.26 holds, Lemma 5.5 provides a lower bound of Ω(∥σ∗∥_2/5/(ε^2 log(d/ε))), and assuming it is insufficient leads to another contradiction.The contradiction again follows from the lower bounds on d_j2−j for j ∈ J∗, completing the case analysis after lifting constraint (23).Source: §5.5 · p. 34
• Fact 5.27 expresses the half-norm of a positive semidefinite σ through its trace and fidelity with the maximally mixed state: ∥σ∥_1/2 = d Tr(σ)^2 · F(bσ, ρ_mm), where bσ = σ/Tr(σ).The identity is established by diagonalizing σ without loss of generality and applying the definition of fidelity.Source: §5.5 · p. 34

6 State Certification Algorithm

• Theorem 6.1 gives a certification algorithm for diagonal σ that distinguishes ρ = σ from ||ρ − σ||1 > ε with probability at least 1 − δ using unentangled nonadaptive measurements.The theorem trims the bottom O(ε^2) spectral mass of σ to form σ′ and defines bσ′ and deff from the remaining support; the resulting upper bound nearly matches the lower bound from Section 5.Source: §6 · p. 35

6.1 Simple Subroutine

• BasicCertify uses O(d log(1/δ)/ε^2) copies to distinguish ρ = σ from ||ρ − σ||HS > ε with probability at least 1 − δ.It measures in a Haar-random basis and applies classical L2 identity testing to the resulting outcome distributions; the analysis uses Haar moment calculations and amplification.Source: §6.1 · pp. 35, 37

6.2 Bucketing and Mass Removal

• The bucketing scheme removes a low-probability spectral tail and partitions the remaining eigenvalues into dyadic buckets, with at most log(10d/ε^2) nonempty buckets.The construction also defines normalized within-bucket and cross-bucket matrix blocks used by the later scenario tests.Source: §6.2 · p. 37

6.3 Instance-Near-Optimal Certification

• Lemmas 6.8–6.11 establish Certify’s correctness and copy-complexity guarantee, covering tests for Scenarios 1, 3, and 4, with Scenario 1 requiring O(log(1/δ)/ε^2) copies.The Scenario 1 test succeeds with probability 1 − O(δ), and the Scenario 3 and 4 tests likewise have probability 1 − O(δ).Source: §6.3 · pp. 38–40
• The procedure compares observed outcome fractions against Tr(σ[j, j]) + ε/(40m2) and defines ε′ and ε′′ according to equations (28) and (29).It also treats distinct index pairs j, j′ with d_j ≥ d_j′ using projections onto principal submatrices indexed by S_j ∪ S_j′.Source: §6.3 · p. 41

A Adaptive Lower Bound

• The lower-bound instance uses σ* obtained by zeroing σ’s largest entry and removing at most O(ε log(d/ε)) additional mass.This more aggressive mass-removal procedure distinguishes the adaptive construction from the nonadaptive one.Source: A Adaptive Lower Bound · p. 44
• Adaptive, unentangled state-certification algorithms require a nontrivial copy-complexity lower bound for diagonal target states σ.Theorem A.1 states the result for sufficiently small ε and an absolute constant c.Source: A Adaptive Lower Bound · p. 44
• The appendix follows the earlier lower-bound outline while verifying the additional conditions required for the adaptive framework.The analysis reduces to the lower-bound instance introduced in Section 5.3.Source: A Adaptive Lower Bound · p. 44

A.1 Bucketing and Mass Removal

• The adaptive procedure may remove up to O(ε log(d/ε)) total mass from σ.This is more aggressive than the corresponding nonadaptive mass-removal procedure.Source: §A.1 · p. 45
• σ* is formed by zeroing σ’s largest entry and all entries in a low-probability tail Stail.The tail is defined using the largest index d′ whose cumulative mass is at most 4ε.Source: §A.1 · p. 45
• The surviving nonzero entries of σ* occupy at most O(log(d/ε)) buckets, and Tr(σ*) ≥ 1 − O(ε log(d/ε)).The trace guarantee quantifies how much mass remains after removing the largest entry and the tail.Source: §A.1 · p. 45

A.2 Analyzing Lower Bound II

• The subproblem is formulated through outcome distributions obtained by measuring N copies of σ with a measurement schedule S.This distributional formulation is the object used to analyze adaptive measurement distinguishability.Source: §A.2 · pp. 45–46
• The analysis studies a subproblem comparing ρ = σ with perturbations ρ = σW supported on bucket dimensions dj and dj′.The perturbation W consists of Haar-random orthonormal columns, with dj ≥ dj′ and a stated condition on ε.Source: §A.2 · p. 45
• For adaptive unentangled POVM schedules, the distinguishing task has a copy-complexity lower bound under the specified bucket and ε conditions.The argument focuses primarily on j ≠ j′, with an extension to j = j′ when dj > 1 at constant-factor cost.Source: §A.2 · pp. 45–46
• The proof verifies the assumptions needed by the adaptive lower-bound framework, including a uniform bound on |gU^P(z)|.The bound follows from lower bounds on the diagonal entries in the selected buckets when ε satisfies the stated condition.Source: §A.2 · p. 45

A.3 Putting Everything Together

• The proof divides into Case 1, where d_j = 1 for every j in J*, and Case 2, where some d_j > 1.The two cases determine which lower-bound argument applies.Source: §A.3 · p. 46
• In Case 1, Lemma 5.24 remains valid for adaptive POVM schedules, so the nonadaptive analysis carries over.This provides the main reason the existing lower-bound construction applies in the adaptive setting.Source: §A.3 · p. 46
• A single bucket outside S_tail yields d_eff = 1, ||σ*||_1/2 = O(1), and an Ω(1/ε^2) lower bound.For sufficiently small ε, the argument uses σ_i,i ≥ 3/4 before invoking Lemma 5.24.Source: §A.3 · p. 46
• Otherwise, the lower-bound instance for consecutive relevant buckets gives Ω(2^-j'/ε^2), which is at least Ω(||σ*||_1/2/(ε^2 log(d/ε))) under the stated condition on ε.The comparison uses Fact 3.18.Source: §A.3 · p. 46
• If that ε condition fails, the resulting inequality implies 2^-j ≤ 2ε and contradicts the removal of all buckets with total mass at most 4ε.The contradiction uses the ordering 2^-j' > 2^-j and the definition of S_tail.Source: §A.3 · p. 46
• In Case 2, the proof derives a lower bound through indices j*, j′ and the relations supplied by Facts 3.18 and 5.27.Because d_j* > 1, the indices j* and j′ need not be distinct.Source: §A.3 · p. 46

B.1 Proof of Lemma 4.4

• For a fixed single-copy subproblem and Haar-random U, the proof introduces functions F_V and G to analyze φ_U,V.The construction is made for an arbitrary POVM subproblem P = (M, σ, {σ_U}).Source: §B.1 · p. 47
• F_V is G(V) · L-Lipschitz and has zero mean over U under Assumption 1.This is the content of Lemma B.1.Source: §B.1 · p. 47
• Conditions 2 and 3 bound the expectation and Lipschitz behavior of G, enabling a sub-Gaussian tail bound through Theorem 3.11.The proof uses Jensen’s inequality to obtain E[G(U)] ≤ ς.Source: §B.1 · p. 47
• Lemma B.2 supplies the tail estimate for G, which is then combined with concentration and the parameter choices for Fact 3.20.The parameters include a = 2ς, τ(x) = exp(−cd(x − ς)^2/L^2), and f(x) = exp(−c′ds^2/L^2x^2).Source: §B.1 · p. 47
• The resulting argument bounds Pr_U,V[|φ_U,V| > s] by averaging the chosen tail function over G(V).The proof invokes Lemma B.1 and Theorem 3.11 before applying Fact 3.20 and Lemma B.2.Source: §B.1 · p. 47

B.2 Proof of Theorem 4.8

• Theorem 4.8 gives an adaptive lower bound for distinguishing σ from the mixture of alternatives {σ_U} under Haar measure.The theorem is proved for single-copy subproblems satisfying Assumption 1.Source: §B.2 · p. 48

B.2.1 Additional Notation

• The proof fixes an unentangled adaptive POVM schedule S and conditions each measurement on the transcript of earlier outcomes.The POVM used at time t is denoted M_z<t.Source: §B.2.1 · p. 48
• It defines transcript distributions through time t under σ and under σ_U, together with quantities based on their Radon–Nikodym derivative.These quantities provide the notation needed for the subsequent likelihood-ratio analysis.Source: §B.2.1 · p. 48

B.2.2 Helper Lemmas

• The helper-lemma stage begins with a lemma giving a lower bound on the likelihood ratio between p≤t.Source: §B.2.2 · p. 48
• Lemma B.3 gives Δ(z≤t) ≥ exp(−4ς^2t) for every transcript under Theorem 4.8’s hypotheses.This provides a uniform lower bound on the transcript likelihood ratio.Source: §B.2.2 · p. 48
• The helper analysis bounds a likelihood-related quantity by exp(O(tγ E[G(U)]^2)) when t = o(d/L^2).The restriction ensures the relevant integral is bounded and a second term is negligible.Source: §B.2.2 · p. 49
• Lemma B.4 is proved by controlling transcript-wise fluctuations using convexity, an elementary logarithmic inequality, and Assumption 1’s Conditions 1 and 2.The proof also uses AM-GM, Hölder’s inequality, and a recurrence unrolling.Source: §B.2.2 · pp. 49–50

B.2.3 Putting Everything Together

• For Theorem 4.8, the proof uses the key inequality from the chain rule for KL in [BCL20], applies Cauchy-Schwarz, and invokes Lemmas 4.4, B.4, and B.6.Source: §B.2.3 · pp. 50–51
• The concluding estimates use the fluctuation event bound, the identity E[g_U | z<t] = G_z<t, and Lemma B.3 together with equation (36).These steps yield the final transcript-level bound in the proof.Source: §B.2.3 · pp. 50–51

• The proof first assumes s < m + n, since otherwise b = n is immediate, and then argues by contradiction.Source: §B.3 · p. 51
• The contradiction argument splits according to whether w_{s′+1} = u_{a+1} or w_{s′+1} = v_{b+1}.Source: §B.3 · p. 51
• In the first case, the proof uses maximality of s, the inequalities u_{a+1} ≤ v_{b+1} and u_{i+1} ≥ 2u_i, and v_{b+1} ≤ P_{b+1}.Source: §B.3 · p. 51
• The second case is handled nearly identically, using maximality of s, u_a ≤ v_{b+1}, u_{i+1} ≥ 2u_i, and v_{b+1} ≤ P_{b+1}.Source: §B.3 · pp. 51–52