REVIEW 3 major objections 4 minor 1 cited by
Sample optimal Quantum identity testing via Pauli Measurements
T0 review · 3 major / 4 minor · reviewed 2026-08-27 · deepseek-v4-flash
Pith's one-line read This paper proves that the sample complexity of quantum identity testing using two-outcome Pauli measurements is Θ(poly(n)·4^n/ε²), with an explicit O(n^4·4^n/ε²) algorithm and a matching Ω(4^n/ε²) lower bound for the maximally mixed case.
desk verdict The upper bound is solid and the claimed Θ(poly(n)4^n/ε²) is likely correct, but the lower-bound proof as written is a two-sentence sketch and needs a real minimax argument. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The carrying object is the expansion of an n-qubit state ρ = Σ_P α_P P / 2^n in the Pauli basis, together with the reduction from quantum identity testing to identity testing of a collection of 4^n binary distributions in a query model. Each two-outcome Pauli measurement along a tensor-product Pauli operator P yields a sample from a binary distribution p_P whose parameter is (1+α_P)/2; the trace-distance hypothesis implies Σ_P (α_P−β_P)^2 ≥ ε², so the problem becomes deciding whether all 4^n binary distributions are equal or have average squared 2-norm distance above ε²/(2·4^n). The query-model algorithm for collections of distributions—which samples indices at exponentially growing scales and runs a binary tester at each scale—does the heavy lifting and gives the O($n^{4}$·4^n/ε²) upper bound.
What would settle it
Construct an explicit adaptive Pauli-measurement strategy that distinguishes the maximally mixed state from the uniform mixture of the states σ_P = (I+εP)/2^n using o(4^n/ε²) copies; if such a strategy exists, the claimed Θ(4^n/ε²) lower bound is false. Conversely, a careful minimax lower-bound proof for adaptivity would confirm the paper's assertion.
Extended reading notes
Core claim
The paper's central claim is Theorem 1: using two-outcome Pauli measurements, the sample complexity of the quantum identity testing problem is Θ(poly(n)·4^n/ε²). The upper bound works by expanding both states in the n-qubit Pauli basis, so a Pauli measurement on a chosen tensor-product basis element produces a binary distribution whose squared 2-norm distance equals the squared difference of the corresponding Pauli coefficients. Identity testing of the two quantum states then reduces to identity testing of a collection of 4^n binary distributions in a query model, which the paper solves with O($log^{4}$ m / ε²) samples for m = 4^n, i.e., O($n^{4}$·4^n/ε²). The lower bound restricts to mixedness testing (σ equal to the maximally mixed state) and constructs an ensemble of states σ_P = (I + εP)/2^n for each n-qubit Pauli P; distinguishing this ensemble from the maximally mixed state, it argues, needs about 1/ε² copies per basis and hence Ω(4^n/ε²) copies overall, with the assertion that adaptivity in choosing Pauli measurements does not help.
Load-bearing premise
The lower bound rests on the assertion, stated without a full minimax proof, that an adaptive strategy for choosing which Pauli measurement to perform offers no advantage, so that distinguishing the hidden state σ_P from the maximally mixed state forces a search over all 4^n Pauli bases at a cost of about 1/ε² copies per basis.
Editorial extensions
If this is right
- Any two-outcome Pauli measurement scheme for quantum identity testing, even adaptive, must use Ω(4^n/ε²) copies when σ is maximally mixed, so the exponential dependence on n is not an artifact of the particular algorithm.
- The upper-bound reduction shows that quantum identity testing under Pauli measurements is essentially equivalent to identity testing of 4^n binary distributions in a query model; any later improvement to the distribution-collection tester would immediately improve the poly(n) factor in the quantum sample complexity.
- For n qubits, the sample complexity is Θ(4^n/ε²) up to polynomial factors, in contrast to the joint-measurement setting where Θ(d/ε²) = Θ(2^n/ε²) copies suffice with entangled measurements; thus restricting to Pauli measurements costs an extra factor exponential in n.
- The lower bound applies even to the special mixedness problem of deciding whether an unknown state is the maximally mixed state or ε-far from it, so testing uniformity of a quantum state already requires Ω(4^n/ε²) samples under two-outcome Pauli measurements.
Reading between the lines
- A natural next step is to test whether a constant number of n-qubit random Clifford measurements, which are single-shot but high-outcome measurements, could beat the 4^n barrier; the paper's lower-bound construction targets two-outcome Pauli measurements specifically, so the tightness may not extend to all Pauli-based schemes with more than two outcomes per measurement.
- The assertion that adaptive Pauli choices give no advantage is the least formalised step; if a minimax proof were supplied, the lower bound would be on much firmer footing, and the same technique might yield tight bounds for other Pauli-restricted property testing problems.
- The query-model algorithm for collections of distributions is generic; the same reduction could give sample-optimal tests for other properties expressed in the Pauli basis, such as estimating Pauli expectation values or testing entanglement witnesses, whenever the property is a function of the 4^n coefficients.
- The result suggests a practical benchmark: for moderate n, the number of copies is around 4^n/ε², so the regime where identity testing is feasible under Pauli measurements is limited; this quantifies a hardware-oriented intuition that non-Pauli or joint measurements are necessary for scalable quantum certification.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies quantum identity testing: given copies of two unknown n-qubit states ρ and σ, decide whether ρ = σ or they are ε-far in trace distance, under the restriction that each copy is measured by a two-outcome Pauli measurement. The main result, Theorem 1, claims that the sample complexity of this task is Θ(poly(n)·4^n/ε²). The upper bound is obtained by expanding ρ and σ in the Pauli basis and reducing the problem to identity testing of a collection of m = 4^n binary distributions, one for each Pauli basis. The paper argues that when ||ρ−σ||_1 > ε, the average squared ℓ2-distance of these binary distributions is at least ε²/(2·4^n), and then applies a known collection tester with sample complexity O(log^4 m / ε'^2), yielding O(n^4·4^n/ε²). The lower bound considers the special case of testing against the maximally mixed state, defines σ_P = (I + εP)/2^n, asserts that Ω(1/ε²) copies are needed for each known P, and concludes without proof that Ω(4^n/ε²) copies are needed when P is unknown, stating that adaptivity gives no advantage.
Significance. If the tight bound is established, the paper resolves the sample complexity of quantum identity testing under two-outcome Pauli measurements, a practically motivated restricted measurement model. The upper bound is a genuinely parameter-free reduction: it relies on external collection-testing results and contains no fitted constants, and the sample count O(n^4·4^n/ε²) follows cleanly from the analysis. The claimed lower bound would show an exponential separation from entangled-measurement protocols, which is an interesting and nontrivial statement. The main weakness is that the lower bound is asserted rather than proved; the per-basis Ω(1/ε²) statement does not automatically imply the claimed Ω(4^n/ε²) without a minimax or information-theoretic argument ruling out adaptive search. The theorem may well be true, and the upper bound is solid, but the central tightness claim is not established by the text as written.
major comments (3)
- [Lower bound] The step from the per-basis bound to the global bound is not proved. The text states: 'Of course, to distinguish σ_P from I/2^n, at least 1/ε² copies are needed to be measured in Pauli measurement corresponding to P. Therefore, to distinguish I/2^n from the uniform distribution over σ_Ps, we need at least (4m−1)1/ε² copies. Adaptively chosen Pauli measurement would not provide any advantage here.' The first statement applies when the basis P is known; the second assumes without argument that an unknown P forces the algorithm to effectively test all 4^n bases. A legitimate adaptive strategy could spend a few samples on many bases to screen candidates and then concentrate on promising ones, so a lower bound must rule out such strategies via a minimax, Yao, or Le Cam argument. This gap is load-bearing: without it, the Ω(4^n/ε²) lower bound in Theorem 1 is unsupported.
- [Lower bound] The family σ_P includes P = σ_I, the identity Pauli. For P = σ_I, σ_P = (I + εI)/2^n has trace (1+ε)/2^n · 2^n = 1+ε, so it is not a valid density matrix. The family should be restricted to P ≠ I, giving 4^n − 1 states. Additionally, the manuscript writes '(4m−1)' with m = 4^n, which equals 4^{n+1} − 1 rather than 4^n − 1. These are repairable, but they indicate that the lower-bound section is not carefully formulated.
- [Observation 1] Observation 1 states that the sample complexity is Θ(log(1−δ)/ε²). For δ ∈ (0,1), log(1−δ) is negative, so the stated complexity is meaningless; the intended expression is almost certainly Θ(log(1/δ)/ε²). Since this observation underlies the failure-probability budget of the collection-testing algorithm, it should be corrected in the formal statement.
minor comments (4)
- [Introduction] There are several typographical errors: 'empolys' should be 'employs', 'sufficient and sufficient' should be 'necessary and sufficient', and the notation 'Θ(d1,2)' is unclear.
- [Upper bound] In the displayed inequality for the collection tester, the upper limit of the summation over k is missing; it should be k = 0 to ⌈log2 m⌉ to match the algorithm's loop.
- [Upper bound] The reduction from quantum states to distribution collections uses the inequality ||ρ−σ||_2² ≥ ||ρ−σ||_1²/2^n. This is correct, but the intervening derivation of ∑_P(α_P−β_P)² ≥ ε² is compressed and would benefit from one explanatory sentence.
- [Lower bound] The phrase 'quantum mixedness testing problem' is used to describe testing against the maximally mixed state; the term 'mixedness' is nonstandard and could be replaced with 'state mixedness' or 'uniformity testing against the maximally mixed state' for clarity.
Circularity Check
No significant circularity: the upper bound is a genuine reduction to external distribution-collection testing, and the lower bound, while having a proof gap, is not circular.
full rationale
The paper's main theorem is not derived from its own conclusion by construction. The upper bound maps Pauli expectation coefficients to binary distributions and invokes an external distribution-collection tester from [16,24]; no parameter is fitted to the target quantity, and the sample complexity O(n^4·4^n/ε²) follows from standard reduction arithmetic rather than from an assumed form of the answer. The lower bound defines a family σ_P = (I+εP)/2^n and argues that distinguishing each σ_P from the maximally mixed state requires 1/ε² samples in the matching Pauli basis, then concludes Ω(4^n/ε²) samples are needed overall. This transition contains an unproved assertion about adaptivity ('Adaptively chosen Pauli measurement would not provide any advantage here'), and the paper even includes an invalid member P=σ_I whose trace exceeds 1. These are correctness/rigor gaps in the lower-bound proof, not circularity: the lower bound does not assume the Θ(4^n/ε²) complexity it is trying to prove, nor does it reduce by its own equations to an earlier published result. The self-citations [22] and [25] are contextual: [22] is an independent measurement scheme cited only as background, and [25] is invoked for a side remark about an alternative 2^n-outcome Pauli measurement model, not for the load-bearing Ω(4^n/ε²) claim. Observation 1 is a standard external fact. Consequently, no fitted input is renamed as a prediction and no load-bearing premise is justified solely by self-citation; the appropriate finding is no significant circularity.
Assumptions & free parameters
assumptions (3)
- domain assumption Standard Pauli expansion of n-qubit states: ρ = Σ_P α_P P / 2^n with α_P = Tr(Pρ).
- standard math Binary distribution identity testing sample complexity Θ(log(1/δ)/ε²).
- domain assumption The minimax lower bound argument for the uniform mixture of σ_P states.
Cite this review
Pith. "Pith review of Sample optimal Quantum identity testing via Pauli Measurements." pith.science (2026). https://pith.science/paper/ODIKIG44
@misc{pith2026200911518,
author = {Pith},
title = {Pith review of: Sample optimal Quantum identity testing via Pauli Measurements},
year = {2026},
howpublished = {\url{https://pith.science/paper/ODIKIG44}},
note = {Machine review of arXiv:2009.11518}
}
abstract
In this paper, we show that $\Theta(\mathrm{poly}(n)\cdot\frac{4^n}{\epsilon^2})$ is the sample complexity of testing whether two $n$-qubit quantum states $\rho$ and $\sigma$ are identical or $\epsilon$-far in trace distance using two-outcome Pauli measurements.
Forward citations
Cited by 1 Pith paper
-
An Optimal Analysis of the Product Test
For every n >= 2, the product test's worst-case acceptance probability equals (1 + mω^2 + (1−mω)^2)/2 with m = floor(1/ω), where ω is the maximum squared overlap with a product state.
Reference graph
Works this paper leans on
-
[1]
A survey of quantum property testing,
A. Montanaro and R. de Wolf, “A survey of quantum property testing,” Theory of Computing Graduate Surveys 7 (2016)
work page 2016
-
[2]
Quantum state tomography via compressed sensing,
D. Gross, Y. Liu, S. T. Flammia, S. Becker, and J. Eisert, “Quantum state tomography via compressed sensing,” Phys. Rev. Lett. 105 (2010)
work page 2010
-
[3]
Quantum tomography via compressed sensing: Error bounds, sample complexity, and efficient estimators,
S. T. Flammia, D. Gross, Y. Liu, and J. Eisert, “Quantum tomography via compressed sensing: Error bounds, sample complexity, and efficient estimators,” New J. Phys. 14, 095022 (2012)
work page 2012
-
[4]
Quantum Tomography From Few Full-Rank Observables
V. Voroninski, “Quantum tomography from few full-rank observables,” (2013), 1309.7669
work page Pith review arXiv 2013
-
[5]
Low rank matrix recovery from rank one measurements,
R. Kueng, H. Rauhut, and U. Terstiege, “Low rank matrix recovery from rank one measurements,” Applied and Compu- tational Harmonic Analysis 42, 88–116 (2017)
work page 2017
-
[6]
Sample-optimal tomography of quantum states,
J. Haah, A. W. Harrow, Z. Ji, X. Wu, , and N. Yu, “Sample-optimal tomography of quantum states,” in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing , STOC ’16 (2016) pp. 913–925
work page 2016
-
[7]
R. O’Donnell and J. Wright, “Efficient quantum tomography,” in Proceedings of the Forty-Seventh Annual ACM on Sym- posium on Theory of Computing , STOC ’16 (2016) pp. 899–912
work page 2016
-
[8]
Efficient quantum tomography ii,
R. O’Donnell and J. Wright, “Efficient quantum tomography ii,” in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing , STOC ’17 (2017) pp. 962–974
work page 2017
Show all 25 references
-
[9]
Testing that distributions are close,
T. Batu, L. Fortnow, R. Rubinfeld, W. D. Smith, and P. White, “Testing that distributions are close,” in Proceedings 41st Annual Symposium on Foundations of Computer Science , FOCS’00 (2000) pp. 259–269
2000
-
[10]
Testing random variables for independence and identity,
T. Batu, L. Fortnow, E. Fischer, R. Kumar, R. Rubinfeld, and P. White, “Testing random variables for independence and identity,” in Proceedings of the 42Nd IEEE Symposium on Foundations of Computer Science , FOCS ’01 (2001) pp. 442–451
2001
-
[11]
Goldreich and D
O. Goldreich and D. Ron, On Testing Expansion in Bounded-Degree Graphs , Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, Lecture Notes in Computer Science, Vol. 6650 (Springer, 2000)
2000
-
[12]
A coincidence-based test for uniformity given very sparsely sampled discrete data,
L. Paninski, “A coincidence-based test for uniformity given very sparsely sampled discrete data,” IEEE Trans. Inf. Theor. 54, 4750–4755 (2008)
2008
-
[13]
Estimating the unseen: An n/log(n)-sample estimator for entropy and support size, shown optimal via new clts,
G. Valiant and P. Valiant, “Estimating the unseen: An n/log(n)-sample estimator for entropy and support size, shown optimal via new clts,” in Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing , STOC ’11 (2011) pp. 685–694
2011
-
[14]
An automatic inequality prover and instance optimal identity testing,
G. Valiant and P. Valiant, “An automatic inequality prover and instance optimal identity testing,” in Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science , FOCS ’14 (2014) pp. 51–60
2014
-
[15]
Optimal algorithms for testing closeness of discrete distributions,
S. Chan, I. Diakonikolas, G. Valiant, and P. Valiant, “Optimal algorithms for testing closeness of discrete distributions,” in Proceedings of the Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA ’14 (2014) pp. 1193–1203
2014
-
[16]
A new approach for testing properties of discrete distributions,
I. Diakonikolas and D. Kane, “A new approach for testing properties of discrete distributions,” in 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) (2016) pp. 685–694
2016
-
[17]
Direct fidelity estimation from few pauli measurements,
Steven T. Flammia and Yi-Kai Liu, “Direct fidelity estimation from few pauli measurements,” Phys. Rev. Lett. 106, 230501 (2011)
2011
-
[18]
Practical characterization of quantum devices without tomography,
Marcus P. da Silva, Olivier Landon-Cardinal, and David Poulin, “Practical characterization of quantum devices without tomography,” Phys. Rev. Lett. 107, 210404 (2011)
2011
-
[19]
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 (2015)
2015
-
[20]
Quantum spectrum testing,
R. O’Donnell and J. Wright, “Quantum spectrum testing,” inProceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing , STOC ’15 (2015) pp. 529–538
2015
-
[21]
Quantum state certification,
C. B˘ adescu, R. O’Donnell, and J. Wright, “Quantum state certification,” inProceedings of the Forty-Nineth Annual ACM on Symposium on Theory of Computing , STOC ’19 (2019)
2019
-
[22]
Quantum closeness testing: A streaming algorithm and applications,
Nengkun Yu, “Quantum closeness testing: A streaming algorithm and applications,” (2019), arXiv:1904.03218 [quant-ph]
2019 arXiv
-
[23]
Entanglement is necessary for optimal quantum property testing,
Sebastien Bubeck, Sitan Chen, and Jerry Li, “Entanglement is necessary for optimal quantum property testing,” (2020), arXiv:2004.07869 [quant-ph]. 6
2020 arXiv
-
[24]
Testing properties of collections of distributions,
R. Levi, D. Ron, and R. Rubinfeld, “Testing properties of collections of distributions,” Theory of Computing 9, 295–347 (2013)
2013
-
[25]
Sample efficient tomography via pauli measurements,
Nengkun Yu, “Sample efficient tomography via pauli measurements,” (2020), arXiv:2009.04610 [quant-ph]
2020 arXiv
Reviewed August 27, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.