Pith. sign in

REVIEW 2 major objections 7 minor 16 references

Robust quantum state certification and uncertainty principles for total influence

T0 review · 2 major / 7 minor · reviewed 2026-07-30 · grok-4.5

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

Pith's one-line read Nonadaptive single-qubit Pauli measurements certify almost all quantum states with constant robustness and optimal copy complexity.

desk verdict Solid resolution of the CLSW two-basis conjecture with a real Boolean-analysis idea; constant is non-explicit and the proof is long, but the claim holds as stated. read the letter →

arxiv 2607.27184 v1 pith:R6XDNZXB submitted 2026-07-29 quant-ph

Andrea Coladangelo , Jerry Li , Joseph Slote This is my paper
classification quant-ph
keywords quantumstatecertificationsingle-qubitPaulimeasurementstotalinfluenceuncertaintyprincipleBooleananalysisclassicalshadowsHaar-randomstatesDirichletenergy
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

Certifying that a lab state is close to a pure target is a basic quantum task, but ideal measurements are as hard as preparing the target. This paper shows that for all but an exponentially small fraction of n-qubit targets, a simple nonadaptive protocol of single-qubit Pauli measurements already works: it accepts states within constant-factor fidelity of the target and rejects those that are farther, using only the information-theoretically optimal number of copies. The protocol essentially runs a known one-basis test in the X and Z bases (with a randomized holdout qubit) and amplifies by repetition and classical shadows. The proof reduces soundness to a new uncertainty principle: a function and its Fourier transform cannot both have small weighted total influence under the measures induced by a typical target and its Hadamard dual. That principle is the hypercube analogue of Heisenberg uncertainty for Dirichlet energies of Glauber dynamics, and it is what upgrades earlier non-robust or multi-qubit tests to constant robustness with only Pauli measurements.

What carries the argument

A weighted-influence uncertainty principle: with high probability over Haar-random f, every unit g orthogonal to f satisfies Inf_{μ_f}[g/f] + Inf_{μ_̂f}[ĝ/̂f] = Ω(n), equivalently Avg_f[g] + Avg_̂f[ĝ] ≤ 2−c. This spectral gap for the sum of the two one-basis acceptance operators drives the constant-robustness soundness.

What would settle it

Numerically sample Haar n-qubit states, form the operator M_f + H^{⊗n} M_̂f H^{⊗n}, and check whether its second eigenvalue stays bounded below 2 by a positive constant independent of n; a second eigenvalue drifting to 2 would falsify the claimed constant robustness.

Watch

Extended reading notes

Core claim

For all but a 2^{-Ω(n)} fraction of pure n-qubit targets, nonadaptive single-qubit Pauli measurements certify whether an unknown state is ε-close or O(ε)-far from the target, using O(ε^{-2} log(1/δ)) copies—optimal even among entangled measurements. Completeness is fidelity; soundness is infidelity up to a universal constant factor.

Load-bearing premise

The target must be a typical Haar state (or in the complementary almost-all set where the uncertainty principle holds), and the tester needs classical access to its amplitudes in both the standard and Hadamard bases.

Editorial extensions

If this is right

  • Almost all pure targets admit copy-optimal certification with only nonadaptive single-qubit Paulis and constant robustness.
  • The two-basis holdout test conjectured earlier is sound for typical targets without needing larger joint measurements.
  • Weighted total influence on the cube obeys a Heisenberg-type lower bound under typical dual Porter–Thomas measures.
  • Adaptivity remains necessary only if one insists on certifying every target, not almost every target.

Reading between the lines

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

  • If structured families (graph states, brickwork circuits) lie in the good set, the same Pauli protocol could certify industrially relevant states without Haar sampling.
  • Tightening the spectral gap of M_f + dual toward the numerical ~4 constant would make the test practical for distinguishing 99.9% vs 99.6% fidelity.
  • The Glauber-Dirichlet view suggests similar uncertainty principles may control robustness of other product-measurement tests on association schemes.
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.

Referee Report

2 major / 7 minor

Summary. The paper proves that nonadaptive single-qubit Pauli measurements certify almost all pure n-qubit target states with constant robustness and information-theoretically optimal copy complexity O(ε^{-2} log(1/δ)). Protocol 1 (slightly adaptive) and Protocol 2 (nonadaptive via classical shadows) accept with probability at least the fidelity and reject with probability at least a constant fraction of the infidelity, for all but a 2^{-Ω(n)} Haar fraction of targets. Soundness reduces (§4) to a spectral-gap claim for M_f + dM_bf on the orthogonal complement, equivalently an uncertainty principle Avg_f[g] + Avg_bf[ĝ] ≤ 2−c (Theorem 4) and a weighted-influence form Inf_μf[g/f] + Inf_μbf[ĝ/bf] ≳ n (Corollary 2 / Appendix C). The proof uses a win-win on Inf_μ, an A–B partition of the cube, metric entropy of low interior-influence functions via a linear extension Ext_A and local escape (Theorem 8), fixed-q concentration of Avg_bf[cf q] (Theorem 5), and operator-norm bounds on the B-part via Gaussianization and Tropp random paving (Theorem 9).

Significance. The result resolves Conjecture 1 of CLSW26 and closes the gap between constant robustness (previously requiring a log n-qubit measurement) and purely single-qubit Pauli measurements for almost all states. Copy complexity matches the entangled-measurement optimum. The technical contribution—an uncertainty principle for harmonic-mean weighted total influence / Glauber Dirichlet forms, with a hypercube Heisenberg analogue as the unweighted special case—is of independent interest in Boolean analysis and is developed with substantial new machinery (smoothed Herbst arguments, A-part extensions, Fourier-side paving). Premises (Haar-typical targets; two-basis amplitude oracle) are stated explicitly and are necessary by the GHO25 adaptivity lower bound. Concurrent work is fairly compared. Non-explicit C is a practical limitation but does not undercut the existence claim.

major comments (2)
  1. [Theorem 1, Corollary 1, §2.6, §8] Theorem 1 / Corollary 1 state soundness with a universal C>1, but the only quantitative control is existence of some c>0 in Theorem 4 (and the schematic 2−κ vs 1.75+small win-win in §2.5.3 and §8). Section 2.6 and Figure 2 indicate numerics suggest C≲5.5, yet no explicit lower bound on the spectral gap of M_f + H^{⊗n} M_bf H^{⊗n} is extracted from the estimates (κ, T, ε, paving density, smoothing η). For a result whose main applied claim is constant robustness, the manuscript should either (i) track constants through §§5–8 far enough to give a concrete C, or (ii) state prominently in Theorem 1/Corollary 1 and the abstract that C is non-constructive and may be large. This is load-bearing for how the result will be cited in practice.
  2. [§8 (Finishing the proof); cf. Theorem 9 and Corollary 6] In the finishing argument (§8), after centering by α and decomposing into A/B blocks, the bound Avg_bf[ĝ] ≤ 3/4 + 5ε is obtained from the 2×2 matrix with entries 1/2+2ε and 1/4+ε, then compared to 1−κ. The choice “κ < 1/4 − 5ε” and “H(CT^5 κ/ε^3) < 1/3” is only asserted to be possible; the dependence of the paving/AB errors (Theorem 9) on T, and of the net cardinality on T^5, means T must be taken large first, then κ small. A short explicit parameter hierarchy (choose ε_pave, then T, then κ, then net ε) should be written so that the intersection of the high-probability events in Theorems 5, 8, and 9 is visibly 1−2^{-Ω(n)} rather than left schematic.
minor comments (7)
  1. [§2.2, Definition 1] Definition 1 and §2.2: clarify whether the oracle returns exact complex amplitudes or approximates them to inverse-poly precision, and how approximation error propagates into the holdout projective measurement / shadow estimator in Protocols 1–2.
  2. [Protocol 2, Step 4] Protocol 2 accepts if ω̂ ≥ 1 − 3ε/(2C). The factor 3/2 is not derived in the main text; a one-line pointer to the shadow variance / Chernoff threshold would help.
  3. [Figure 1] Figure 1 table: “O(1)” copy complexity for this work is for constant ε,δ; the full dependence O(ε^{-2} log(1/δ)) appears only in Corollary 1. Align the table caption with Corollary 1.
  4. [§2.3, Proposition 1–3] Proposition 1 / unweighted uncertainty: the sharp constant (1−1/√2)n is nice; consider stating it in the abstract’s “Ω(n)” sentence or in §2.3 for readers coming from Boolean analysis.
  5. [Appendix A] Appendix A glossary is helpful but incomplete (e.g., Avg_f, M_f, dM_bf, q-compatibility). Expanding it would ease navigation of §§5–8.
  6. [§1, §2.1, Corollary 1] Typos: “measuremerents” (Corollary 1 statement); “succeds” (§2.5.2); “guarantess” (§2.1); “Wepauseheretomake...” spacing (§1).
  7. [Interlude after §5] Interlude (phase states) is pedagogically useful but sits between §5 and §6 without a number; label it as a numbered subsection or remark so it can be skipped cleanly as the text invites.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: soundness reduces to a proved weighted-influence uncertainty principle via self-contained analysis, not by definition or fitted inputs.

full rationale

The central claims (Theorem 1 / Corollary 1) are existence and high-probability statements over Haar-random targets. Completeness is elementary (A has |ψ⟩ as a +1 eigenvector). Soundness is reduced to Proposition 4 / Theorem 4 (Avg_f[g] + Avg_bf[bg] ≤ 2−c for g ⊥ f), equivalently Corollary 2 via the identity in Appendix C relating Avg to Inf_μ. That uncertainty principle is proved in Sections 5–8 by fixed-q concentration (Theorem 5: smoothing, Gaussian comparison, Herbst), A–B partition and local-escape extensions controlling metric entropy (Theorem 8), and operator-norm bounds on the B-part via Gaussianization and Tropp random paving (Theorem 9)—all derived in-paper from Steinhaus/Porter–Thomas facts, hypercontractivity, and cited external tools (Tropp, HPS canonical paths, Weissler). Self-citations to CLSW26 state a conjecture this work proves and compare prior protocols; they do not supply the gap. No parameter is fitted to data and renamed a prediction; Figure 2 is numerical illustration of C only. Haar-typicality and the two-basis oracle are explicit premises, not hidden redefinitions of the goal. The derivation is therefore independent of its conclusion by construction.

Assumptions & free parameters 2 free parameters · 6 assumptions · 2 invented entities

Load-bearing inputs are standard quantum/Boolean analysis plus domain modeling choices (Haar typicality, two-basis amplitude oracle, nonadaptive Pauli product measurements). No fitted physical constants. The robustness constant C is existential from spectral gap arguments, not data-fit. Invented objects are proof devices (weighted Inf_μ, A–B sets, Ext_A), not new physical entities.

free parameters (2)
  • Robustness constant C (and related spectral gap c) = existential C>1; numerics suggest <5.5
    Proved only as some universal C>1 (equivalently c>0 in Avg_f+Avg_bf≤2−c). Numerics suggest C<5.5 but are not part of the proof; κ, ε, T in the win-win and A–B arguments are chosen small/large enough for entropy vs concentration, not fitted to external data.
  • Threshold T for A–B partition and influence cutoff κ = T large, κ small enough that H(CT^5 κ/ε^3)<1/3
    T>1 and small κ>0 are chosen so covering numbers beat concentration and operator bounds stay ≤1/2+ε, 1/4+ε. Hand-chosen proof parameters, not empirical fits.
assumptions (6)
  • domain assumption Haar-random pure states induce Porter–Thomas / Dirichlet(1) measures on amplitudes with standard bias and concentration bounds (Lemma 1, Fact 1).
    Used throughout to get 1−2^{-Ω(n)} probability over targets; standard in random quantum states.
  • domain assumption Oracle access to amplitudes of |ψ⟩ in standard and Hadamard bases (Definition 1) suffices to compute post-measurement single-qubit target states.
    Access model between HPS and GHO; required for classical post-processing of the test.
  • standard math Tropp random-paving moment bounds for sparse coordinate projections of entrywise-small matrices (Tro08).
    Invoked for ∥Π_B M̂_bf Π_B∥_op and cross terms in §7.
  • standard math Steinhaus hypercontractivity / log-Sobolev and negative-moment Khintchine-type bounds for Steinhaus sums.
    Used for concentration of Avg_bf[cf q] and smoothing error (§5).
  • domain assumption Adaptivity is necessary to certify all states with single-qubit measurements (GHO25); hence almost-all is the right nonadaptive target.
    Frames why 2^{-Ω(n)} exceptional set is inherent, not a proof artifact.
  • standard math Identity Avg_f[g]=1−(1/n)Inf_{μ_f}[g/f] for nowhere-zero f (Appendix C).
    Elementary algebraic identity linking certification averages to weighted influence.
invented entities (2)
  • μ-weighted total influence Inf_μ (harmonic-mean edge weights / Glauber Dirichlet form) independent evidence
    purpose: Reformulate two-basis certification soundness as an uncertainty principle dualizing Inf under μ_f and μ_bf.
    Standard Dirichlet form for Glauber dynamics, specialized here to Porter–Thomas dual measures; not a new physical object.
  • A–B partition of the cube and linear extension Ext_A for low interior-influence functions
    purpose: Restore covering-number control on the typical-mass set A while handling atypical mass B by random paving.
    Proof devices built from HPS-style canonical paths and local escape; no independent ontology beyond the argument.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Robust quantum state certification and uncertainty principles for total influence." pith.science (2026). https://pith.science/paper/R6XDNZXB

@misc{pith2026260727184,
  author       = {Pith},
  title        = {Pith review of: Robust quantum state certification and uncertainty principles for total influence},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/R6XDNZXB}},
  note         = {Machine review of arXiv:2607.27184}
}
abstract

We show that nonadaptive single-qubit Pauli measurements suffice to test whether an unknown $n$-qubit state $\rho$ is $\varepsilon$-close to or $O(\varepsilon)$-far from an ideal target state $|\psi\rangle$, for all but a $2^{-\Omega(n)}$ fraction of target states. The test uses $O(\varepsilon^{-2}\log(1/\delta))$ copies of $\rho$ to achieve confidence $1-\delta$, which is information-theoretically optimal even among protocols with arbitrary joint measurements. The main technical innovation is an uncertainty principle for weighted generalizations of the total influence of Boolean functions. As a simple example, the unweighted variant states that $\mathbf{Inf}[f]+\mathbf{Inf}[\widehat{f}] = \Omega(n)$, which is a natural hypercube analogue of the Heisenberg uncertainty principle (here $\widehat{\,\cdot\,}$ denotes the $2^{-n/2}$-normalized Fourier transform). The weighted case generalizes $\mathbf{Inf}[\,\cdot\,]$ and $\mathbf{Inf}[\,\widehat{\,\cdot\,}\,]$ to Dirichlet energies associated with Glauber dynamics for certain dual measures on the cube.

Figures

Figures reproduced from arXiv: 2607.27184 by the authors.

Figure 1
Figure 1. Comparing this work to previous protocols certifying all or almost all target states. Green [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Numerical values for the uncertainty principle constant [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗

Review history (2 revisions) →

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

16 extracted references · 2 linked inside Pith

  1. [1]

    Benedetto and Paul J

    John J. Benedetto and Paul J. Koprowski. Graph theoretic uncertainty principles. In 2015 International Conference on Sampling Theory and Applications (SampTA) , pages 357--361, 2015

    2015

  2. [2]

    Quantum state certification

    Costin Badescu, Ryan O'Donnell, and John Wright. Quantum state certification. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019 , pages 503--514. ACM , 2019

    2019

  3. [3]

    The power of two bases: Robust and copy-optimal certification of nearly all quantum states with few-qubit measurements

    Andrea Coladangelo, Jerry Li, Joseph Slote, and Ellen Wu. The power of two bases: Robust and copy-optimal certification of nearly all quantum states with few-qubit measurements. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing , pages 1771--1776, 2026

    2026

  4. [4]

    Certifying localizable quantum properties with constant sample complexity

    Zhenyu Du, Jinchang Liu, Elias X Huber, Zi-Wen Liu, and Xiongfeng Ma. Certifying localizable quantum properties with constant sample complexity. arXiv preprint arXiv:2509.17580v3 , 2026

    arXiv 2026

  5. [5]

    Few single-qubit measurements suffice to certify any quantum state

    Meghal Gupta, William He, and Ryan O'Donnell. Few single-qubit measurements suffice to certify any quantum state. CoRR , abs/2506.11355, 2025

    arXiv 2025

  6. [6]

    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. Nature Physics , Sep 2025

    2025

  7. [7]

    Theory of quantum system certification

    Martin Kliesch and Ingo Roth. Theory of quantum system certification. PRX Quantum , 2:010201, Jan 2021

    2021

  8. [8]

    Concentration of measure and logarithmic Sobolev inequalities , page 120–216

    Michel Ledoux. Concentration of measure and logarithmic Sobolev inequalities , page 120–216. Springer Berlin Heidelberg, 1999

    1999

Show all 16 references
  1. [9]

    Levin and Yuval Peres

    David A. Levin and Yuval Peres. Markov Chains and Mixing Times . American Mathematical Society, Providence, RI, second edition, October 2017. With contributions by Elizabeth L. Wilmer

    2017

  2. [10]

    Universal and efficient quantum state verification via schmidt decomposition and mutually unbiased bases

    Yunting Li and Huangjun Zhu. Universal and efficient quantum state verification via schmidt decomposition and mutually unbiased bases. arXiv preprint arXiv:2506.19809 , 2025

    2025

  3. [11]

    Analysis of Boolean Functions

    Ryan O'Donnell. Analysis of Boolean Functions . Cambridge University Press, 2014

    2014

  4. [12]

    Negative moments of steinhaus sums, 2025

    Martin Rapaport, Tomasz Tkocz, and Isabella Wu. Negative moments of steinhaus sums, 2025

    2025

  5. [13]

    Efficient certification of intractable quantum states with few pauli measurements, 2025

    Sami Abdul Sater, Maxime Garnier, Thierry Martinez, Harold Ollivier, and Ulysse Chabaud. Efficient certification of intractable quantum states with few pauli measurements, 2025

    2025

  6. [14]

    Joel A. Tropp. The random paving property for uniformly bounded matrices. Studia Math. , 185(1):67--82, 2008

    2008

  7. [15]

    Logarithmic sobolev inequalities and hypercontractive estimates on the circle

    Fred B Weissler. Logarithmic sobolev inequalities and hypercontractive estimates on the circle. Journal of Functional Analysis , 37(2):218--234, 1980

    1980

  8. [16]

    Optimal verification and fidelity estimation of maximally entangled states

    Huangjun Zhu and Masahito Hayashi. Optimal verification and fidelity estimation of maximally entangled states. Phys. Rev. A , 99:052346, May 2019

    2019

Pith tools

Reviewed July 30, 2026 · model on record in the stance chip above.