Adaptive Stabilizer State Fidelity Certification

Kun Wang

arxiv: 2605.29820 · v1 · pith:CVDERYM2new · submitted 2026-05-28 · 🪐 quant-ph

Adaptive Stabilizer State Fidelity Certification

Kun Wang This is my paper

Pith reviewed 2026-06-29 07:19 UTC · model grok-4.3

classification 🪐 quant-ph

keywords stabilizer statesfidelity certificationadaptive measurementquantum state verificationlinear programminggauge selectionwitness elimination

0 comments

The pith

Adaptive gauge selection certifies the full fidelity interval of a stabilizer state.

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

The paper develops an adaptive protocol to certify the fidelity of a prepared quantum state to a target stabilizer state by choosing successive stabilizer gauges based on prior outcomes. It first derives the optimal worst-case upper bound for a single fixed gauge, then formulates gauge selection as an adaptive design problem solved by endpoint linear programs under a witness elimination policy. This approach produces a certified fidelity interval that tightens monotonically and recovers the exact fidelity once all nontrivial stabilizers have been measured. The work also shows that full coverage is necessary in the worst case but can be outperformed by adaptivity for certain structured syndrome distributions, with numerical confirmation of faster concentration.

Core claim

We develop an adaptive extension that reports the full certified fidelity interval. First, for a single gauge, we derive the complementary optimal worst-case upper bound. We then formulate gauge selection as an adaptive design problem in which each round solves exact endpoint linear programs and chooses a new gauge by a witness elimination policy. We prove monotonic tightening, exact recovery once all nontrivial stabilizers are covered, and the worst-case necessity of full coverage. Finally, we identify structured syndrome distributions for which adaptivity beats this exponential benchmark, and we numerically confirm faster concentration.

What carries the argument

Adaptive gauge selection via endpoint linear programs and witness elimination policy that chooses the next stabilizer measurement from prior outcomes.

If this is right

The certified fidelity interval narrows monotonically after each adaptive round.
Exact fidelity recovery occurs once every nontrivial stabilizer has been measured.
Full stabilizer coverage remains necessary to guarantee certification in the worst case.
For certain structured syndrome distributions adaptivity reduces the number of measurements below the exponential benchmark.
Numerical simulations show faster concentration of the certified interval under the adaptive policy.

Where Pith is reading between the lines

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

The method could reduce total measurements needed in experiments when states exhibit favorable syndrome statistics.
The linear-programming formulation of gauge choice might generalize to certifying other quantum properties such as entanglement witnesses.
Relaxing the assumption of perfect adaptive gauge implementation could reveal robustness limits under realistic device noise.

Load-bearing premise

Prior measurement outcomes can be used to select subsequent gauges without additional unmodeled noise or implementation constraints on the adaptive choice.

What would settle it

An explicit counterexample in which the adaptive protocol either fails to tighten the interval monotonically or fails to recover exact fidelity after all nontrivial stabilizers are measured.

read the original abstract

Certifying the fidelity of a prepared state to a target stabilizer state is a fundamental task in quantum information processing. Ref. [Phys. Rev. A 99, 042337 (2019)] gave the optimal worst-case lower bound from one fixed stabilizer generator gauge, but gauge dependence can leave a large fidelity ambiguity. We develop an adaptive extension that reports the full certified fidelity interval. First, for a single gauge, we derive the complementary optimal worst-case upper bound. We then formulate gauge selection as an adaptive design problem in which each round solves exact endpoint linear programs and chooses a new gauge by a witness elimination policy. We prove monotonic tightening, exact recovery once all nontrivial stabilizers are covered, and the worst-case necessity of full coverage. Finally, we identify structured syndrome distributions for which adaptivity beats this exponential benchmark, and we numerically confirm faster concentration.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper cleanly extends the 2019 fixed-gauge result with an adaptive upper bound and gauge selection via LPs, plus proofs of monotonicity and recovery, but the adaptivity assumes idealized feedback with no modeled noise or constraints.

read the letter

The core advance is turning the fixed-gauge lower bound into a full certified interval by adding the matching upper bound and then making gauge choice adaptive. Each round solves endpoint linear programs and applies a witness elimination policy to pick the next stabilizer generator. The proofs show the interval tightens monotonically, recovers the exact fidelity once all nontrivial stabilizers are covered, and that full coverage is necessary in the worst case. It also flags structured syndrome distributions where adaptivity beats the exponential benchmark and backs that with numerics on faster concentration.

The math reads as a direct, non-circular extension of the prior work. The derivations stand on their own without data fitting.

The main limitation is the adaptive step. The construction treats prior outcomes as perfect inputs for the next exact LP solve and gauge choice. It does not incorporate feedback latency, selection errors, or extra noise channels that would appear in any real implementation. Under those conditions the reported guarantees become conditional on an idealized oracle the paper does not analyze.

This is for researchers focused on stabilizer certification who need tighter practical bounds. The formal results are solid enough that a serious editor should send it to referees rather than desk-reject, even if revisions will be needed on the implementation assumptions.

Referee Report

1 major / 2 minor

Summary. The paper develops an adaptive protocol for certifying fidelity of a prepared quantum state to a target stabilizer state. Starting from the known optimal worst-case lower bound for a fixed stabilizer generator gauge, it derives the complementary optimal upper bound. It then formulates gauge selection as an adaptive design problem solved via exact endpoint linear programs at each round, using a witness elimination policy. The manuscript proves that this yields monotonic tightening of the certified fidelity interval, exact recovery of the true fidelity once all nontrivial stabilizers are measured, and the necessity of full coverage in the worst case. It further identifies structured syndrome distributions where adaptivity outperforms the exponential non-adaptive benchmark and provides numerical confirmation of faster concentration.

Significance. If the mathematical results hold, the work supplies a principled adaptive strategy that can reduce the measurement overhead for stabilizer fidelity certification while providing explicit interval guarantees. The proofs of monotonic tightening and exact recovery constitute a clear theoretical contribution, and the identification of structured cases where adaptivity helps is a useful practical insight. These elements strengthen the case for adaptive verification methods in quantum information processing.

major comments (1)

[adaptive design problem formulation] The adaptive design problem (formulated via endpoint linear programs and witness elimination) assumes that prior measurement outcomes can be fed back to select the next gauge while preserving the stated monotonicity and exact-recovery properties. The manuscript does not incorporate or analyze any model of feedback latency, selection errors, or additional noise channels that would arise in a physical implementation of the adaptive choice. This idealized-oracle assumption is load-bearing for the claimed interval guarantees outside the purely mathematical setting.

minor comments (2)

Notation for the endpoint linear programs and the witness elimination policy should be introduced with explicit definitions before the proofs of monotonic tightening are stated.
The numerical examples confirming faster concentration would benefit from explicit reporting of the number of trials and the precise syndrome distributions used.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and constructive comment. We address the point below.

read point-by-point responses

Referee: The adaptive design problem (formulated via endpoint linear programs and witness elimination) assumes that prior measurement outcomes can be fed back to select the next gauge while preserving the stated monotonicity and exact-recovery properties. The manuscript does not incorporate or analyze any model of feedback latency, selection errors, or additional noise channels that would arise in a physical implementation of the adaptive choice. This idealized-oracle assumption is load-bearing for the claimed interval guarantees outside the purely mathematical setting.

Authors: We agree that the analysis assumes an idealized feedback model with perfect, instantaneous, and error-free selection of the next gauge. The manuscript is a theoretical work whose proofs of monotonic tightening, exact recovery upon full coverage, and worst-case necessity of full coverage are derived under these ideal conditions; the interval guarantees are stated for that mathematical setting. The referee is correct that no model of latency, selection errors, or extra noise channels is analyzed. We will revise the manuscript to add an explicit paragraph in the introduction and a dedicated limitations paragraph in the conclusions that states the idealized assumptions and notes that practical implementations must separately account for control-system latency and measurement noise while preserving the core mathematical properties under the ideal model. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivations are independent mathematical extensions

full rationale

The paper cites a prior result solely for the known lower bound on fidelity certification and then derives a complementary upper bound, formulates gauge selection via endpoint linear programs, and proves new properties (monotonic tightening, exact recovery upon full stabilizer coverage) through direct mathematical arguments. None of these steps reduce by construction to fitted inputs, self-definitions, or load-bearing self-citations; the adaptive design and witness elimination policy are defined and analyzed independently of any data-fitting loop or prior-work ansatz. The derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are identifiable from the abstract; the work relies on standard linear programming and stabilizer formalism from prior literature.

pith-pipeline@v0.9.1-grok · 5657 in / 1018 out tokens · 28782 ms · 2026-06-29T07:19:39.871104+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

57 extracted references · 3 canonical work pages · 2 internal anchors

[1]

( 8) On the other hand, taking the expectation of a stabilizer element g(u) in ρ gives, for every u ∈ Fn 2, µρ(u) := Tr[ρg(u)] = ∑ s∈Fn 2 (−1)u·spρ(s) = bpρ(u)

( 7) The stabilizer fidelity of ρ with respect to the stabilizer state |ψ⟩ is simply the probability of the trivial syn- drome s = 0, F(ρ, ψ) := Tr[ρ|ψ⟩ ⟨ψ|] = Tr[ρΠ0] = pρ(0). ( 8) On the other hand, taking the expectation of a stabilizer element g(u) in ρ gives, for every u ∈ Fn 2, µρ(u) := Tr[ρg(u)] = ∑ s∈Fn 2 (−1)u·spρ(s) = bpρ(u). ( 9) Thus each stab...
[2]

Equivalently, one may solve a fixed sequence of secondary linear op- timizations over the optimal face

If either endpoint LP has multiple optimal solu- tions, choose the lexicographically smallest probability vector on the corresponding optimal face. Equivalently, one may solve a fixed sequence of secondary linear op- timizations over the optimal face. This convention de- termines p− t , p+ t , and hence dt, without changing the certified endpoints Lt and ...
[3]

A feasible set is any linearly independent subset of Fn 2 \ {0}, and a vector matroid basis is any set B = {b1, · · · , bn} ⊂ Fn 2 \ {0} with rank (B) = n

The ground set is Fn 2 \ {0}, with weight dt(u) as- signed to element u ∈ Fn 2 \ {0}. A feasible set is any linearly independent subset of Fn 2 \ {0}, and a vector matroid basis is any set B = {b1, · · · , bn} ⊂ Fn 2 \ {0} with rank (B) = n. Thus the column set of the next gauge is obtained by solving Bt+1 ∈ arg max B⊆Fn 2 \{0} |B|=n, rank (B)=n B̸⊆Qt ∑ u...
[4]

The lower and upper endpoint problems are two linear programs over this syndrome vector

Endpoint LP cost. The lower and upper endpoint problems are two linear programs over this syndrome vector. A generic LP solver therefore has classical cost Ct,LP = poly(2n, qt, log(1/τnum)) = 2O(n), ( 39) where τnum denotes the requested numerical accuracy. We do not assume a specialized linear time LP algo- rithm; the polynomial degree can depend on the ...
[5]

After the endpoint wit- nesses p− t and p+ t are obtained, the disagreement spec- trum is the Walsh transform of the length 2 n vector p+ t − p− t

Disagreement spectrum cost. After the endpoint wit- nesses p− t and p+ t are obtained, the disagreement spec- trum is the Walsh transform of the length 2 n vector p+ t − p− t . A fast Walsh–Hadamard transform gives Ct,dis = O(n2n). ( 40)
[6]

The next gauge is obtained by the greedy vector matroid algorithm in Eq

Gauge selection cost. The next gauge is obtained by the greedy vector matroid algorithm in Eq. (37). It scans the 2 n − 1 nonzero stabilizer labels and performs rank updates over F2, giving Ct,gauge = O(2n poly(n)) , ( 41) where the precise polynomial factor depends on the im- plementation of the rank updates. Combining the components gives the per round ...
[7]

not reached

In the coordinates of the chosen gauge, take 1 2 (δ0 + δ1), 1 2 (δe1 + δe1+1), ( 62) and pull them back through A. Every coordinate gen- erator has expectation zero for both distributions, while only the first distribution contains the zero syndrome. Thus a fixed gauge can leave a constant ambiguity on affine lines, whereas the adaptive search can learn t...
[8]

We use 51 random instances and Tmax = 32

with all concentration parameters equal to one, i.e., every syn- drome has nonzero probability almost surely. We use 51 random instances and Tmax = 32. The right panel of Fig. 3 shows that the witness elimination policy still concentrates faster. The median final width is approxi- mately 0.0085 for witness elimination and 0.028 for the uniform random gaug...
[9]

Stabilizer Codes and Quantum Error Correction

D. Gottesman, Stabilizer Codes and Quantum Error Cor- rection, Ph.D. thesis, California Institute of Technology (1997), arXiv:quant-ph/9705052

work page internal anchor Pith review Pith/arXiv arXiv 1997
[10]

B. M. Terhal, Rev. Mod. Phys. 87, 307–346 (2015)

2015
[11]

Raussendorf and H

R. Raussendorf and H. J. Briegel, Nature 409, 46–52 (2001)

2001
[12]

Walther, K

P . Walther, K. J. Resch, T. Rudolph, E. Schenck, H. We- infurter, V . Vedral, M. Aspelmeyer, and A. Zeilinger, Na- ture 434, 169–176 (2005)

2005
[13]

Barends et al., Nature 508, 500–503 (2014)

R. Barends et al., Nature 508, 500–503 (2014)

2014
[14]

Kelly et al., Nature 519, 66–69 (2015)

J. Kelly et al., Nature 519, 66–69 (2015)

2015
[15]

Cao et al., Nature 619, 738–742 (2023)

S. Cao et al., Nature 619, 738–742 (2023)

2023
[16]

Jiang et al., Nature Phys

T. Jiang et al., Nature Phys. 22, 430–438 (2026)

2026
[17]

K. J. Satzinger et al., Science 374, 1237–1241 (2021)

2021
[18]

Google Quantum AI, Nature 614, 676–681 (2023)

2023
[19]

Egan et al., Nature 598, 281–286 (2021)

L. Egan et al., Nature 598, 281–286 (2021)

2021
[20]

Bluvstein et al., Nature 626, 58–65 (2024)

D. Bluvstein et al., Nature 626, 58–65 (2024)

2024
[21]

Bluvstein et al., Nature 649, 39–46 (2025)

D. Bluvstein et al., Nature 649, 39–46 (2025)

2025
[22]

D. F. V . James, P . G. Kwiat, W. J. Munro, and A. G. White, Phys. Rev. A 64, 052312 (2001)

2001
[23]

J. B. Altepeter, E. R. Jeffrey, and P . G. Kwiat, inAdvances in Atomic, Molecular, and Optical Physics , Vol. 52 (Academic Press, 2005) p. 105–159

2005
[24]

Gross, Y.-K

D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert, Phys. Rev. Lett. 105, 150401 (2010)

2010
[25]

Cramer et al., Nature Commun

M. Cramer et al., Nature Commun. 1, 149 (2010)

2010
[26]

Hayashi and T

M. Hayashi and T. Morimae, Phys. Rev. Lett. 115, 220502 (2015)

2015
[27]

Dangniam, Y.-G

N. Dangniam, Y.-G. Han, and H. Zhu, Phys. Rev. Re- search 2, 043323 (2020)

2020
[28]

Li, Y.-G

Z. Li, Y.-G. Han, and H. Zhu, Phys. Rev. Applied 13, 054002 (2020)

2020
[29]

S. Chen, W. Xie, P . Xu, and K. Wang, Phys. Rev. Research 7, 013003 (2025)

2025
[30]

Zheng, X

C. Zheng, X. Yu, Z. Zhang, P . Xu, and K. Wang, Quantum Sci. Technol. X, XXXXXX (2026), accepted Manuscript on- line; arXiv:2409.19699

work page arXiv 2026
[31]

S. T. Flammia and Y.-K. Liu, Phys. Rev. Lett. 106, 230501 (2011). 16

2011
[32]

M. P . da Silva, O. Landon-Cardinal, and D. Poulin, Phys. Rev. Lett. 107, 210404 (2011)

2011
[33]

Kalev, A

A. Kalev, A. Kyrillidis, and N. M. Linke, Phys. Rev. A 99, 042337 (2019)

2019
[34]

J. E. Kelley, J. Soc. Indust. Appl. Math. 8, 703–712 (1960)

1960
[35]

Bertsimas and J

D. Bertsimas and J. N. Tsitsiklis, Introduction to Linear Op- timization (Athena Scientific, Belmont, MA, 1997)

1997
[36]

Desaulniers, J

G. Desaulniers, J. Desrosiers, and M. M. Solomon, eds., Column Generation (Springer, New York, 2005)

2005
[37]

M. E. Lübbecke and J. Desrosiers, Oper. Res. 53, 1007–1023 (2005)

2005
[38]

Rocchetto, Quantum Inf

A. Rocchetto, Quantum Inf. Comput. 18, 541–552 (2018)

2018
[39]

Learning stabilizer states by Bell sampling

A. Montanaro, Learning stabilizer states by bell sampling (2017), arXiv:1707.04012

work page internal anchor Pith review Pith/arXiv arXiv 2017
[40]

Aaronson and D

S. Aaronson and D. Gottesman, Phys. Rev. A 70, 052328 (2004)

2004
[41]

Adaptive Stabilizer State Fidelity Certification

H. Lange, M. Kebriˇ c, M. Buser, U. Schollwöck, F. Grusdt, and A. Bohrdt, Quantum 7, 1129 (2023). 17 Supplemental Material for “Adaptive Stabilizer State Fidelity Certification” This Supplemental Material is organized to follow the structure of the main text (MT). Appx. A gives the details for Sec. III; Appx. B proves the one gauge upper endpoint results ...

2023
[42]

Proofs for Sec

Further details for the illustrative examples 18 B. Proofs for Sec. IV 18
[43]

Fine grained adaptive stabilizer fidelity certification algorithm 20 D

Calculation of the GHZ upper certificates 20 C. Fine grained adaptive stabilizer fidelity certification algorithm 20 D. Proofs for Sec. VI 22
[44]

10 24 Appendix A: Additional material for Sec

Proof of Prop. 10 24 Appendix A: Additional material for Sec. III
[45]

1 Let A ∈ GL(n, 2) be arbitrary

Proof of Prop. 1 Let A ∈ GL(n, 2) be arbitrary. In the A-coordinates, define two distributions on Fn 2 by ep = 1 2 δ0 + δe1+e2 , eq = 1 2 δe1 + δe2 , (A 1) where e1, e2 are the first two standard basis vectors. For every coordinate vector ei, bep(ei) =beq(ei) = ( 0, i = 1, 2, 1, i = 3, · · · , n, (A2) because the two support points in each distribution ha...
[46]

Further details for the illustrative examples For the gauge choice claim in Sec. III B, the KKL lower bound from one gauge for generator expectations µ1, · · · , µn is LKKL = max ( 0, 1 − 1 2 n ∑ i=1 (1 − µi) ) , (A 7) which is the explicit worst-case fidelity formula derived in Ref. [ 25]. Substituting (µ1, µ2, µ3) = ( 1/2, 1/2, 1/2) gives LKKL = 1/4, wh...
[47]

2 Work in the coordinates of the chosen gauge A, so that the measured generator labels are the standard basis vectors e1, · · · , en

Proof of Prop. 2 Work in the coordinates of the chosen gauge A, so that the measured generator labels are the standard basis vectors e1, · · · , en. Write ai := 1 + µρ(ai) 2 . (B 1) For any feasible syndrome distribution p, the constraint on ai is equivalent to ∑ s:si=0 p(s) = ai. (B 2) 19 The event {s = 0} is contained in every event {si = 0}, so every f...
[48]

3 For each i, Hoeffding’s inequality for the binary variables Yi,j ∈ {0, 1} gives Pr {|bai − ai| > ε} ≤ 2 exp(−2miε2)

Proof of Prop. 3 For each i, Hoeffding’s inequality for the binary variables Yi,j ∈ {0, 1} gives Pr {|bai − ai| > ε} ≤ 2 exp(−2miε2). (B 13) Under Eq. (24), the right-hand side is at most δ/n. A union bound over i ∈ [n] gives max i∈[n] |bai − ai| ≤ ε (B14) with probability at least 1 − δ. On this event, min i∈[n] bai − min i∈[n] ai ≤ max i∈[n] |bai − ai| ...
[49]

4 The true syndrome distribution of ρ is feasible for the exact optimization problem in Eq

Proof of Cor. 4 The true syndrome distribution of ρ is feasible for the exact optimization problem in Eq. ( 19). Hence F(ρ, ψ) ≤ Fmax(A; ρ). (B 16) Combining this inequality with Prop. 3 gives Eq. ( 26) with probability at least 1 − δ. Summing the per generator shot count in Eq. ( 24) over all n generators gives Eq. (27)
[50]

Calculation of the GHZ upper certificates Here we spell out the upper certificate entries in Tab. I. For a desired confidence level pconf, set δ = 1 − pconf. Cor. 4 gives F(ρ, ψ) ≤ bUA + ε, ε = r log(2n/δ) 2m , (B 17) when each of the n generators has effective sample count m. Since every fidelity is at most 1, the reported upper certificate is Ucert = mi...
[51]

5 Since the constraints are cumulative, Qt ⊆ Qt+1

Proof of Prop. 5 Since the constraints are cumulative, Qt ⊆ Qt+1. Hence every distribution satisfying all constraints at round t + 1 also satisfies all constraints at round t, so Ft+1 ⊆ F t. (D 1) Therefore Lt+1 = min p∈Ft+1 p(0) ≥ min p∈Ft p(0) = Lt, (D 2) and similarly Ut+1 = max p∈Ft+1 p(0) ≤ max p∈Ft p(0) = Ut. (D 3) It follows immediately that Wt+1 =...
[52]

6 For any probability distribution p ∈ ∆(Fn 2 ), the zeroth Walsh coefficient is bp(0) = ∑ s p(s) = 1

Proof of Prop. 6 For any probability distribution p ∈ ∆(Fn 2 ), the zeroth Walsh coefficient is bp(0) = ∑ s p(s) = 1. (D 4) If Qt⋆ = Fn 2 \ {0} and p ∈ F t⋆, then every Walsh coefficient of p agrees with the corresponding Walsh coefficient of pρ: the nonzero coefficients agree by definition of Ft⋆, while the zeroth coefficient agrees by normalization. Wal...
[53]

7 Assume an adaptive generator-only protocol has queried a set Q ⊆ Fn 2 \ {0} of nontrivial stabilizer labels, and suppose that some nonzero direction v /∈ Q remains unqueried

Proof of Prop. 7 Assume an adaptive generator-only protocol has queried a set Q ⊆ Fn 2 \ {0} of nontrivial stabilizer labels, and suppose that some nonzero direction v /∈ Q remains unqueried. For any η ∈ (0, 1], define p±(s) := 2−n 1 ± η(−1)v·s , s ∈ Fn
[54]

By Walsh orthogonality, bp±(u) = ∑ s∈Fn 2 (−1)u·s2−n 1 ± η(−1)v·s = 1 [u = 0] ± η 1 [u = v]

(D 7) These are valid probability distributions because 1 ± η(−1)v·s ∈ [0, 2] and the Walsh character (−1)v·s has zero average over s. By Walsh orthogonality, bp±(u) = ∑ s∈Fn 2 (−1)u·s2−n 1 ± η(−1)v·s = 1 [u = 0] ± η 1 [u = v]. (D 8) Thereforebp+(u) = bp−(u) for every u ∈ Q, because v /∈ Q and all queried labels are nonzero. The protocol receives the same...
[55]

8 Let p, q ∈ F t

Proof of Prop. 8 Let p, q ∈ F t. Walsh–Hadamard inversion at the zero syndrome gives p(0) − q(0) = 2−n ∑ u∈Fn 2 bp(u) −bq(u) . (D 11) The term u = 0 vanishes because both p and q are probability distributions, and every term with u ∈ Qt vanishes because p and q satisfy the same queried Walsh constraints. Hence p(0) − q(0) = 2−n ∑ u∈(Fn 2 \{0})\Qt bp(u) −b...
[56]

9 Applying Walsh–Hadamard inversion to the endpoint witnesses gives Wt = p+ t (0) − p− t (0) = 2−n ∑ u∈Fn 2 bp+ t (u) −bp− t (u)

Proof of Prop. 9 Applying Walsh–Hadamard inversion to the endpoint witnesses gives Wt = p+ t (0) − p− t (0) = 2−n ∑ u∈Fn 2 bp+ t (u) −bp− t (u) . (D 16) The zeroth term vanishes because both endpoint witnesses are probability distributions, and every queried term vanishes because both witnesses lie in Ft. Hence Wt = 2−n ∑ u∈(Fn 2 \{0})\Qt bp+ t (u) −bp− t...
[57]

10 Let p = ps0,V where V ≤ Fn 2 has dimension r and codimension d = n − r

Proof of Prop. 10 Let p = ps0,V where V ≤ Fn 2 has dimension r and codimension d = n − r. For any u ∈ Fn 2, bp(u) = ∑ s∈Fn 2 (−1)u·sp(s) = 2−r ∑ v∈V (−1)u·(s0+v) = ( −1)u·s0 2−r ∑ v∈V (−1)u·v. (D 18) If u ∈ V⊥, every term in the last sum equals 1, so bp(u) = ( −1)u·s0. If u /∈ V⊥, then the character v 7→ (−1)u·v is nontrivial on V and sums to 0. Therefore...

[1] [1]

( 8) On the other hand, taking the expectation of a stabilizer element g(u) in ρ gives, for every u ∈ Fn 2, µρ(u) := Tr[ρg(u)] = ∑ s∈Fn 2 (−1)u·spρ(s) = bpρ(u)

( 7) The stabilizer fidelity of ρ with respect to the stabilizer state |ψ⟩ is simply the probability of the trivial syn- drome s = 0, F(ρ, ψ) := Tr[ρ|ψ⟩ ⟨ψ|] = Tr[ρΠ0] = pρ(0). ( 8) On the other hand, taking the expectation of a stabilizer element g(u) in ρ gives, for every u ∈ Fn 2, µρ(u) := Tr[ρg(u)] = ∑ s∈Fn 2 (−1)u·spρ(s) = bpρ(u). ( 9) Thus each stab...

[2] [2]

Equivalently, one may solve a fixed sequence of secondary linear op- timizations over the optimal face

If either endpoint LP has multiple optimal solu- tions, choose the lexicographically smallest probability vector on the corresponding optimal face. Equivalently, one may solve a fixed sequence of secondary linear op- timizations over the optimal face. This convention de- termines p− t , p+ t , and hence dt, without changing the certified endpoints Lt and ...

[3] [3]

A feasible set is any linearly independent subset of Fn 2 \ {0}, and a vector matroid basis is any set B = {b1, · · · , bn} ⊂ Fn 2 \ {0} with rank (B) = n

The ground set is Fn 2 \ {0}, with weight dt(u) as- signed to element u ∈ Fn 2 \ {0}. A feasible set is any linearly independent subset of Fn 2 \ {0}, and a vector matroid basis is any set B = {b1, · · · , bn} ⊂ Fn 2 \ {0} with rank (B) = n. Thus the column set of the next gauge is obtained by solving Bt+1 ∈ arg max B⊆Fn 2 \{0} |B|=n, rank (B)=n B̸⊆Qt ∑ u...

[4] [4]

The lower and upper endpoint problems are two linear programs over this syndrome vector

Endpoint LP cost. The lower and upper endpoint problems are two linear programs over this syndrome vector. A generic LP solver therefore has classical cost Ct,LP = poly(2n, qt, log(1/τnum)) = 2O(n), ( 39) where τnum denotes the requested numerical accuracy. We do not assume a specialized linear time LP algo- rithm; the polynomial degree can depend on the ...

[5] [5]

After the endpoint wit- nesses p− t and p+ t are obtained, the disagreement spec- trum is the Walsh transform of the length 2 n vector p+ t − p− t

Disagreement spectrum cost. After the endpoint wit- nesses p− t and p+ t are obtained, the disagreement spec- trum is the Walsh transform of the length 2 n vector p+ t − p− t . A fast Walsh–Hadamard transform gives Ct,dis = O(n2n). ( 40)

[6] [6]

The next gauge is obtained by the greedy vector matroid algorithm in Eq

Gauge selection cost. The next gauge is obtained by the greedy vector matroid algorithm in Eq. (37). It scans the 2 n − 1 nonzero stabilizer labels and performs rank updates over F2, giving Ct,gauge = O(2n poly(n)) , ( 41) where the precise polynomial factor depends on the im- plementation of the rank updates. Combining the components gives the per round ...

[7] [7]

not reached

In the coordinates of the chosen gauge, take 1 2 (δ0 + δ1), 1 2 (δe1 + δe1+1), ( 62) and pull them back through A. Every coordinate gen- erator has expectation zero for both distributions, while only the first distribution contains the zero syndrome. Thus a fixed gauge can leave a constant ambiguity on affine lines, whereas the adaptive search can learn t...

[8] [8]

We use 51 random instances and Tmax = 32

with all concentration parameters equal to one, i.e., every syn- drome has nonzero probability almost surely. We use 51 random instances and Tmax = 32. The right panel of Fig. 3 shows that the witness elimination policy still concentrates faster. The median final width is approxi- mately 0.0085 for witness elimination and 0.028 for the uniform random gaug...

[9] [9]

Stabilizer Codes and Quantum Error Correction

D. Gottesman, Stabilizer Codes and Quantum Error Cor- rection, Ph.D. thesis, California Institute of Technology (1997), arXiv:quant-ph/9705052

work page internal anchor Pith review Pith/arXiv arXiv 1997

[10] [10]

B. M. Terhal, Rev. Mod. Phys. 87, 307–346 (2015)

2015

[11] [11]

Raussendorf and H

R. Raussendorf and H. J. Briegel, Nature 409, 46–52 (2001)

2001

[12] [12]

Walther, K

P . Walther, K. J. Resch, T. Rudolph, E. Schenck, H. We- infurter, V . Vedral, M. Aspelmeyer, and A. Zeilinger, Na- ture 434, 169–176 (2005)

2005

[13] [13]

Barends et al., Nature 508, 500–503 (2014)

R. Barends et al., Nature 508, 500–503 (2014)

2014

[14] [14]

Kelly et al., Nature 519, 66–69 (2015)

J. Kelly et al., Nature 519, 66–69 (2015)

2015

[15] [15]

Cao et al., Nature 619, 738–742 (2023)

S. Cao et al., Nature 619, 738–742 (2023)

2023

[16] [16]

Jiang et al., Nature Phys

T. Jiang et al., Nature Phys. 22, 430–438 (2026)

2026

[17] [17]

K. J. Satzinger et al., Science 374, 1237–1241 (2021)

2021

[18] [18]

Google Quantum AI, Nature 614, 676–681 (2023)

2023

[19] [19]

Egan et al., Nature 598, 281–286 (2021)

L. Egan et al., Nature 598, 281–286 (2021)

2021

[20] [20]

Bluvstein et al., Nature 626, 58–65 (2024)

D. Bluvstein et al., Nature 626, 58–65 (2024)

2024

[21] [21]

Bluvstein et al., Nature 649, 39–46 (2025)

D. Bluvstein et al., Nature 649, 39–46 (2025)

2025

[22] [22]

D. F. V . James, P . G. Kwiat, W. J. Munro, and A. G. White, Phys. Rev. A 64, 052312 (2001)

2001

[23] [23]

J. B. Altepeter, E. R. Jeffrey, and P . G. Kwiat, inAdvances in Atomic, Molecular, and Optical Physics , Vol. 52 (Academic Press, 2005) p. 105–159

2005

[24] [24]

Gross, Y.-K

D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert, Phys. Rev. Lett. 105, 150401 (2010)

2010

[25] [25]

Cramer et al., Nature Commun

M. Cramer et al., Nature Commun. 1, 149 (2010)

2010

[26] [26]

Hayashi and T

M. Hayashi and T. Morimae, Phys. Rev. Lett. 115, 220502 (2015)

2015

[27] [27]

Dangniam, Y.-G

N. Dangniam, Y.-G. Han, and H. Zhu, Phys. Rev. Re- search 2, 043323 (2020)

2020

[28] [28]

Li, Y.-G

Z. Li, Y.-G. Han, and H. Zhu, Phys. Rev. Applied 13, 054002 (2020)

2020

[29] [29]

S. Chen, W. Xie, P . Xu, and K. Wang, Phys. Rev. Research 7, 013003 (2025)

2025

[30] [30]

Zheng, X

C. Zheng, X. Yu, Z. Zhang, P . Xu, and K. Wang, Quantum Sci. Technol. X, XXXXXX (2026), accepted Manuscript on- line; arXiv:2409.19699

work page arXiv 2026

[31] [31]

S. T. Flammia and Y.-K. Liu, Phys. Rev. Lett. 106, 230501 (2011). 16

2011

[32] [32]

M. P . da Silva, O. Landon-Cardinal, and D. Poulin, Phys. Rev. Lett. 107, 210404 (2011)

2011

[33] [33]

Kalev, A

A. Kalev, A. Kyrillidis, and N. M. Linke, Phys. Rev. A 99, 042337 (2019)

2019

[34] [34]

J. E. Kelley, J. Soc. Indust. Appl. Math. 8, 703–712 (1960)

1960

[35] [35]

Bertsimas and J

D. Bertsimas and J. N. Tsitsiklis, Introduction to Linear Op- timization (Athena Scientific, Belmont, MA, 1997)

1997

[36] [36]

Desaulniers, J

G. Desaulniers, J. Desrosiers, and M. M. Solomon, eds., Column Generation (Springer, New York, 2005)

2005

[37] [37]

M. E. Lübbecke and J. Desrosiers, Oper. Res. 53, 1007–1023 (2005)

2005

[38] [38]

Rocchetto, Quantum Inf

A. Rocchetto, Quantum Inf. Comput. 18, 541–552 (2018)

2018

[39] [39]

Learning stabilizer states by Bell sampling

A. Montanaro, Learning stabilizer states by bell sampling (2017), arXiv:1707.04012

work page internal anchor Pith review Pith/arXiv arXiv 2017

[40] [40]

Aaronson and D

S. Aaronson and D. Gottesman, Phys. Rev. A 70, 052328 (2004)

2004

[41] [41]

Adaptive Stabilizer State Fidelity Certification

H. Lange, M. Kebriˇ c, M. Buser, U. Schollwöck, F. Grusdt, and A. Bohrdt, Quantum 7, 1129 (2023). 17 Supplemental Material for “Adaptive Stabilizer State Fidelity Certification” This Supplemental Material is organized to follow the structure of the main text (MT). Appx. A gives the details for Sec. III; Appx. B proves the one gauge upper endpoint results ...

2023

[42] [42]

Proofs for Sec

Further details for the illustrative examples 18 B. Proofs for Sec. IV 18

[43] [43]

Fine grained adaptive stabilizer fidelity certification algorithm 20 D

Calculation of the GHZ upper certificates 20 C. Fine grained adaptive stabilizer fidelity certification algorithm 20 D. Proofs for Sec. VI 22

[44] [44]

10 24 Appendix A: Additional material for Sec

Proof of Prop. 10 24 Appendix A: Additional material for Sec. III

[45] [45]

1 Let A ∈ GL(n, 2) be arbitrary

Proof of Prop. 1 Let A ∈ GL(n, 2) be arbitrary. In the A-coordinates, define two distributions on Fn 2 by ep = 1 2 δ0 + δe1+e2 , eq = 1 2 δe1 + δe2 , (A 1) where e1, e2 are the first two standard basis vectors. For every coordinate vector ei, bep(ei) =beq(ei) = ( 0, i = 1, 2, 1, i = 3, · · · , n, (A2) because the two support points in each distribution ha...

[46] [46]

Further details for the illustrative examples For the gauge choice claim in Sec. III B, the KKL lower bound from one gauge for generator expectations µ1, · · · , µn is LKKL = max ( 0, 1 − 1 2 n ∑ i=1 (1 − µi) ) , (A 7) which is the explicit worst-case fidelity formula derived in Ref. [ 25]. Substituting (µ1, µ2, µ3) = ( 1/2, 1/2, 1/2) gives LKKL = 1/4, wh...

[47] [47]

2 Work in the coordinates of the chosen gauge A, so that the measured generator labels are the standard basis vectors e1, · · · , en

Proof of Prop. 2 Work in the coordinates of the chosen gauge A, so that the measured generator labels are the standard basis vectors e1, · · · , en. Write ai := 1 + µρ(ai) 2 . (B 1) For any feasible syndrome distribution p, the constraint on ai is equivalent to ∑ s:si=0 p(s) = ai. (B 2) 19 The event {s = 0} is contained in every event {si = 0}, so every f...

[48] [48]

3 For each i, Hoeffding’s inequality for the binary variables Yi,j ∈ {0, 1} gives Pr {|bai − ai| > ε} ≤ 2 exp(−2miε2)

Proof of Prop. 3 For each i, Hoeffding’s inequality for the binary variables Yi,j ∈ {0, 1} gives Pr {|bai − ai| > ε} ≤ 2 exp(−2miε2). (B 13) Under Eq. (24), the right-hand side is at most δ/n. A union bound over i ∈ [n] gives max i∈[n] |bai − ai| ≤ ε (B14) with probability at least 1 − δ. On this event, min i∈[n] bai − min i∈[n] ai ≤ max i∈[n] |bai − ai| ...

[49] [49]

4 The true syndrome distribution of ρ is feasible for the exact optimization problem in Eq

Proof of Cor. 4 The true syndrome distribution of ρ is feasible for the exact optimization problem in Eq. ( 19). Hence F(ρ, ψ) ≤ Fmax(A; ρ). (B 16) Combining this inequality with Prop. 3 gives Eq. ( 26) with probability at least 1 − δ. Summing the per generator shot count in Eq. ( 24) over all n generators gives Eq. (27)

[50] [50]

Calculation of the GHZ upper certificates Here we spell out the upper certificate entries in Tab. I. For a desired confidence level pconf, set δ = 1 − pconf. Cor. 4 gives F(ρ, ψ) ≤ bUA + ε, ε = r log(2n/δ) 2m , (B 17) when each of the n generators has effective sample count m. Since every fidelity is at most 1, the reported upper certificate is Ucert = mi...

[51] [51]

5 Since the constraints are cumulative, Qt ⊆ Qt+1

Proof of Prop. 5 Since the constraints are cumulative, Qt ⊆ Qt+1. Hence every distribution satisfying all constraints at round t + 1 also satisfies all constraints at round t, so Ft+1 ⊆ F t. (D 1) Therefore Lt+1 = min p∈Ft+1 p(0) ≥ min p∈Ft p(0) = Lt, (D 2) and similarly Ut+1 = max p∈Ft+1 p(0) ≤ max p∈Ft p(0) = Ut. (D 3) It follows immediately that Wt+1 =...

[52] [52]

6 For any probability distribution p ∈ ∆(Fn 2 ), the zeroth Walsh coefficient is bp(0) = ∑ s p(s) = 1

Proof of Prop. 6 For any probability distribution p ∈ ∆(Fn 2 ), the zeroth Walsh coefficient is bp(0) = ∑ s p(s) = 1. (D 4) If Qt⋆ = Fn 2 \ {0} and p ∈ F t⋆, then every Walsh coefficient of p agrees with the corresponding Walsh coefficient of pρ: the nonzero coefficients agree by definition of Ft⋆, while the zeroth coefficient agrees by normalization. Wal...

[53] [53]

7 Assume an adaptive generator-only protocol has queried a set Q ⊆ Fn 2 \ {0} of nontrivial stabilizer labels, and suppose that some nonzero direction v /∈ Q remains unqueried

Proof of Prop. 7 Assume an adaptive generator-only protocol has queried a set Q ⊆ Fn 2 \ {0} of nontrivial stabilizer labels, and suppose that some nonzero direction v /∈ Q remains unqueried. For any η ∈ (0, 1], define p±(s) := 2−n 1 ± η(−1)v·s , s ∈ Fn

[54] [54]

By Walsh orthogonality, bp±(u) = ∑ s∈Fn 2 (−1)u·s2−n 1 ± η(−1)v·s = 1 [u = 0] ± η 1 [u = v]

(D 7) These are valid probability distributions because 1 ± η(−1)v·s ∈ [0, 2] and the Walsh character (−1)v·s has zero average over s. By Walsh orthogonality, bp±(u) = ∑ s∈Fn 2 (−1)u·s2−n 1 ± η(−1)v·s = 1 [u = 0] ± η 1 [u = v]. (D 8) Thereforebp+(u) = bp−(u) for every u ∈ Q, because v /∈ Q and all queried labels are nonzero. The protocol receives the same...

[55] [55]

8 Let p, q ∈ F t

Proof of Prop. 8 Let p, q ∈ F t. Walsh–Hadamard inversion at the zero syndrome gives p(0) − q(0) = 2−n ∑ u∈Fn 2 bp(u) −bq(u) . (D 11) The term u = 0 vanishes because both p and q are probability distributions, and every term with u ∈ Qt vanishes because p and q satisfy the same queried Walsh constraints. Hence p(0) − q(0) = 2−n ∑ u∈(Fn 2 \{0})\Qt bp(u) −b...

[56] [56]

9 Applying Walsh–Hadamard inversion to the endpoint witnesses gives Wt = p+ t (0) − p− t (0) = 2−n ∑ u∈Fn 2 bp+ t (u) −bp− t (u)

Proof of Prop. 9 Applying Walsh–Hadamard inversion to the endpoint witnesses gives Wt = p+ t (0) − p− t (0) = 2−n ∑ u∈Fn 2 bp+ t (u) −bp− t (u) . (D 16) The zeroth term vanishes because both endpoint witnesses are probability distributions, and every queried term vanishes because both witnesses lie in Ft. Hence Wt = 2−n ∑ u∈(Fn 2 \{0})\Qt bp+ t (u) −bp− t...

[57] [57]

10 Let p = ps0,V where V ≤ Fn 2 has dimension r and codimension d = n − r

Proof of Prop. 10 Let p = ps0,V where V ≤ Fn 2 has dimension r and codimension d = n − r. For any u ∈ Fn 2, bp(u) = ∑ s∈Fn 2 (−1)u·sp(s) = 2−r ∑ v∈V (−1)u·(s0+v) = ( −1)u·s0 2−r ∑ v∈V (−1)u·v. (D 18) If u ∈ V⊥, every term in the last sum equals 1, so bp(u) = ( −1)u·s0. If u /∈ V⊥, then the character v 7→ (−1)u·v is nontrivial on V and sums to 0. Therefore...