Pith. sign in

REVIEW 3 minor 23 references

For every number of parties, the product test's exact worst-case acceptance curve is (1 + mω² + (1−mω)²)/2, closing the open low-overlap regime.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-01 07:20 UTC pith:GC24SXDI

load-bearing objection Exact product-test curve resolved for all n and ω; proof is elementary, correct, and a genuine advance, with only a minor fixed-dimension caveat.

arxiv 2607.21477 v1 pith:GC24SXDI submitted 2026-07-23 quant-ph

An Optimal Analysis of the Product Test

Jacob Beckey , Fernando Granha Jeronimo , Pei Wu This is my paper
classification quant-ph MSC 81P4581P6868Q12
keywords product testswap testquantum property testingproduct state fidelityunentangled quantum proofsQMA(k) to QMA(2) reductioncapped collision probabilitymultipartite entanglement
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper proves an exact formula for the worst-case acceptance probability of the product test, the standard circuit that checks whether an n-partite quantum state is fully unentangled by comparing corresponding registers of two copies. With ω denoting the largest squared overlap of the input with any product state and m = floor(1/ω), the formula reads PT_n(ω) = (1 + mω² + (1−mω)²)/2 for every n ≥ 2 and every ω in (0,1]. It recovers the previously known tight branch ω ≥ 1/2, supplies every low-overlap piece ω < 1/2, and implies that the acceptance probability approaches 1/2 as ω → 0, resolving an open question. The result also sharpens the one-shot soundness loss in the reduction from many unentangled quantum witnesses to two, from a constant 100 to a constant 4. A reader should care because this settles the exact soundness curve of a basic primitive in quantum property testing and unentangled-prover complexity.

Core claim

The central claim is Theorem 1.1: for every n ≥ 2 and every ω ∈ (0,1], the largest possible acceptance probability of the product test over all n-partite pure states with closest-product overlap ω is PT_n(ω) = (1 + s(ω))/2, where s(ω) = mω² + (1−mω)² and m = ⌊1/ω⌋. Equivalently, on each interval 1/(m+1) < ω ≤ 1/m the curve is the quadratic 1 − mω + m(m+1)ω²/2. The supremum is attained by a bipartite state whose squared Schmidt coefficients are the capped-simplex optimizer (ω, …, ω, 1−mω), tensored with arbitrary product states on the remaining registers; this is why the curve is independent of the number of parties. The matching upper bound is dimension-free and proceeds by a sharp first-swa

What carries the argument

The load-bearing object is the capped collision probability s(ω): the maximum of Σ_j p_j² over probability vectors with every entry at most ω, solved greedily by filling m = ⌊1/ω⌋ entries to height ω and putting the residual mass 1−mω on one more entry. Two quantum identities connect this classical quantity to the test: the product-test acceptance probability equals 2^{−n} Σ_{S⊆[n]} Tr(ρ_S²), and for bipartite inputs it reduces to (1 + Σ_j λ_j²)/2 with λ_j the squared Schmidt coefficients. The inductive upper bound rests on a first-swap reduction that keeps every diagonal Schmidt branch after the first local swap test, bounding only the off-diagonal branches by the norm of the remaining proj

Load-bearing premise

The theorem's worst-case curve lets the lower-bound construction choose local dimensions as large as about 1/ω; if an application fixes smaller local dimensions, the construction may not fit, and the formula could overstate the true worst-case acceptance for that fixed dimension.

What would settle it

Numerically maximize Σ_i λ_i² s(φ_i) over probability vectors λ and branch overlaps φ_i satisfying λ_i φ_i ≤ ω; Lemma 3.4 asserts the maximum is s(ω). A single instance, say near a reciprocal cap ω = 1/(m+1)+ε, where this sum exceeds s(ω) would break the inductive upper bound and falsify the curve. Equivalently, an explicit n-partite state with product overlap ω and acceptance probability above (1+s(ω))/2 would refute Theorem 1.1.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • The low-overlap limit is resolved: PT_n(ω) → 1/2 as ω → 0, with the quantitative bounds 1/2 ≤ PT_n(ω) ≤ 1/2 + ω/2.
  • The exact curve gives a tight trace-distance soundness statement: if a state is δ-far from every product state, the product test accepts with probability at most (1 + s(1−δ²))/2, which is 1 − δ² + δ⁴ when δ ≤ 1/√2.
  • The one-shot soundness parameter in the reduction from k unentangled witnesses to two improves from 1 − (1−σ)²/100 to 1 − (1−σ)²/4, where σ is the original soundness; the collapse QMA(k) = QMA(2) is unchanged.
  • The worst case cannot be worsened by adding parties: for every n ≥ 2, a bipartite state realizing the capped Schmidt spectrum, tensored with product states, is extremal, so the curve is n-independent.
  • At reciprocal points ω = 1/d the d-dimensional maximally entangled state is extremal and achieves acceptance (1 + 1/d)/2, matching the quadratic pieces that meet continuously at those breakpoints.

Where Pith is reading between the lines

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

  • The same capped-refinement accounting should transfer to any two-copy test whose acceptance depends only on branch collision probabilities, suggesting exact curves for related local-symmetric measurements could be derived by the same induction.
  • Because the matching construction needs local dimension ⌊1/ω⌋+1, the dimension-free curve may not be the exact worst case for fixed small local dimensions; a natural conjecture is that the fixed-dimension extremal curve is the same capped-simplex value truncated to the available Schmidt rank.
  • The paper notes but does not optimize the sharper soundness expression obtained from the full curve; a numerical or analytic optimization over the two branch overlaps could yield conversion parameters better than the uniform 1/4 constant for specific soundness ranges.
  • The piecewise-quadratic structure mirrors extremal density curves in graph theory; reading the proof as a template, one might expect exact property-testing soundness curves in other settings to be encoded by greedy concentration problems with a cap, indexed by how many active coefficients the cap permits.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 3 minor

Summary. The paper determines the exact worst-case acceptance probability of the product test for pure multipartite states as a function of the maximum squared overlap with a product state. It proves that for every n ≥ 2 and every ω ∈ (0,1], PT_n(ω) = (1+s(ω))/2, where s(ω) = mω^2 + (1−mω)^2 and m = ⌊1/ω⌋. The proof consists of a matching lower bound via a bipartite state whose Schmidt spectrum is the capped-simplex optimizer, and an upper bound by induction that uses a first-SWAP reduction retaining all diagonal Schmidt branches, a branch-overlap constraint, and a capped refinement inequality. The result recovers the known ω ≥ 1/2 branch, resolves the low-overlap regime including the limit PT_n(ω)→1/2 as ω→0, and improves the one-shot soundness parameter in the Harrow–Montanaro QMA(k)→QMA(2) reduction from 1−(1−σ)^2/100 to 1−(1−σ)^2/4.

Significance. If the result holds, it resolves open problems posed by Soleimanifar–Wright (SODA 2022) and Lovitz–Lowe, showing that the bipartite extremal curve is universal for every number of parties. The proof is elementary, self-contained, and fully rigorous, with explicit extremal states and a sharp linear rejection bound ε/2 for the complexity-theoretic application. The fixed-dimension caveat is explicitly scoped out in Section 8 and does not affect the dimension-free theorem. The paper also gives a clean structural explanation of why the low-overlap regime requires retaining all diagonal branches, and it provides a concrete improvement in a well-studied QMA collapse reduction. Overall this is a significant contribution to quantum property testing and unentangled quantum proofs.

minor comments (3)
  1. [§6, Proof of Proposition 6.1] When Lemma 3.4 is invoked to conclude Σ_i λ_i^2 s(φ_i) ≤ s(ω), the text is mathematically correct but terse: the lemma is applied with weights w_i = λ_i and α_i = φ_i, using Σ_i λ_i = 1 and λ_i φ_i ≤ ω from Lemma 5.3. It would help the reader to state this explicitly.
  2. [§7, Eq. (7.5)] Equation (7.5) is stated as the two-state analogue of Lemma 2.3 without derivation. A one-line expansion of the accepting projector Π_Prod,k = 2^{−k} Σ_S SWAP_S would make the section self-contained.
  3. [References / §1.5] The in-text citation for the survey by Jeronimo, Leigh, and Wu appears as '[JL W26]' with an extra space, and the bibliography entry has a similar spacing issue in the label. This is a minor formatting glitch.

Circularity Check

0 steps flagged

No significant circularity: exact formula is derived from an independent capped-simplex optimization plus a self-contained inductive upper bound; the fixed-dimension caveat is explicitly scoped.

full rationale

The central claim is the exact formula PT_n(ω) = (1+s(ω))/2. The quantity s(ω) is defined independently in Definition 3.1 and Lemma 3.2 as a classical optimization over probability vectors capped by ω, solved in closed form as mω²+(1−mω)²; it is not defined in terms of the product test. The lower bound, Proposition 4.1, explicitly constructs a bipartite state whose squared Schmidt coefficients are the capped optimizer, and Lemma 2.6 (proved in the paper from the SWAP expansion) computes PT2 = (1+Σλ_j²)/2 and Overlap2 = max_j λ_j. Thus the lower bound is a direct computation, not a fitted parameter or renamed prediction. The upper bound, Proposition 6.1, is an induction: Lemma 5.1 gives the first-SWAP reduction, where the only lossy step is bounding off-diagonal branches by 1; Lemma 5.3 derives the branch constraint λ_i ϕ_i ≤ ω from the definition of Overlap_n; and Lemma 3.4 is a standalone inequality showing that subdividing masses cannot beat the global cap s(ω). No step assumes the theorem being proved, and no parameter is fitted to acceptance data. Prior results by SW22, LL26, and HM13 are used as context or comparison, not as load-bearing justifications; the known ω≥1/2 branch is recovered rather than assumed. Section 8 explicitly flags the fixed-dimension limitation: the upper bound remains valid verbatim, while the matching lower-bound construction may require local dimension about 1/ω. That is a scope caveat, not a circular step. There is no renaming of a known result, no ansatz imported via self-citation, and no uniqueness theorem invoked from the authors' own prior work. The manuscript even records its use of AI assistants, which is unrelated to the mathematical derivation. Accordingly, no circular step is present.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

No free parameters are fitted; the only quantities are the input overlap ω and the derived m and r. The proof relies on standard quantum-information axioms and one cited continuity estimate, with no ad hoc postulates or invented mediators.

axioms (5)
  • domain assumption Finite-dimensional Hilbert spaces over C, pure state inputs, and arbitrary but finite local dimensions (Section 2).
    The theorem is stated and proved in this finite-dimensional setting; compactness of the product-state set and Schmidt decomposition are used throughout.
  • standard math Standard swap-trick identities and the purity formula for the product test (Lemma 2.3, Lemma 2.6).
    Elementary linear algebra expressing acceptance probabilities and product overlap in terms of reduced density matrices and Schmidt coefficients.
  • standard math Haar-measure integral representation of the symmetric-subspace projector on two copies (Section 7).
    Used to show the product-test accepting operator is separable across the two Merlin registers; a standard result in representation theory of the symmetric group.
  • standard math Convexity and extreme-point reduction to pure messages in the two-Merlin soundness analysis (Section 7).
    The total acceptance probability is separately convex in each Merlin message, so maximization over mixed strategies reduces to pure states.
  • domain assumption Continuity bound: a measurement on a pure state changes by at most about √ε when the state has product overlap 1 − ε (Section 7, citing HM13 Lemma 22).
    This cited standard estimate is used to bound the original k-Merlin verification branch on non-product inputs; it is external but standard in the QMA(2) literature.

pith-pipeline@v1.3.0-alltime-deepseek · 15508 in / 31226 out tokens · 258063 ms · 2026-08-01T07:20:40.610792+00:00 · methodology

0 comments
read the original abstract

Product testing, i.e., deciding whether a pure multipartite quantum state is fully unentangled across a specified tensor decomposition, serves as a bridge between quantum property testing, unentangled quantum proof systems, and tensor optimization. Despite being a fundamental property testing task and having many applications, the product test's exact (worst-case) acceptance probability curve has yet to be fully determined. In this work, we determine this curve exactly. Let $\omega$ be the maximum squared overlap of the input with a product state, and let $\mathrm{PT}_n(\omega)$ be the largest possible acceptance probability of the product test over all $n$-partite pure states with product overlap $\omega$, allowing arbitrary finite local dimensions. We prove that, for every $n\ge 2 $ and every $\omega\in(0,1] $, $$ \mathrm{PT}_n(\omega)=\frac12\left(1+m\omega^2+(1-m\omega)^2\right), $$ where $m=\lfloor1/\omega\rfloor $. The formula recovers the previously known tight section of the curve for $\omega\ge 1/2 $, resolves all low-overlap regimes $\omega<1/2 $, and implies $\mathrm{PT}_n(\omega)\to 1/2 $ as $\omega\to 0$ answering an open problem in [Soleimanifar and Wright, SODA 2022]. As a complexity-theoretic application, our results improve the one-shot soundness parameter in the Harrow-Montanaro reduction from $\mathsf{QMA}(k)$ to $\mathsf{QMA}(2)$. Our techniques, built upon those of Soleimanifar and Wright, allow us to resolve these open questions while remaining surprisingly elementary.

Figures

Figures reproduced from arXiv: 2607.21477 by Fernando Granha Jeronimo, Jacob Beckey, Pei Wu.

Figure 1
Figure 1. Figure 1: The product test. Given two copies of the same multipartite state, the product test performs a SWAP test on each pair of corresponding registers, and accepts only if all individual tests accept. Although the measurements act independently on each subsystem pair, the overall acceptance probability detects the global failure of product structure. [SW22]. Their inductive argument gave a simpler proof of the s… view at source ↗
Figure 2
Figure 2. Figure 2: Exact product-test acceptance curve for every n. It shows that the curve of the bipartite case, n = 2, of Lovitz and Lowe [LL26] is extremal for every n ≥ 2. Compared with the two previous envelopes from [SW22, [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The capped-simplex optimizer. Under the cap pj ≤ ω, collision probability is maximized by concentrating mass as much as the cap permits: fill m = ⌊1/ω⌋ entries to height ω, then put the residual mass r = 1 − mω on one final entry. Lemma 3.2 (Capped-simplex optimizer). Let ω ∈ (0, 1], set m = ⌊1/ω⌋, and set r = 1 − mω. Then s(ω) = mω2 + r 2 . The value is achieved by the vector (ω, . . . , ω, r), with m cop… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 19 linked inside Pith

  1. [3]

    [BCWdW01] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf

    arXiv:2510.07820. [BCWdW01] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum fingerprinting. Physical Review Letters, 87:167902,

    Pith/arXiv arXiv

  2. [6]

    [BH16] Fernando G

    arXiv:2410.12706. [BH16] Fernando G. S. L. Brand˜ ao and Aram W. Harrow. Product-state approximations to quantum states.Communications in Mathematical Physics, 342(1):47–80,

    Pith/arXiv arXiv

  3. [14]

    [LL26] Benjamin Lovitz and Angus Lowe

    arXiv:2406.16827. [LL26] Benjamin Lovitz and Angus Lowe. Nearly Tight Bounds for Testing Tree Tensor Network States. IEEE Transactions on Information Theory, 72(5):3074–3097, May

    Pith/arXiv arXiv

  4. [18]

    [OW15] Ryan O’Donnell and John Wright

    arXiv:1310.2035. [OW15] Ryan O’Donnell and John Wright. Quantum spectrum testing. InProceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, pages 529–538,

    Pith/arXiv arXiv 2035

  5. [19]

    [Raz08] Alexander A

    arXiv:1501.05028. [Raz08] Alexander A. Razborov. On the minimal density of triangles in graphs.Combinatorics, Probability and Computing, 17(4):603–618,

    Pith/arXiv arXiv

  6. [22]

    [Yu20] Nengkun Yu

    arXiv:quant- ph/0307219. [Yu20] Nengkun Yu. Sample optimal quantum identity testing via Pauli measurements,

    arXiv

  7. [1997]

    [BBK+25] Ainesh Bakshi, John Bostanci, William Kretschmer, Zeph Landau, Jerry Li, Allen Liu, Ryan O’Donnell, and Ewin Tang

    arXiv:quant-ph/9604028. [BBK+25] Ainesh Bakshi, John Bostanci, William Kretschmer, Zeph Landau, Jerry Li, Allen Liu, Ryan O’Donnell, and Ewin Tang. Learning the closest product state. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25,

    Pith/arXiv arXiv

  8. [2001]

    [BGCC21] Jacob L

    arXiv:quant-ph/0102001. [BGCC21] Jacob L. Beckey, N. Gigena, Patrick J. Coles, and M. Cerezo. Computable and operationally meaningful multipartite entanglement measures.Physical Review Letters, 127:140501,

    Pith/arXiv arXiv

  9. [2002]

    [Has07] Matthew B

    arXiv:quant-ph/0203016. [Has07] Matthew B. Hastings. An area law for one-dimensional quantum systems.Journal of Statistical Mechanics: Theory and Experiment, 2007:P08024,

    Pith/arXiv arXiv 2007

  10. [2003]

    [CWZ24] Kean Chen, Qisheng Wang, and Zhicheng Zhang

    arXiv:quant-ph/0305094. [CWZ24] Kean Chen, Qisheng Wang, and Zhicheng Zhang. Local test for unitarily invariant properties of bipartite quantum states,

    Pith/arXiv arXiv

  11. [2005]

    [MdW16] Ashley Montanaro and Ronald de Wolf

    arXiv:quant-ph/0505162. [MdW16] Ashley Montanaro and Ronald de Wolf. A survey of quantum property testing.Theory of Computing Graduate Surveys, 7:1–81,

    Pith/arXiv arXiv

  12. [2007]

    [HLM17] Aram W

    arXiv:0705.2024. [HLM17] Aram W. Harrow, Cedric Yen-Yu Lin, and Ashley Montanaro. Sequential measurements, disturbance and property testing. InProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1598–1611. SIAM,

    Pith/arXiv arXiv 2024

  13. [2008]

    Testing matrix product states

    [SW22] Mehdi Soleimanifar and John Wright. Testing matrix product states. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1679–1701. SIAM,

    2022

  14. [2013]

    [JL W26] Fernando Granha Jeronimo, Itai Leigh, and Pei Wu

    arXiv:1001.0017. [JL W26] Fernando Granha Jeronimo, Itai Leigh, and Pei Wu. The QMA(2) universe—complexity, entanglement, and optimization.ACM SIGACT News, 57(1):64–99,

    Pith/arXiv arXiv

  15. [2015]

    [MCKB05] Florian Mintert, Andr´ e R

    arXiv:1307.5143. [MCKB05] Florian Mintert, Andr´ e R. R. Carvalho, Marek Ku´ s, and Andreas Buchleitner. Measures and dynamics of entangled states.Physics Reports, 415(4):207–259,

    Pith/arXiv arXiv

  16. [2016]

    19 [Bre03] Gavin K

    arXiv:1310.0017. 19 [Bre03] Gavin K. Brennen. An observable measure of entanglement for pure states of multi-qubit systems.Quantum Information and Computation, 3(6):619–626,

    Pith/arXiv arXiv

  17. [2017]

    [HM13] Aram W

    arXiv:1607.03236. [HM13] Aram W. Harrow and Ashley Montanaro. Testing product states, quantum Merlin-Arthur games and tensor optimisation.Journal of the ACM, 60(1):3:1–3:43,

    Pith/arXiv arXiv

  18. [2020]

    arXiv:2009.11518. 20

    Pith/arXiv arXiv 2009

  19. [2021]

    [BGTW25] Adam Bouland, Tudor Giurgic˘ a-Tiron, and John Wright

    arXiv:2104.06923. [BGTW25] Adam Bouland, Tudor Giurgic˘ a-Tiron, and John Wright. The state hidden subgroup problem and an efficient algorithm for locating unentanglement. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25,

    Pith/arXiv arXiv

  20. [2022]

    [WG03] Tzu-Chieh Wei and Paul M

    arXiv:2201.01824. [WG03] Tzu-Chieh Wei and Paul M. Goldbart. Geometric measure of entanglement and applications to bipartite and multipartite quantum states.Physical Review A, 68:042307,

    Pith/arXiv arXiv

  21. [2024]

    [EAO+02] Artur K

    arXiv:2404.04599. [EAO+02] Artur K. Ekert, Carolina Moura Alves, Daniel K. L. Oi, Micha l Horodecki, Pawe l Horodecki, and L. C. Kwek. Direct Estimations of Linear and Nonlinear Functionals of a Quantum State. Physical Review Letters, 88(21):217901, May

    Pith/arXiv arXiv

  22. [2025]

    [BCS+25] Jacob Beckey, Luke Coffman, Ariel Shlosberg, Louis Schatzki, and Felix Leditzky

    arXiv:2411.04283. [BCS+25] Jacob Beckey, Luke Coffman, Ariel Shlosberg, Louis Schatzki, and Felix Leditzky. Product testing with single-copy measurements,

    arXiv

  23. [2026]

    [L VV15] Zeph Landau, Umesh Vazirani, and Thomas Vidick

    arXiv:2410.21417. [L VV15] Zeph Landau, Umesh Vazirani, and Thomas Vidick. A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians.Nature Physics, 11:566–569,

    arXiv