Pith. sign in

REVIEW 3 major objections 5 minor 5 cited by

Few Single-Qubit Measurements Suffice to Certify Any Quantum State

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Every pure n-qubit state can be certified against a lab state using only single-qubit measurements, with adaptivity inside each copy provably essential.

desk verdict The algorithm idea is strong and likely right, but the main theorem has a real zero-amplitude gap, and the lower bound needs more care. read the letter →

arxiv 2506.11355 v2 pith:YTGXDI2M submitted 2025-06-12 quant-ph cs.DS

Meghal Gupta , William He , Ryan O'Donnell This is my paper
classification quant-phcs.DS PACS 03.67.-a
keywords quantumstatecertificationsingle-qubitmeasurementsadaptivedecisiontreebasisphasestatesfidelitygapcopycomplexityverification
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

This paper claims that every pure $n$-qubit state can be certified using only single-qubit measurements: an adaptive procedure applied to $O(n/\epsilon)$ copies of the lab state, with $O(n^2)$ total single-qubit measurements, distinguishes fidelity at least $1 - \epsilon/(2n)$ from fidelity at most $1 - \epsilon$. Prior to this work, no algorithm with polynomially many single-qubit measurements was known even to exist for arbitrary pure states, so the claim resolves the main open question raised in that line of work. The proof uses decision-tree bases in which the conditioned hypothesis state is a phase state, reducing the certification problem to a fidelity-gap calculation that telescopes to $(1-F)/n$, where $F = \langle \mathrm{hyp}|\rho_{\mathrm{lab}}|\mathrm{hyp}\rangle$ is the fidelity. The paper also proves the adaptivity is necessary: any algorithm that measures each copy in a mostly-fixed product basis, with only $o(n)$ qubits chosen adaptively, requires exponentially many copies for the worst-case state.

What carries the argument

The DT basis (Definition 3) is the central object: a depth-$n$ binary tree whose outgoing edges are labelled by orthogonal single-qubit states, which defines an orthonormal basis of product states and can be measured by an adaptive sequence of single-qubit measurements. Corollary 7 shows that for any two $n$-qubit states there exists a DT basis in which both are phase states, meaning every leaf outcome occurs with equal probability. The subtest (Definition 8) measures the tail of the lab state in such a basis and compares the final qubit to the hypothesis' conditioned state; Theorem 11 shows the subtest's accept and reject probabilities dominate the squared fidelity and the fidelity gap $\Delta$, respectively, and Proposition 12 telescopes the expected gap to $(1-F)/n$. Lemma 16 implements the DT-basis construction in $O(n)$ time using the oracle of Definition 15.

What would settle it

Take the hard state $|\psi_C\rangle$ of Definition 18—the normalized superposition of $N \approx 2^{10^{-10}n}$ product states drawn from the four-vector SIC-POVM $\{|\chi_0\rangle,|\chi_1\rangle,|\chi_2\rangle,|\chi_3\rangle\}$—and run any candidate certification algorithm on copies of $\rho_C = \frac{1}{N}\sum_s |\psi_{c_s}\rangle\langle\psi_{c_s}|$; if $2^{o(n)}$ copies distinguish the two using only $10^{-8}n$-adaptive product bases, Theorem 2 is false, while if the proposed algorithm succeeds only with the oracle of Definition 15 and fails when that oracle is replaced by a circuit description of $|\psi_C\rangle$, the oracle model is doing essential work.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: given an oracle that returns $\langle \mathrm{hyp}|\Pi|\mathrm{hyp}\rangle$ for any tensor product of single-qubit projectors, and one copy of a possibly mixed $\rho_{\mathrm{lab}}$, the algorithm accepts with probability at least $F = \langle \mathrm{hyp}|\rho_{\mathrm{lab}}|\mathrm{hyp}\rangle$ and rejects with probability at least $(1-F)/n$, using only single-qubit measurements and running in linear time. Repetition of this test turns the guarantee into the full certification theorem. The mechanism is the DT basis: for any pair of states, there is a decision-tree basis in which both are phase states, constructed level by level by choosing each qubit's basis orthogonal to the two current reduced states. After measuring a random prefix in the computational basis, the algorithm measures the remaining tail in the DT basis and then measures the last qubit against the hypothesis' conditioned state; the resulting subtest has accept probability at least the squared fidelity and reject probability at least the fidelity gap, and the expected gap over the random prefix is exactly $(1-F)/n$ by a telescoping sum.

Load-bearing premise

The algorithm's efficiency assumes an oracle that returns the exact probability $\langle \mathrm{hyp}|\Pi|\mathrm{hyp}\rangle$ for any tensor product of single-qubit projectors; without such an oracle, or with a noisy one, the decision-tree basis construction has no guarantee.

Editorial extensions

If this is right

  • Every pure $n$-qubit state, including highly entangled and Haar-random states, becomes certifiable with polynomially many single-qubit measurements; the open question of finding a state that resists such certification is closed in the negative.
  • Adaptivity within a copy is provably necessary: for the worst-case state, any algorithm that uses only $o(n)$ adaptively chosen qubits per copy needs exponentially many copies.
  • Repetition of the one-copy test yields $O(n \epsilon^{-1} \ln(1/\delta))$ copies with confidence $1-\delta$, matching the information-theoretic $\Omega(1/\epsilon)$ lower bound up to a factor of $n$.
  • Because the algorithm runs in time linear in the number of measurements, a hypothesis state given by a small-bond-dimension matrix product state can be certified efficiently under the oracle model.
  • The one-sided guarantees (accept with probability at least $F$, reject with probability at least $(1-F)/n$) combine with a Chernoff bound to give a two-sided test, which is the form stated in the Main Theorem.

Reading between the lines

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

  • The oracle model (Definition 15) is doing real work: a practical implementation must estimate single-qubit-projector probabilities, and the paper does not analyze noise in those estimates. A testable extension would be to make the algorithm robust to additive oracle error and see how the copy complexity degrades.
  • The phase-state flattening device—choosing a basis in which several candidate states are flat—may transfer to other verification tasks, such as certifying properties or rejecting a set of alternative hypotheses with a single product measurement.
  • Prior results on Haar-random states show no adaptivity is needed on average, while this paper shows the worst-case state needs $\Omega(n)$ adaptivity; quantifying the minimal adaptivity for intermediate ensembles, such as states with polynomial bond dimension, is a natural next step.
  • The lower bound's constants (the $10^{-8}n$ adaptivity threshold and the $0.99$ bound from the SIC-POVM geometry) are not optimized; a quantitative refinement would clarify how much adaptivity is needed for realistic $n$.
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

3 major / 5 minor

Summary. The paper claims two main results. First, Theorem 1: for any pure n-qubit hypothesis state, with oracle access to its classical description (Definition 15) and one copy of an arbitrary mixed lab state, there is an adaptive single-qubit measurement algorithm that accepts with probability at least the fidelity and rejects with probability at least the infidelity divided by n; repetition gives O(n/eps) copies for certification, resolving the open question of Huang, Preskill, and Soleimanifar. Second, Theorem 2: an exponential copy lower bound for certification algorithms that are only slightly adaptive, built from SIC-POVM vectors and a coding-theoretic construction. Section 2 develops the upper bound through decision-tree (DT) bases, a subtest analysis with exact acceptance/rejection expressions (Proposition 13), a fidelity-gap identity (Proposition 14), and a telescoping argument (Proposition 12). Section 3 sketches the lower bound via a total-variation comparison between a pure state and a mixed state in any slightly adaptive basis.

Significance. If both theorems were fully established, the upper bound would be a significant advance: it would show that arbitrary pure states—not just Haar-random or structured states—can be certified with polynomially many single-qubit measurements, and the lower bound would demonstrate that adaptivity is essential. The upper-bound proof has genuinely appealing features: the subtest analysis is exact and derived from first principles, the fidelity-gap inequality follows cleanly from Cauchy-Schwarz, and the telescoping identity is elegant. The lower-bound construction is also interesting. However, the paper as written contains a load-bearing gap in the upper bound (zero-amplitude branches) and substantial gaps in the lower-bound proof, so the advertised claims are not yet established.

major comments (3)
  1. [Section 2.2, Algorithm 1 and Corollary 7] Algorithm 1 is undefined for hypotheses with zero computational-basis branch amplitudes. For example, for |hyp> = |0^n>, when k=1 and x is the empty string, |hyp_{x1}> = 0, so Corollary 7 cannot produce a DT basis in which both |hyp_{x0}> and |hyp_{x1}> are phase states, and Step 3 has no defined basis to use. This is not a measure-zero corner case: it occurs for every computational basis state. The subsequent analysis inherits the problem: Theorem 11 and Proposition 14 implicitly require both branch states to be normalized, and Proposition 12's telescoping sum assumes all |hyp_{xb}> are defined. Since Theorem 1 claims to hold for every pure hypothesis state, this is a load-bearing gap. A fix must be supplied, for example by first reducing to a hypothesis with all nonzero amplitudes or by adding an explicit handling of zero-support branches.
  2. [Section 3.2, Lemma 21] The proof of Lemma 21 relies on the graph-theoretic assertion that any five pairs of indices either have a vertex of degree 3 or form a disjoint union of cycles and edges. This assertion is false: five pairs can form a path of length five, such as {1,2}, {2,3}, {3,4}, {4,5}, {5,6}, which has maximum degree 2 and is not a disjoint union of cycles and single edges. Since the subsequent labeling and Chernoff argument, as well as the conclusion that at most four non-bad pairs exist, depends on this dichotomy, the proof of Lemma 21 is incomplete. The lower bound of Theorem 2 is therefore not established as written.
  3. [Section 3, Claim 17] Claim 17 is stated with only a one-sentence proof: 'These vectors are far from coplanar, so the result follows.' The claim is a uniform quantitative statement over all single-qubit bases, with a specific bound of 0.99, and it is the per-qubit contraction mechanism for Lemma 21. A rigorous derivation or a verification of the numerical constant is needed. As it stands, the claim is an unproved geometric assertion in a central part of the lower-bound proof.
minor comments (5)
  1. [Section 2.3, Theorem 11] The statement says the DT basis makes |hyp_{x0}> and |lab_{x1}> phase states, but the proof and Algorithm 1 require the hypothesis branches |hyp_{x0}> and |hyp_{x1}>; the lab state is unknown to the algorithm, so this must be a typo.
  2. [Section 2.3, Proposition 13, Eq. (3)] The displayed chain for the acceptance probability contains a malformed term 'a1 ζ_l v1_l |1⟩)' with a stray '|1⟩)' that should be removed.
  3. [Section 2.4, Lemma 16] In the proof, the second reduced state is written as 'ρ0_t' but should be 'ρ1_t'.
  4. [Section 3.2] The text repeatedly refers to '10^{-8}n-adaptive bases', but Definition ℓ-adaptive requires ℓ to be an integer; floors should be used, and the relationship between the constant 10^{-8} and the constants c2, c3, c4 in Theorem 2 should be stated explicitly.
  5. [Section 3.1, Definition 18] The notation C := (c_1, ..., c_N) is confusing because each c_s is itself an n-tuple over {0,1,2,3}; writing C = (c^1, ..., c^N) or explicitly clarifying the indexing would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the certification algorithm's acceptance and rejection bounds are derived by direct algebraic inequalities and telescoping sums, not by fitting, renaming, or self-citation.

full rationale

The paper's central derivation is self-contained. The algorithm's guarantees in Theorem 1 follow from Theorem 11, Proposition 12, and the elementary algebra of Propositions 13 and 14. Theorem 11 lower-bounds the subtest's rejection probability by the fidelity gap Delta and its acceptance probability by the squared fidelity; both inequalities are proved by expanding the relevant amplitudes and using Cauchy-Schwarz, not by assuming the conclusion. Proposition 12 then evaluates the expectation of Delta by telescoping: E_x[Delta] = (1/n)(1 - |<hyp|lab>|^2). No fitted parameter is renamed as a prediction, and no quantity in the analysis is defined to equal the target fidelity. The oracle access model (Definition 15) is an input specification: it tells the algorithm exact hypothesis probabilities, and the theorem's copy and measurement bounds are stated relative to that oracle; the proof of the lower bound (Theorem 2) does not depend on the oracle model and uses independent geometric and random-coding arguments. The only cited prior work used as a remark is the reference to [ZZJ20] for an alternative construction of Corollary 7, but Corollary 7 is proven directly via Lemma 6 and is not load-bearing from that citation. There is, however, a non-circular correctness gap worth flagging: Algorithm 1 is undefined when a branch state |hypx1> is the zero vector, since Corollary 7 and Definition 5 require a normalized phase state, so Theorem 1 as written does not cover hypotheses such as |0^n> without an additional reduction. This is a proof-coverage issue, not a circularity, because it does not involve fitting, self-citation, or defining the conclusion into the inputs.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The main theorem depends on the oracle access model (Definition 15) and on standard fidelity inequalities. The lower bound additionally assumes the existence of SIC-POVM states. No free parameters are fitted to data, and no new physical entities are introduced.

assumptions (3)
  • domain assumption Existence of a SIC-POVM (the tetrahedron) for a single qubit, with pairwise inner products of magnitude 1/3.
    Used in Definition 18 and Claim 17 to construct the hard-to-certify state; the paper cites this as a known object ('as in the SIC-POVM').
  • domain assumption Oracle access model (Definition 15): for any tensor product of single-qubit projectors, the oracle returns the exact probability <hyp|Prod|hyp>.
    The upper-bound algorithm and its O(n) implementation (Lemma 16) depend on this access; it is a modeling choice, not derived from a circuit model.
  • standard math Standard probability and quantum-information tools: Chernoff bound, data processing inequality for fidelity, and Cauchy-Schwarz.
    Invoked throughout Sections 2 and 3 without proof; they are background results in the field.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Few Single-Qubit Measurements Suffice to Certify Any Quantum State." pith.science (2026). https://pith.science/paper/YTGXDI2M

@misc{pith2026250611355,
  author       = {Pith},
  title        = {Pith review of: Few Single-Qubit Measurements Suffice to Certify Any Quantum State},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YTGXDI2M}},
  note         = {Machine review of arXiv:2506.11355}
}
abstract

A fundamental task in quantum information science is state certification: testing whether a lab-prepared $n$-qubit state is close to a given hypothesis state. In this work, we show that every pure hypothesis state can be certified using only $O(n^2)$ single-qubit measurements applied to $O(n)$ copies of the lab state. Prior to our work, it was not known whether even subexponentially many single-qubit measurements could suffice to certify arbitrary states. This resolves the main open question of Huang, Preskill, and Soleimanifar (FOCS 2024, QIP 2024). Our algorithm also showcases the power of adaptive measurements: within each copy of the lab state, previous measurement outcomes dictate how subsequent qubit measurements are made. We show that the adaptivity is necessary, by proving an exponential lower bound on the number of copies needed for any nonadaptive single-qubit measurement algorithm.

Discussion (0). Sign in to comment.

Forward citations

Cited by 5 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Instance-Optimal Quantum State Certification with Entangled Measurements

    quant-ph 2025-07 accept novelty 9.0 of 10

    Quantum state certification with entangled measurements has copy complexity Θ~(∥σ*∥_{1/2}/ε²), where σ* is the hypothesis state with a small tail of eigenvalues removed.

  2. Robust quantum state certification and uncertainty principles for total influence

    quant-ph 2026-07 accept novelty 8.0 of 10

    For all but a 2^{-Ω(n)} fraction of n-qubit targets, nonadaptive single-qubit Pauli measurements certify ε-close vs O(ε)-far states using O(ε^{-2} log(1/δ)) copies.

  3. Certifying Quantum States with Uniform Measurements

    quant-ph 2025-08 conditional novelty 7.0 of 10

    Uniform (global) measurements suffice to efficiently certify a family of graph states, with a provable performance guarantee.

  4. Shallow quantum circuit for generating extremely low-entangled approximate state designs

    quant-ph 2025-07 reject novelty 7.0 of 10

    Approximate state t-designs can be built from low-entanglement states via random injective maps, but the claimed tight lower bound on magic fails for small t since stabilizer states form an exact 2-design with zero magic.

  5. Efficient certification of intractable quantum states with few Pauli measurements

    quant-ph 2025-11 reject novelty 6.0 of 10

    The paper claims Clifford-enhanced product states can be certified with O(n^2/epsilon^2) Pauli measurements in the i.i.d. setting and polynomially many in the adversarial setting, but the central estimator is derived ...

Reference graph

Works this paper leans on

22 extracted references · 18 canonical work pages · cited by 5 Pith papers

  1. [1]

    Reliable quantum certification of photonic state preparations

    Leandro Aolita, Christian Gogolin, Martin Kliesch, and Jens Eisert. Reliable quantum certification of photonic state preparations. Nature Communications , 6(1):8498, 2015

    work page 2015

  2. [2]

    Quantum state certification

    Costin Bădescu, Ryan O'Donnell, and John Wright. Quantum state certification. In Symposium on Theory of Computing (STOC) , pages 503--514. ACM, 2019

    work page 2019

  3. [3]

    Weak F ourier-- S chur sampling, the hidden subgroup problem, and the quantum collision problem

    Andrew Childs, Aram Harrow, and Pawe Wocjan. Weak F ourier-- S chur sampling, the hidden subgroup problem, and the quantum collision problem. In Symposium on Theoretical Aspects of Computer Science (STACS) , volume 4393, pages 598--609. Springer, Berlin, 2007

    2007

  4. [4]

    Direct fidelity estimation from few P auli measurements

    Steven Flammia and Yi-Kai Liu. Direct fidelity estimation from few P auli measurements. Physical Review Letters , 106(23):230501, 2011

    work page 2011

  5. [5]

    Fidelity witnesses for fermionic quantum simulations

    Marek Gluza, Martin Kliesch, Jens Eisert, and Leandro Aolita. Fidelity witnesses for fermionic quantum simulations. Physical Review Letters , 120(19):190501, 2018

    work page 2018

  6. [6]

    Verifiable measurement-only blind quantum computing with stabilizer testing

    Masahito Hayashi and Tomoyuki Morimae. Verifiable measurement-only blind quantum computing with stabilizer testing. Physical review letters , 115(22):220502, 2015

    work page 2015

  7. [7]

    A study of LOCC -detection of a maximally entangled state using hypothesis testing

    Masahito Hayashi, Keiji Matsumoto, and Yoshiyuki Tsuda. A study of LOCC -detection of a maximally entangled state using hypothesis testing. Journal of Physics A: Mathematical and General , 39(46):14427, 2006

    work page 2006

  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 Symposium on Foundations of Computer Science (FOCS) , pages 1202--1206. IEEE, 2024

    2024

Show all 22 references
  1. [9]

    Verifying commuting quantum computations via fidelity estimation of weighted graph states

    Masahito Hayashi and Yuki Takeuchi. Verifying commuting quantum computations via fidelity estimation of weighted graph states. New Journal of Physics , 21(9):093060, 2019

    2019

  2. [10]

    Theory of quantum system certification

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

    2021

  3. [11]

    Verification of phased D icke states

    Zihao Li, Yun-Guang Han, Hao-Feng Sun, Jiangwei Shang, and Huangjun Zhu. Verification of phased D icke states. Physical Review A , 103(2):022601, 2021

    2021

  4. [12]

    Efficient verification of bipartite pure states

    Zihao Li, Yun-Guang Han, and Huangjun Zhu. Efficient verification of bipartite pure states. Physical Review A , 100(3):032316, 2019

    2019

  5. [13]

    Efficient verification of D icke states

    Ye-Chao Liu, Xiao-Dong Yu, Jiangwei Shang, Huangjun Zhu, and Xiangdong Zhang. Efficient verification of D icke states. Physical Review Applied , 12(4):044020, 2019

    2019

  6. [14]

    Quantum proofs can be verified using only single-qubit measurements

    Tomoyuki Morimae, Daniel Nagaj, and Norbert Schuch. Quantum proofs can be verified using only single-qubit measurements. Physical Review A , 93(2):022326, 2016

    2016

  7. [15]

    Verification of hypergraph states

    Tomoyuki Morimae, Yuki Takeuchi, and Masahito Hayashi. Verification of hypergraph states. Physical Review A , 96(6):062321, 2017

    2017

  8. [16]

    Quantum spectrum testing

    Ryan O'Donnell and John Wright. Quantum spectrum testing. Communications in Mathematical Physics , 387(1):1--75, 2021

    2021

  9. [17]

    Practical characterization of quantum devices without tomography

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

    2011

  10. [18]

    Verification of many-qubit states

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

    2018

  11. [19]

    Optimal verification of general bipartite pure states

    Xiao-Dong Yu, Jiangwei Shang, and Otfried G \"u hne. Optimal verification of general bipartite pure states. npj Quantum Information , 5(1):112, 2019

    2019

  12. [20]

    Efficient verification of hypergraph states

    Huangjun Zhu and Masahito Hayashi. Efficient verification of hypergraph states. Physical Review Applied , 12(5):054047, 2019

    2019

  13. [21]

    Statistical methods for quantum state verification and fidelity estimation

    Huangjun Zhu and Masahito Hayashi. Statistical methods for quantum state verification and fidelity estimation. Physical Review A , 99(5):052346, 2019

    2019

  14. [22]

    Saturating the quantum C ram \'e r-- R ao bound using LOCC

    Sisi Zhou, Chang-Ling Zou, and Liang Jiang. Saturating the quantum C ram \'e r-- R ao bound using LOCC . Quantum Science and Technology , 5(2):025005, 2020

    2020

Pith tools

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