Verifying a stabilizer state with few observables but many shots

Dirk Oliver Theis

REVIEW 2 major objections 4 minor 19 references

Verifying a stabilizer state with few observables but many shots

T0 review · 2 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read Randomly sampling a stabilizer basis and taking the minimum of per-observable estimates certifies stabilizer states with n settings and provable error bounds.

desk verdict Worth a referee's time, provided the full paper with Propositions 13 and 16 is attached; the idea is genuinely new and the self-criticism is unusually honest. read the letter →

arxiv 2412.16690 v2 pith:DQM4BXII submitted 2024-12-21 quant-ph

Dirk Oliver Theis This is my paper · ORCID

classification quant-ph

keywords stabilizerstatesquantumstatecertificationdirectfidelityestimationminimumofmeansfalse-positiveratefalse-negativeNISQtestingrandombasis

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proposes a quantum-state certification protocol, Basis-Min-of-Means (BMoM), that checks whether an experimentally prepared state is close to a known stabilizer target state. Instead of averaging over many random stabilizer measurements, it samples one random basis of the stabilizer group, estimates each basis element's expectation value with many identical shots, and accepts only if the minimum of those estimates is high. The author proves that this protocol needs only n measurement settings rather than O(1/epsilon), and that it comes with rigorous worst-case guarantees: good states (fidelity at least 1−δ) are never intrinsically rejected, and bad states (fidelity at most 1−ε) are rejected except with probability exponentially small in n for fixed gap parameters. The motivation is in-situ testing of near-term quantum computers, where switching measurement bases is expensive while repeating identical shots is cheap.

What carries the argument

The protocol's load-bearing object is a uniformly random basis of the stabilizer group of the target state, together with a certificate function that takes the minimum of the n estimated expectation values. The key mechanism is amplification through randomization: for a fixed basis the minimum expectation of a bad state can be as low as 1−O(ε/n), but when the basis is drawn uniformly at random, the probability that every basis element's expectation exceeds 1−αε becomes exponentially small in n (for α<1 fixed). This randomization converts a weak fixed-basis bound (inherited from Somma et al.) into a strong worst-case guarantee.

What would settle it

Evaluate the probability numerically for a concrete bad state, e.g., a pure state orthogonal to the target, at n around 20 with α=1/4: if the fraction of random stabilizer bases whose minimum expectation exceeds 1−αε is not below the claimed O(((α+1)/2)^n) bound, the false-positive analysis is wrong.

Watch

Extended reading notes

Core claim

The central claim is that BMoM certifies a stabilizer state with overwhelming probability: any state with fidelity at least 1−δ is accepted and any state with fidelity at most 1−ε is rejected. The false-negative part is deterministic with ω=2 — for every good state, every element of every basis of the stabilizer group has expectation at least 1−2δ — and the intrinsic false-positive probability is bounded above by O(((α+1)/2)^n) and below by $2^{{−Ω(n/α)}}$, where the parameters are tied by ωδ(1+γ_good) = β = (1−γ_bad)αε. This is achieved with exactly n measurement settings, each repeated m times, in contrast to DFE-C which requires O(1/ε) settings. The paper also claims, as a hypothesis rather than a proven result, that the non-linear minimum-of-means certificate can catch some faults that linear averages miss.

Load-bearing premise

The false-positive guarantee depends on a combinatorial probability estimate — that for every bad state a uniformly random stabilizer basis makes every basis element's expectation exceed 1−αε with probability at most η_n(α) — which is only stated, not proved, in this extended abstract.

Editorial extensions

If this is right

A stabilizer state can be certified with exactly n measurement settings, each repeated m times, with worst-case bounds on both accepting bad states and rejecting good states.
When switching measurement bases is the dominant cost, BMoM can certify a state with fewer wall-clock seconds than DFE-C, even though its total shot count is larger.
The protocol requires a wide fidelity gap: the analysis needs ε > 2δ, and suggests ε ≈ 8δ for small qubit counts, to make intrinsic false positives negligible.
Using the minimum instead of the mean gives the certificate a non-linear component, which in principle can distinguish some faults whose effects cancel in a linear average, though the paper presents this as a hypothesis.
The intrinsic false-positive probability decreases exponentially in n/α, so larger systems and wider gaps automatically become safer for fixed α.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the omitted combinatorial bound holds, the same random-basis-plus-minimum amplification could be applied to other groups of observables, such as generators of graph states or hypergraph states, yielding verification protocols with few settings for those families too.
The paper leaves open replacing the deterministic factor ω=2 by a probabilistic ω<2; if that succeeds, the effective gap requirement shrinks and BMoM becomes viable for ε closer to 2δ, where DFE-C operates.
The fault-detection advantage of the non-linear certificate is untested; a simulation study of specific fault models, e.g., a two-qubit gate that intermittently misfires, could confirm or refute it before any hardware trial.
Should future NISQ hardware make basis switching as cheap as identical shots, the latency-based motivation disappears and BMoM's remaining value would rest on the still-unproven fault-detection hypothesis.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Punchline: this is a genuinely new protocol idea, clearly presented, but the central false-positive proof is not in the submitted artifact — it lives in a separate full paper. Worth refereeing, with the full paper attached.

What is actually new: Somma et al. fix a basis and use an affine combination of expectation values; BMoM randomizes the basis and uses the minimum of per-observable means. That change is simple but not in the prior literature, and the paper gives rigorous worst-case bounds for both error directions, including an exponential-in-n intrinsic false-positive probability. The deterministic no-false-negative fact (ω=2) is elementary and correct. The paper also has a refreshingly honest critical evaluation section: it states plainly that BMoM works only for n≪1000 and ε>2δ, that the lower/upper bounds are far apart, that the lower bound lacks a closed form, and that the practical speed-up depends on shots being much cheaper than basis switching. Credit where due: the author identifies the narrow regime of applicability better than most.

The soft spot: fact (b) in §2.2.b.i — the upper bound on the intrinsic false-positive probability — is asserted, with proofs deferred to Propositions 13 and 16 of a full paper that is not part of the arXiv artifact. This is the load-bearing step. If that bound were wrong, BMoM could accept bad states with non-negligible probability. I agree with the stress-test note that this is the real issue. That said, the note's own short counting argument (using ∑_{s≠I}(1−tr(sρ)) = 2^n(1−F)) suggests the lemma is true; I'm not accusing the author of a false claim, just noting the artifact is not self-contained. No code or simulations accompany the text, and the non-linear fault-catching motivation is explicitly a hypothesis. These are addressable weaknesses, not fatal ones.

Who should read this: anyone working on stabilizer-state verification or NISQ testing. The protocol is simple enough to implement, and the analysis framework (intrinsic vs statistical mistakes) is useful. For peer review: yes, send it out, but require the full paper's proof of Propositions 13 and 16 to be included or at least stated completely. The extended abstract alone doesn't establish the main theorem.

Referee Report

2 major / 4 minor

Summary. The paper proposes BMoM (Basis-Min-of-Means), a protocol for certifying stabilizer states. The protocol samples a random basis of the stabilizer group, estimates the expectation value of each basis element by m identical shots, and accepts if the minimum of these estimates is at least 1−β. The paper claims deterministic absence of intrinsic false negatives for good states (fidelity ≥ 1−δ) when the gap parameter ω=2, and bounds on the intrinsic false-positive probability for bad states (fidelity ≤ 1−ε): an upper bound O(((α+1)/2)^n) and a lower bound 2^{−Ω(n/α)}, where α is a parameter in Eq. (2) relating δ and ε. The statistical-noise analysis is sketched through Chernoff bounds and a partition of the fidelity gap. The manuscript is explicitly an extended abstract, with the proofs of the main false-positive bounds deferred to Propositions 13 and 16 of an external full paper.

Significance. If the deferred combinatorial bounds are correct, the paper offers a conceptually clean result: randomizing over stabilizer bases and taking the minimum of the empirical means amplifies the fidelity gap, reducing the worst-case factor from O(n) in Somma et al.'s bound to O(1). The deterministic no-false-negative part (ω=2) is elementary and correct, and the author is unusually candid about the method's practical limitations. However, the central false-positive guarantee is not proved in the submitted artifact; the main theorem is therefore conditional on an external proof. The paper also contains no formal statement of the total error probability combining intrinsic and statistical errors. The significance is real but presently unverified from the manuscript alone.

major comments (2)

[§2.2.b.i and Introduction (p.2)] The central false-positive guarantee is stated as fact (b) in §2.2.b.i: for every bad state, the probability over a uniformly random stabilizer basis that all basis elements have expectation above 1−αε is at most η_n(α)=O(((α+1)/2)^n). This bound is load-bearing: it is the only quantitative support for the claim that BMoM rejects bad states with overwhelming probability. The proof is deferred to Propositions 13 and 16 of an external full paper, which is not part of the arXiv artifact, and the submitted text does not even sketch the argument. Because the abstract promises 'mathematically rigorous analysis' of the false-positive rate, the proof (or at least a complete proof sketch) must be included in the submitted manuscript; otherwise the main theorem remains unverifiable.
[§2.2.b and §2.2.b.i] The paper never states a formal theorem that combines the intrinsic-error bounds (facts (a) and (b)) with the statistical-noise analysis into a total error probability for the full protocol. The abstract claims that the protocol 'with overwhelming probability, accepts any good state ... and rejects any bad state,' but the only explicit quantitative statements in the artifact are the intrinsic bounds; the choice of m, β, γ_good, γ_bad to achieve a target total error probability p is described only informally ('one uses Chernoff's theorem' in §2.1). A precise statement of the achieved false-negative and false-positive probabilities as functions of all parameters is needed to substantiate the abstract's claim.

minor comments (4)

[§2.2.c] The passage 'No clear instances of outright grammatical errors or significant misuses of language appear in this text...' appears to be a leftover note to the author or editor and should be removed; it is not part of a scientific manuscript.
[§2.2.b and §1.1] The example 'α = 1/4 if n ≥ 47' seems inconsistent with the typical choice 'ε = 8δ' stated in §1.1: Eq. (2) requires 2δ < αε, so for α=1/4 one needs ε > 8δ, leaving no room for γ_good and γ_bad when ε = 8δ. Please clarify the required margins or correct the numeric examples.
[Figure 2 caption] The caption references Propositions 13 and 16 of the full paper, which are not in the submitted artifact; since the figure is meant to display the paper's bounds, the caption should either describe the plotted functions explicitly or the relevant definitions should be included in the artifact.
[Footnote 4 (p.2)] The footnote 'A useless observation in view of our stated target of n ≪ 1000...' is informal and distracts from the technical presentation; consider rewriting it as a neutral remark about the asymptotic regime.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: BMoM's guarantees rest on external stabilizer/fidelity results and deferred probabilistic lemmas, not on fitted inputs or self-referential definitions.

full rationale

BMoM's derivation chain is not circular. The accept/reject rule in Algorithm 2 is a stated design choice—estimate each basis element's expectation and take the minimum—and the analysis then decomposes correctness into two mathematical claims. The no-false-negative claim in §2.2.b.i(a), with ω=2, follows from the stabilizer identity tr(xρ) ≥ 2F−1 ≥ 1−2δ for every non-identity stabilizer x and every good state ρ, an external consequence of fidelity and the stabilizer formalism, not a restatement of the desired conclusion. The few-false-positives claim in §2.2.b.i(b) is a nontrivial probabilistic lemma about random stabilizer bases for states with fidelity ≤1−ε; its proof is stated to be in the full paper (Propositions 13 and 16), and the arXiv artifact does not contain that proof. That is a completeness/verifiability limitation, but the claim is not defined in terms of the bound it is supposed to prove, nor is any fitted parameter renamed as a prediction. The threshold partition in Eq. (2) merely fixes free parameters (γgood, γbad, α, ω=2) from δ and ε; it does not force the theorem. The lower and upper bounds on intrinsic false positives are independent estimates, and the paper's own §1.3 candidly lists weaknesses. The only self-reference is the pointer to the author's full paper; it is load-bearing for proof details, but it is not a self-citation chain that makes the conclusion equivalent to its input. Hence no significant circularity; score 1 reflects only the minor full-paper deferral.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The central guarantee rests on standard probability bounds, the stabilizer fidelity inequality, a sampling oracle, and on the unverified full-paper combinatorial lemma for random bases. The parameters α, ω, γgood, and γbad are explicit design choices in the threshold partition, not fitted constants. No new physical entities are introduced.

free parameters (4)

α = chosen by user; example α=1/4 for n≥47
Multiplicative gap on the bad-state expectation threshold; appears in the partition ωδ(1+γgood)=β=(1−γbad)αε and controls the intrinsic false-positive rate. Chosen by hand to make the certification gap fit.
ω = 2
Multiplicative gap on the good-state expectation threshold; set to 2 so that every basis element of a good state has expectation above the accept threshold deterministically, ruling out intrinsic false negatives.
γgood
Statistical-noise gap above the good-state threshold; tuned together with γbad when deriving β and the inner-loop shot count m from the fidelity bounds.
γbad
Statistical-noise gap below the bad-state threshold; tuned together with γgood to balance false-positive and false-negative probabilities from measurement noise.

assumptions (5)

standard math Multiplicative Chernoff bounds govern the accuracy of each mean estimate.
Used in Sections 2.1 and 2.2 to convert inner-loop shot counts into upper bounds on statistical mistake probabilities.
standard math For a state with fidelity F to a stabilizer state, every stabilizer expectation satisfies tr(xρ) ≥ 2F−1.
This yields the deterministic no-false-negative property at ω=2 in Section 2.2.b.
domain assumption An oracle can sample a uniformly random basis of the stabilizer group of the prepared state.
Algorithm 2 requires this primitive; the paper notes it can be realized by rejection sampling with constant expected overhead.
domain assumption Repeated shots of an unchanged circuit are negligible in cost compared to switching measurement bases.
This shots-cheap cost model motivates BMoM in Section 1.1 and is needed for its wall-clock advantage over DFE-C; the author warns it may fail on future hardware.
ad hoc to paper The full-paper combinatorial bounds on the intrinsic false-positive probability (Propositions 13 and 16) are correct.
The extended abstract states these bounds without proof and relies on them for the rejection guarantee; they are not derived in this document.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Verifying a stabilizer state with few observables but many shots." pith.science (2026). https://pith.science/paper/DQM4BXII

@misc{pith2026241216690,
  author       = {Pith},
  title        = {Pith review of: Verifying a stabilizer state with few observables but many shots},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DQM4BXII}},
  note         = {Machine review of arXiv:2412.16690}
}

read the original abstract

We propose a quantum-state-certification protocol for stabilizer states, motivated by application in in-situ testing of NISQ-era quantum computer systems: The number of qubits is bounded, and in terms of cost of running the protocol, identical repetition of quantum circuits contribute negligibly compared to switching the measurement bases. The method builds on Direct Fidelity Estimation and work by Somma et al.~(2006), but replaces linear averages by a minimum over estimates of expectation values. We provide mathematically rigorous analysis of the false-negative and false-positive rates.

Figures

Figures reproduced from arXiv: 2412.16690 by the authors.

**Figure 1.** NISQ Computer-System Testing. This is a simplified system diagram of an example NISQ-era quantum computer system. (a) Unavoidable quantum error happens in the quantum hardware (green). Faults can be present in any of the yellow-colored components (boxes). Certification functions that are affine in the measurement results (such as averages) cannot distinguish between the effect of faults and the effect of quantum er… view at source ↗

**Figure 2.** Intrinsic false-positive probabilities: Lower and upper bounds. The plots show the intrinsic false-positive probability lower and upper bounds in the form in which they are proven in §4.4 of the full paper , see Propositions 13 and 16 there. The probability 10−12 is marked with a dashed horizontal line, as an example of an acceptable rate of intrinsic false positives. It could be concluded that for more than 64 qubi… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 13 canonical work pages

[1]

Scalable Experimental Bounds for Entangled Quantum State Fidelities

Shamminuj Aktar, Andreas B ¨artschi, Abdel-Hameed A. Badawy, and Stephan Eiden- benz. Scalable experimental bounds for entangled quantum state fidelities.ACM Trans- actions on Quantum Computing, 5(4):1–21, 2024. arXiv:2210.03048

work page Pith review arXiv 2024
[2]

Sampling Groups of Pauli Operators to Enhance Direct Fidelity Estimation

J ´ulia Barber `a-Rodr´ıguez, Mariana Navarro, and Leonardo Zambrano. Sampling groups of pauli operators to enhance direct fidelity estimation. arXiv preprint, 2025. arXiv:2501.19228

work page Pith review arXiv 2025
[3]

da Silva, Olivier Landon-Cardinal, and David Poulin

Marcus P. da Silva, Olivier Landon-Cardinal, and David Poulin. Practical characteriza- tion of quantum devices without tomography. Physical Review Letters, 107(21):210404,

work page
[4]

Optimal verification of stabilizer states

Ninnat Dangniam, Yun-Guang Han, and Huangjun Zhu. Optimal verification of stabi- lizer states. Physical Review Research, 2(4):043323, 2020. arXiv:2007.09713

work page Pith review arXiv 2020
[5]

Ran- domized benchmarking with stabilizer verification and gate synthesis

Ellen Derbyshire, Rawad Mezher, Theodoros Kapourniotis, and Elham Kashefi. Ran- domized benchmarking with stabilizer verification and gate synthesis. arXiv preprint,

work page
[6]

Flammia and Yi-Kai Liu

Steven T. Flammia and Yi-Kai Liu. Direct fidelity estimation from few pauli measure- ments. Physical Review Letters, 106(23):230501, 2011. arXiv:1104.4695

arXiv 2011
[7]

Verification of quantum computation: An overview of existing approaches

Alexandru Gheorghiu, Theodoros Kapourniotis, and Elham Kashefi. Verification of quantum computation: An overview of existing approaches. Theory of Computing Sys- tems, 63:715–808, 2019. arXiv:1709.06984

arXiv 2019
[8]

Certifying almost all quantum states with few single-qubit measurements

Hsin-Yuan Huang, John Preskill, and Mehdi Soleimanifar. Certifying almost all quantum states with few single-qubit measurements. In IEEE 65th Annual Sym- posium on Foundations of Computer Science (FOCS) , pages 1202–1206. IEEE, 2024. arXiv:2404.07281

arXiv 2024

Show all 19 references

[9]

Quan- tum process tomography with digital twins of error matrices

Tangyou Huang, Akshay Gaikwad, Ilya Moskalenko, Anuj Aggarwal, Tahereh Abad, Marko Kuzmanovic, Yu-Han Chang, Ognjen Stanisavljevic, Emil Hogedal, Christo- pher Warren, Irshad Ahmad, Janka Bizn ´arov´a, Amr Osman, Mamta Dahiya, Mar- cus Rommel, Anita Fadavi Rousari, Andreas Nyl...

2025
[10]

Amir Kalev, Anastasios Kyrillidis, and Norbert M. Linke. Validating and certifying stabilizer states. Physical Review A, 99(4):042337, 2019. arXiv:1808.10786

2019 arXiv
[11]

Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma. Nonstabilizerness deter- mining the hardness of direct.. fidelity estimation. Physical Review A, 107(2):022429,
[12]

A simple protocol for certifying graph states and applications in quantum networks

Damian Markham and Alexandra Krause. A simple protocol for certifying graph states and applications in quantum networks. Cryptography, 4(1):3, 2020. arXiv:1801.05057

2020 arXiv
[13]

Optimal verification of entan- gled states with local measurements

Sam Pallister, Noah Linden, and Ashley Montanaro. Optimal verification of entan- gled states with local measurements. Physical Review Letters , 120(17):170502, 2018. arXiv:1709.03353

2018 arXiv
[14]

Somma, John Chiaverini, and Dana J

Rolando D. Somma, John Chiaverini, and Dana J. Berkeland. Lower bounds for the fidelity of entangled-state preparation. Physical Review A , 74(5):052302, 2006. arXiv:quant-ph/0606023. 14

2006 arXiv
[15]

Verification of many-qubit states

Yuki Takeuchi and Tomoyuki Morimae. Verification of many-qubit states. Physical Review X, 8(2):021060, 2018. arXiv:1709.07575

2018 arXiv
[16]

Divide- and-conquer verification method for noisy intermediate-scale quantum computation

Yuki Takeuchi, Yasuhiro Takahashi, Tomoyuki Morimae, and Seiichiro Tani. Divide- and-conquer verification method for noisy intermediate-scale quantum computation. Quantum, 6:758, 2022. arXiv:2109.14928

2022 arXiv
[17]

Sørensen

Konstantin Tiurev and Anders S. Sørensen. Fidelity measurement of a multiqubit cluster state with minimal effort. Physical Review Research , 4(3):033162, 2022. arXiv:2107.10386

2022 arXiv
[18]

Detecting multipartite entan- glement structure with minimal resources

You Zhou, Qi Zhao, Xiao Yuan, and Xiongfeng Ma. Detecting multipartite entan- glement structure with minimal resources. npj Quantum Information , 5(1):83, 2019. arXiv:1904.05001

2019 arXiv
[19]

General framework for verifying pure quan- tum states in the adversarial scenario

Huangjun Zhu and Masahito Hayashi. General framework for verifying pure quan- tum states in the adversarial scenario. Physical Review A , 100(6):062335, 2019. arXiv:1909.01943. 15

2019 arXiv

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [1]

Scalable Experimental Bounds for Entangled Quantum State Fidelities

Shamminuj Aktar, Andreas B ¨artschi, Abdel-Hameed A. Badawy, and Stephan Eiden- benz. Scalable experimental bounds for entangled quantum state fidelities.ACM Trans- actions on Quantum Computing, 5(4):1–21, 2024. arXiv:2210.03048

work page Pith review arXiv 2024

[2] [2]

Sampling Groups of Pauli Operators to Enhance Direct Fidelity Estimation

J ´ulia Barber `a-Rodr´ıguez, Mariana Navarro, and Leonardo Zambrano. Sampling groups of pauli operators to enhance direct fidelity estimation. arXiv preprint, 2025. arXiv:2501.19228

work page Pith review arXiv 2025

[3] [3]

da Silva, Olivier Landon-Cardinal, and David Poulin

Marcus P. da Silva, Olivier Landon-Cardinal, and David Poulin. Practical characteriza- tion of quantum devices without tomography. Physical Review Letters, 107(21):210404,

work page

[4] [4]

Optimal verification of stabilizer states

Ninnat Dangniam, Yun-Guang Han, and Huangjun Zhu. Optimal verification of stabi- lizer states. Physical Review Research, 2(4):043323, 2020. arXiv:2007.09713

work page Pith review arXiv 2020

[5] [5]

Ran- domized benchmarking with stabilizer verification and gate synthesis

Ellen Derbyshire, Rawad Mezher, Theodoros Kapourniotis, and Elham Kashefi. Ran- domized benchmarking with stabilizer verification and gate synthesis. arXiv preprint,

work page

[6] [6]

Flammia and Yi-Kai Liu

Steven T. Flammia and Yi-Kai Liu. Direct fidelity estimation from few pauli measure- ments. Physical Review Letters, 106(23):230501, 2011. arXiv:1104.4695

arXiv 2011

[7] [7]

Verification of quantum computation: An overview of existing approaches

Alexandru Gheorghiu, Theodoros Kapourniotis, and Elham Kashefi. Verification of quantum computation: An overview of existing approaches. Theory of Computing Sys- tems, 63:715–808, 2019. arXiv:1709.06984

arXiv 2019

[8] [8]

Certifying almost all quantum states with few single-qubit measurements

Hsin-Yuan Huang, John Preskill, and Mehdi Soleimanifar. Certifying almost all quantum states with few single-qubit measurements. In IEEE 65th Annual Sym- posium on Foundations of Computer Science (FOCS) , pages 1202–1206. IEEE, 2024. arXiv:2404.07281

arXiv 2024