General framework for verifying pure quantum states in the adversarial scenario

I. INTRODUCTION

• The adversarial setting is difficult because an untrusted device may produce arbitrary correlated or entangled states, while efficient general-purpose approaches were previously unavailable.This limitation matters for high-security applications including blind MBQC and quantum networks.Source: §I · pp. 1–2
• At most three times the nonadversarial test overhead is required for high-precision adversarial verification, using a general recipe applicable even with local projective measurements.The recipe applies to arbitrary pure states and supports efficient verification of several important bipartite and multipartite families.Source: §I · p. 2

A. Verification of pure states: Nonadversarial scenario

• The nonadversarial QSV framework represents a strategy by a verification operator whose spectral gap determines the minimum tests needed to reach infidelity ǫ and significance level δ.For a bad state, the all-pass probability is bounded by [1 −ν(Ω)ǫ]^N, yielding the test-complexity expression for N.Source: A. Verification of pure states:… · pp. 2–3

B. Connection with fidelity estimation

• QSV can estimate fidelity from passing probabilities, and homogeneous strategies make the relevant bounds tight while enabling analytical formulas for practical figures of merit.The fidelity-estimation standard deviation decreases monotonically with the spectral gap and the number of tests.Source: B. Connection with fidelity estimation · pp. 3–4

A. What is verified in QSV?

• The usual nonadversarial assumption that every run is either ideal or below a fixed fidelity threshold is unnatural without identical preparation and yields weaker conclusions about what verification establishes.Under this assumption, passing all tests confirms only that at least one run has fidelity above the threshold, rather than that the device performs well on average.Source: §III · p. 4, A. What is verified in QSV? · p. 4

B. Independent state preparation

• For independently prepared states, the fixed-fidelity assumption can be dropped: passing tests certifies the average fidelity, with the same test-count formula as in the nonadversarial framework.The conclusion does not require identical states across runs, although it assumes the post-verification average fidelity matches the during-verification average.Source: B. Independent state preparation · p. 4

C. Correlated state preparation

• Correlations can invalidate these guarantees: a device that sometimes emits all ideal states and otherwise emits identical imperfect states can pass every test with probability at least a, regardless of N.Thus verification can fail to achieve significance δ<a for the corresponding average infidelity, motivating the adversarial framework.Source: C. Correlated state preparation · p. 5

IV. QUANTUM STATE VERIFICATION IN THE ADVERSARIAL SCENARIO

• Adversarial devices may produce arbitrary correlated or entangled states, making efficient verification important for high-security applications and difficult to analyze.Previous approaches lacked efficient resource-cost determination, and known protocols could require astronomical test counts for small hypergraph states.Source: §IV · p. 5

A. Formulation

• Randomly testing N systems and retaining one application system reduces verification to the conditional fidelity of that remaining system after all tests pass.Permutation invariance can be assumed because the tested systems are chosen randomly.Source: A. Formulation · p. 5
• Correlated preparations can still be verified at arbitrary infidelity ǫ and significance level δ, even when the adversary supplies entangled states.For tensor-power states, the passing probability follows the nonadversarial exponential behavior [1 − ν(Ω)ǫ′]^N.Source: A. Formulation · pp. 5–6

B. Main figures of merit

• The four figures of merit characterize passing probability, conditional fidelity, and the required test number, with F(N, δ, Ω) giving minimum fidelity at significance level δ.The minimum test count N(ǫ, δ, Ω) is defined as the smallest N achieving fidelity at least 1 − ǫ.Source: B. Main figures of merit · p. 6

A. Key observations

• The feasible region R_N,Ω of passing probability and fidelity is a convex polygon determined by the verification operator’s distinct eigenvalues, not their degeneracies.Its boundary determines the figures of merit, and the region concentrates around f = p as N increases, implying F(N, δ, Ω) approaches 1.Source: B. Main figures of merit · p. 6, A. Key observations · p. 7
• If one verification operator has a subset of another’s distinct eigenvalues, it is at least as efficient under the stated spectral condition.Specifically, F(N, δ, Ω′) ≥ F(N, δ, Ω) and N(ǫ, δ, Ω′) ≤ N(ǫ, δ, Ω).Source: A. Key observations · p. 7

B. Computation of the verification precision

• Verification precision can be computed by linear programming, with piecewise-linear boundary functions whose extrema correspond to polygon vertices and often require distributions supported on at most two points.The resulting relations connect ζ and η to the fidelity figures of merit through Eqs. (35)–(37).Source: B. Computation of the verification… · pp. 7–8

C. Properties of the main figures of merit

• ζ is convex and nondecreasing in δ, η is concave and increasing in f, and both fidelity figures increase with their respective conditioning parameter.The stated strict-increase ranges depend on the critical threshold δc.Source: C. Properties of the main figures of… · p. 8
• The pairs of auxiliary functions are inverse-related through η(N, ζ(N, δ, Ω), Ω) = max{δ, δc} and ζ(N, η(N, f, Ω), Ω) = f.The corresponding saturation conditions are specified by the critical threshold and f = 1.Source: C. Properties of the main figures of… · p. 8
• The required test number increases with stricter infidelity and significance targets and can be computed equivalently from ζ, η, or F.The equivalences are given by Eqs. (40)–(42).Source: C. Properties of the main figures of… · p. 8

VI. HOMOGENEOUS STRATEGIES

• For unrestricted measurements, an optimal performance can always be achieved by a homogeneous strategy whose non-target eigenvalues are equal.This makes homogeneous strategies central to adversarial quantum state verification.Source: §VI · p. 9

A. Singular homogeneous strategy

• A singular homogeneous strategy with λ = 0 has unsatisfactory 1/δ scaling in the adversarial scenario despite being optimal nonadversarially.Nonsingular homogeneous strategies can achieve better scaling behavior.Source: A. Singular homogeneous strategy · p. 9

1. Verification precision

• Theorem 1 determines achievable fidelity from N, δ, and λ through F(N, δ, λ) = ζ(N, δ, λ)/δ, with k∗ selected by an explicit threshold condition.The resulting fidelity decreases monotonically with k, and the δ- and λ-dependence is illustrated for N = 2 and N = 10.Source: §1 · p. 10, Figure 2 · p. 10

2. Number of required tests

• Theorem 2 gives the minimum test number N(ǫ, δ, λ) for homogeneous strategies, with k∗ determined by δ ≤ λ^k/(F + λǫ).The associated bounds are saturated in specified δ intervals and when log_λ δ is an integer.Source: §2 · pp. 11–12
• Small-λ homogeneous strategies are inefficient for high-precision verification, such as ǫ, δ ≤ 0.1.This behavior is reflected in the test-number bounds and the variation of N with λ.Source: §2 · p. 11, Figure 4 · p. 11, §1 · p. 12

1. Optimal strategies in the high-precision limit ǫ, δ →0

• For high precision, N(ǫ, δ, λ) ≈ (λǫ ln λ)^−1 ln δ, matching the nonadversarial scaling in ǫ and δ for nonsingular homogeneous strategies.The approximation is accurate across most relevant parameters but becomes poor when λ is very small.Source: §1 · p. 12
• The high-precision efficiency function is minimized at λ = 1/e, yielding an overhead of e relative to the nonadversarial benchmark.The choice λ = 1/e is nearly optimal for practical precisions ǫ, δ ≤ 0.1, and local projective measurements suffice for several important state families.Source: §1 · p. 12

2. Optimal strategies in the limit δ →0

• The optimal λ∗(ǫ) decreases monotonically from 1/e at ǫ = 0 to 0 at ǫ = 1 and is concave in ǫ.The normalized test number approaches 1 as ǫ → 0; it remains at least 0.965 for ǫ ≤ 0.5 and at least 0.999 for ǫ ≤ 0.1 when benchmarked against λ = 1/e.Source: §2 · p. 13
• The benchmark homogeneous strategy λ = 1/e is nearly optimal across most practically relevant infidelities, although smaller λ can outperform it when ǫ is large.For λ > 1/e, the strategy is less efficient than the benchmark, while for sufficiently small λ the normalized cost can become lower at large ǫ.Source: §2 · p. 13

VII. SINGLE-COPY VERIFICATION

• Single-copy verification is characterized by an exact condition relating infidelity ǫ and significance level δ, with the feasible region compared directly against the nonadversarial case.For δ ≤ 1/2, the paper gives a corresponding lower-bound condition on ǫ.Source: A. Single-copy verification with… · p. 14, Figure 6 · p. 14

A. Single-copy verification with homogeneous strategies

• For homogeneous strategies, single-copy verification requires 0 < λ < δ, excluding β(Ω) = 0 and β(Ω) ≥ 1/2 when δ ≤ 1/2.Except at δ = 5/9, the optimal homogeneous strategy is unique; at δ = 5/9, λ = 0 and λ = 1/3 are both optimal.Source: A. Single-copy verification with… · p. 14

B. Single-copy verification with general strategies

• For general strategies, single-copy efficiency is determined by the second-largest and smallest eigenvalues, β and τ, rather than by homogeneity alone.A single test is impossible for β = 0 or β ≥ 1/2 when δ ≤ 1/2.Source: B. Single-copy verification with… · p. 15

A. Singular verification strategies

• Singular verification strategies retain a suboptimal 1/δ dependence, despite improving substantially over earlier quantum-de-Finetti-based approaches.The relevant bounds are nontrivial only above stated δ thresholds and become tight in specified regimes.Source: A. Singular verification strategies · pp. 15–16

B. Nonsingular verification strategies

• Nonsingular strategies have the same ǫ−1 and δ−1 scaling as nonadversarial verification when the smallest eigenvalue τ is bounded below by a positive constant.Their bounds become nearly tight in the high-precision limit, while very small τ limits efficiency.Source: B. Nonsingular verification strategies · pp. 16–17

IX. GENERAL RECIPE TO VERIFYING PURE STATES IN THE ADVERSARIAL SCENARIO

• The recipe mixes a verification operator with the identity, performing the trivial test with probability p, thereby increasing the smallest eigenvalues and hedging adversarial effects.The modified eigenvalues are β_p = 1 − ν + pν and τ_p = (1 − p)τ + p.Source: §IX · p. 17, A. The recipe · p. 17

A. The recipe

• Optimizing p yields a hedged strategy whose high-precision overhead is largely insensitive to τ; the difference across τ values is below 12%.The optimal p∗, prefactor h∗, and overhead νh∗ are summarized in Fig. 7.Source: A. The recipe · p. 17, Figure 7 · p. 18

B. Properties of hedged verification strategies

• In the homogeneous case, νh*(ν,1−ν) is strictly increasing and exceeds 1, while its limit approaches 1 as ν approaches zero.Source: B. Properties of hedged verification… · p. 18
• For hedged strategies, p*(ν,τ) is nondecreasing in ν and nonincreasing in τ, and the optimal probability can be characterized by bounds and, in one regime, a unique equation.Source: B. Properties of hedged verification… · pp. 18–19

C. Overhead of QSV in the adversarial scenario

• The overhead νh*(ν,τ) becomes negligible as ν approaches zero, with upper bounds 1.09, 1.19, 1.31, 1.45, and 1.61 for ν ≤ 0.1, 0.2, 0.3, 0.4, and 0.5, respectively.Source: B. Properties of hedged verification… · p. 18
• The adversarial protocol has the same scaling in ǫ^-1 and δ^-1 as nonadversarial verification, with overhead at most four times for ǫ,δ ≤ 1/4 and three times for ǫ,δ ≤ 1/10.Source: C. Overhead of QSV in the adversarial… · p. 20
• The overhead bound is independent of the specific verification construction once its verification operator is fixed, and the adversarial protocol reuses the nonadversarial measurement settings apart from the trivial test.Source: C. Overhead of QSV in the adversarial… · p. 20
• The optimized hedged strategy is weakly sensitive to the smallest eigenvalue τ: the difference between extreme τ choices is below 12%, while p = p*(ν) and p = ν/e are nearly optimal.Source: C. Overhead of QSV in the adversarial… · p. 20

A. Minimum measurement settings for verifying multipartite pure states

• Each entangled party needs at least two adaptive local measurement settings, while two settings suffice for several important state families.More settings can improve efficiency in total test count.Source: A. Minimum measurement settings for… · p. 21

B. Maximally entangled states and GHZ states

• The maximally entangled-state strategy has a nearly tight nonadversarial test bound, and adding a trivial test yields a homogeneous adversarial strategy with β(Ω)=1/e optimal at high precision.The resulting adversarial bound is nearly tight when δ≤1/e.Source: B. Maximally entangled states and GHZ… · p. 21

C. Bipartite pure states

• For general bipartite pure states, adaptive two-way measurements attain the best known separable-measurement spectral gap, and the resulting homogeneous strategy supports high-precision adversarial verification.The construction also applies to fidelity estimation and does not rely on self-testing.Source: C. Bipartite pure states · pp. 21–22

D. Stabilizer states

• For stabilizer and graph states, the PLM protocol is nearly optimal adversarially, with test-count scaling in ǫ and δ independent of qubit number and the specific state.Both scaling behaviors are optimal, improving over the previously best graph-state requirement of ⌈m3/(δǫ)⌉ tests, or ⌈n3/(δǫ)⌉ in the worst case.Source: D. Stabilizer states · pp. 22–23

E. Qudit stabilizer states

• For prime local dimension d, the qudit stabilizer protocol uses (d^n−1)/(d−1) distinct tests and becomes more efficient as d increases.Prime-dimensional qudit stabilizer states with d>2 can be verified more efficiently than qubit stabilizer states.Source: E. Qudit stabilizer states · p. 23
• For connected prime-dimensional qudit graph states, one local-projective test can certify genuine multipartite entanglement at sufficiently high significance levels and large enough d.The one-test guarantee applies for any given significance level when d is large enough, assuming d is prime.Source: E. Qudit stabilizer states · pp. 23–24

F. Hypergraph states

• n measurement settings are reduced to at most ∆(G) + 1 without adaptation for hedged coloring, or χ(G) with an optimal coloring.The protocol is dramatically more efficient than previous hypergraph-state protocols and supports applications including verifiable blind MBQC and quantum supremacy.Source: F. Hypergraph states · p. 24

G. Weighted graph states

• For weighted graph states, hedged coloring achieves the same verification efficiency as for hypergraph states in the adversarial scenario.The construction uses p = ν/e and reaches the optimal significance-level scaling described in the paper.Source: G. Weighted graph states · p. 24

H. Dicke states

• Dicke states obtain adversarial verification with a test count comparable to the nonadversarial case, despite no previously known protocol for general Dicke states.The broader recipe yields about nǫ−1 ln δ−1 tests for general hypergraph, weighted graph, and Dicke states.Source: H. Dicke states · p. 25

XI. COMPARISON WITH OTHER APPROACHES

• QSV, DFE, and self-testing answer different questions and rely on different assumptions, so their efficiencies cannot be compared completely fairly.QSV decides whether fidelity crosses a threshold, whereas tomography reconstructs the state, DFE estimates fidelity, and self-testing does not trust measurement devices.Source: §XI · pp. 25–26

XII. SUMMARY

• The recipe transfers efficient nonadversarial protocols to the adversarial setting, enabling efficient local-projective verification for many important state families.The summary covers bipartite pure, GHZ, stabilizer, hypergraph, weighted graph, and Dicke states, with applications to blind MBQC and quantum networks.Source: §XII · pp. 26–27

Appendix A: Proof of Eq. (1)

• The appendix establishes Eq. (1) by reducing the optimization to the verification operator’s eigenbasis and identifying the second eigenvalue as the relevant spectral quantity.The extremal state is a mixture of the target state and the second eigenspace projector.Source: Appendix A · p. 27

1. Proofs of Lemmas 1 to 3

• The functions ζ̃, η̃, and F̃ satisfy convexity or concavity and monotonicity properties that underpin the adversarial verification bounds.The appendix proves strict increase above the critical significance level or for positive fidelity, with nondecreasing behavior over the full domains.Source: §1 · pp. 27–28

2. Proofs of Lemmas 4 to 7

• The appendix proves recursive inequalities and equality conditions relating verification trade-offs for N and N−1 tests.The relevant inequalities are saturated only at specified boundary cases, including f = 1 for one key relation.Source: §2 · p. 29
• The trade-off functions are piecewise linear, with turning points determined by extremal points of the admissible region R_N,Ω.Lemma 14 expresses ζ and η through ordered turning points between the critical value and one.Source: §2 · p. 30

1. Auxiliary results on homogeneous strategies

• The appendix proves monotonicity properties of the auxiliary slopes and uses them to identify adjacent extremal points that determine ζ(N, δ, λ).The optimal representation uses k* and k* + 1, with the corresponding convex coefficients.Source: §1 · p. 30
• For homogeneous strategies, ζ(N, δ, λ, k) increases with δ and generally with N, while its optimization over k is attained at the largest k satisfying η_k ≥ δ.The monotonicity has the stated boundary exception when δ = 1 and k = 0.Source: §1 · pp. 30, 32
• The minimum test-count expression Ñ(ǫ, δ, λ, k) decreases with ǫ and δ, and is minimized by the largest k satisfying δ ≤ λ^k/(F + λǫ).This yields the optimizer k* used in the homogeneous-strategy formulas.Source: §1 · pp. 31–32

2. Proofs of Theorems 1-3 and Eq. (72)

• The proof of Theorem 2 characterizes the minimum test count N(ǫ, δ, λ) through the largest admissible value of the integer parameter k.The condition F(N, δ, λ) ≥ 1 − ǫ is reduced to an optimized inequality involving the verification trade-off.Source: §2 · p. 33
• The bounds on N(ǫ, δ, λ) are established by comparing the optimized expression with neighboring integer choices and with the allowed range of N.These arguments prove both lower and upper bounds and identify conditions for equality.Source: §2 · pp. 33–34
• When log_λ δ is an integer, the lower and upper bounds coincide, so the test-count bound is saturated.The same integer condition also saturates the bound corresponding to Eq. (74).Source: §2 · p. 34

Appendix D: Proof of Theorem 4

• For homogeneous strategies, ζ(N, δ, Ω) = ζ(N, δ, β); in general, the equality follows by establishing ζ(N, δ, Ω) ≤ ζ(N, δ, β) and the opposite inequality.Source: Appendix D · p. 34
• For β < 1/2, an auxiliary operator ˜Ω with eigenvalues 1, β, and τ reduces the proof to verifying the reverse inequality against ˜Ω.The comparison is completed by treating k1 = 0, 1, and 2 and combining the resulting inequality with the opposite bound.Source: Appendix D · p. 34

1. Main body of the proofs

• The proof of Theorem 5 represents permutation-invariant states as mixtures of ρk and separates the special case pρ = 1 from 0 < pρ < 1.The resulting decomposition enables application of the auxiliary inequalities used to derive Eq. (112).Source: §1 · p. 35
• The bound in Eq. (112) is saturated for δ ≥ δ∗ by ρk0, ρk1, and their convex combinations.At the endpoints, pρ and fρ attain the required values; linearity in ρ extends saturation throughout the relevant range.Source: §1 · p. 35
• When Ω is singular and 1/(N + 1) ≤ δ ≤ δ∗, the bound in Eq. (113) is saturated using endpoint states and convexity.The endpoint choices have δ = 1/(N + 1) and δ = δ∗, after which linearity supplies the intermediate values.Source: §1 · pp. 34–35

2. Auxiliary lemmas

• The verification operator eigenvalues satisfy 1 = λ1 > λ2 ≥ ··· ≥ λD ≥ 0, with β = λ2 and τ = λD, while ν = 1 − β.These parameters define the second-largest and smallest eigenvalues used throughout the bounds.Source: §2 · p. 35
• ηk(λ) − ζk(λ) ≤ 1/(N + 1) for every k ∈ SN when β ≤ 1/2.The proof reduces the difference to eigenvalue bounds and uses β ≤ 1/2.Source: §2 · p. 35
• The region RN,Ω is contained in a triangle whose vertices are (1, 1), (τ^N, 0), and (1/(Nν + 1), 0).The first two vertices are extremal points of RN,Ω.Source: §2 · p. 36
• When ζk(λ) = 0, the relevant cases are k1 = 0 or zero eigenvalues among components with positive occupation, and the resulting bounds agree with Lemma 23.These special cases connect the spectral formulas to the geometric containment results.Source: §2 · p. 36
• For vectors u ≤ v with identical first component 1, ξk(u) ≥ ξk(v).The result follows from continuity and the fact that ξk is nonincreasing in the remaining components.Source: §2 · p. 36

2. Auxiliary lemmas

• The convex-hull construction extends ηk(λ) and ζk(λ) from SN to its convex hull when Ω is positive definite.This extension underlies the definitions used in the auxiliary bounds.Source: §1 · pp. 36–37
• For δ > β^N, ζ(N, δ, Ω) is represented by a convex combination of two points whose η-values bracket δ.The coefficients are determined by normalization and the constraint c0η0 + c1η1 = δ.Source: §1 · p. 37
• The parametrized curve (η(t), ζ(t)) lies below the line segment joining its endpoints, yielding the inequality in Eq. (F3).The proof analyzes the curve’s convexity, including the case where η′(t) has a unique zero.Source: §1 · pp. 37–38
• The analogous inequality in Eq. (F4) follows by replacing convexity with concavity for the parametrized curve.The derivative structure ensures ζ′(t) has at most one zero, allowing the same endpoint comparison argument.Source: §1 · pp. 38–39
• The linear-programming lemma reduces the relevant maximization to extremal feasible points.When c < 0, convexity of c/(x ln x) identifies the extremal form; when c = 0, all coefficients vanish.Source: §1 · p. 39

2. Main body of the proofs

• When δ ≤ β^N, the bound in Eq. (120) is zero or negative and therefore trivial.For δ > β^N, Lemma 25 supplies the nontrivial starting inequality for the same bound.Source: §2 · p. 39
• N(ε, δ, Ω) ≤ N follows from Lemma 9 together with Lemma 6, confirming the first upper bound in Eq. (125).A second upper bound follows from h > |1/ln β| and |β̃ ln β̃| ≤ |β ln β|.Source: §2 · p. 40

Appendix G: Proofs of Lemmas 10-12

• For τ = 1 − ν, νh∗(ν, 1 − ν) is greater than 1 and strictly increasing for 0 < ν ≤ 1.The derivative argument covers the interval up to 1 − e^-1, while Eq. (G1) supplies the remaining range.Source: Appendix G · p. 40
• p∗(ν, τ) is nondecreasing in ν and nonincreasing in τ, while h∗(ν, τ) is nonincreasing in both parameters.These monotonicities are established through comparisons of the defining threshold conditions.Source: Appendix G · pp. 40–41
• νh∗(ν, τ) increases strictly with ν, and limν→0 νh∗(ν, τ) = 1.The strict increase establishes the corresponding statements in Lemma 11, while the limit gives its small-ν behavior.Source: Appendix G · p. 41
• p∗(ν) is strictly increasing in ν, whereas h∗(ν) is strictly decreasing and νh∗(ν) is strictly increasing.The proof also establishes 0 < p∗(ν) ≤ 1/e.Source: Appendix G · p. 41

• The bipartite proof assumes Alice uses a single complete projective measurement in an orthonormal basis, with rank-1 projectors P_k.Source: Appendix H · p. 42
• Under this restriction, every test operator has the form E = Σ_k P_k ⊗ Q_k, where Bob’s operators satisfy 0 ≤ Q_k ≤ 1.Source: Appendix H · p. 42
• Ensuring that the target state always passes requires the test operator to satisfy ⟨Ψ|E|Ψ⟩ = 1.Source: Appendix H · p. 42
• The proof introduces Bob’s unnormalized conditional states |˜ψ_k⟩, their outcome probabilities p_k, and normalized states |ψ_k⟩ for each Alice outcome.Source: Appendix H · p. 42