Instance-Optimal Quantum State Certification with Entangled Measurements

Chirag Wadhwa; Ryan O'Donnell

REVIEW 3 major objections 3 minor 1 cited by

Instance-Optimal Quantum State Certification with Entangled Measurements

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

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

Pith's one-line read A single norm of the hypothesis state fixes quantum certification's copy cost.

desk verdict New lower-bound technique is real, but the paper's central near-optimality claim fails because the two sigma* definitions aren't comparable; the gap is 1/epsilon^2, not a log factor. read the letter →

arxiv 2507.06010 v1 pith:EK3THGEK submitted 2025-07-08 quant-ph cs.DScs.LG

Ryan O'Donnell , Chirag Wadhwa This is my paper

classification quant-phcs.DScs.LG MSC 81P6868Q12 PACS 03.67.-a

keywords quantumstatecertificationcopycomplexityfullyentangledmeasurementsinstance-optimalboundsSchatten1/2-quasinormχ²-divergenceIngster–Suslinamethodmixednesstesting

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 proves nearly instance-optimal bounds for quantum state certification with fully entangled measurements: up to polylog factors, the copy complexity for a hypothesis state $\sigma$ is $\|\sigma^*\|_{1/2}/\epsilon^2$, where $\sigma^*$ is $\sigma$ with a small amount of eigenvalue mass removed and $\|\cdot\|_{1/2}$ is the Schatten $1/2$-quasinorm. This is the first instance-dependent characterization for unrestricted testers and it makes concrete how difficulty interpolates from pure states ($O(1/\epsilon^2)$ copies) to the maximally mixed state ($\Theta(d/\epsilon^2)$ copies). The lower bounds run through a new quantum analogue of the Ingster–Suslina method that computes quantum $\chi^2$-divergences against Haar-random alternative states and uses concentration of measure for random unitary matrices. The same method gives a short proof of the $\Omega(d/\epsilon^2)$ mixedness-testing lower bound, previously obtained with heavier representation theory.

What carries the argument

The engine is a quantum analogue of the Ingster–Suslina method, built on the quantum $\chi^2$-divergence $D_{\chi^2}(\rho\|\sigma) = \operatorname{tr}(\sigma^{-1}(\rho-\sigma)^2)$ (Definition 3.1). For a random family of alternative states $\rho_\theta$ with $\mathbb{E}_\theta\rho_\theta=\sigma$, Lemma 4.3 computes $$D_{\$chi^{2}$}(\mathbb{E}_\$\theta$\rho_\$theta^{{\otimes n}}$\|\$sigma^{{\otimes n}}$) = \mathbb{E}_{\$\theta$,\$\theta$'}\operatorname{tr}(\$sigma^{{-1}}$\rho_\$\theta$\rho_{\$\theta$'})^n - 1 = \mathbb{E}_{\$\theta$,\$\theta$'}(1 + \operatorname{tr}(\$sigma^{{-1}}$(\rho_\$\theta$-\$\sigma$)(\rho_{\$\theta$'}-\$\sigma$)))^n - 1 \le \mathbb{E}_{\$\theta$,\$\theta$'}\exp(n\operatorname{tr}(\$sigma^{{-1}}$(\rho_\$\theta$-\$\sigma$)(\rho_{\$\theta$'}-\$\sigma$))) - 1.$$ The inner trace is a mean-zero polynomial in Haar-random unitary matrices, and Lemma 3.8 bounds its exponential moment by $\exp(48n^2\|\sigma^{-1}\|_2^2\delta^4/d)$ whenever the perturbation has operator norm at most $\delta$. General states are handled by bucketing eigenvalues into constant-multiplicative ranges, removing a small tail, and independently perturbing each bucket with a traceless unitary conjugation, so the divergence factorizes into a product of per-bucket bounds; a corner case with a principal eigenvalue at least $1/2$ is treated by rotating the top two eigenvectors or using a random $2\times2$ perturbation. The upper bound reuses the same bucketing and tests the three ways $\rho$ can be far from $\sigma$ (heavy tail, diagonal-block deviation, off-diagonal deviation) using the entangled Hilbert–Schmidt tester.

What would settle it

Verify Lemma 6.6 by a search over small-dimensional states: any pair $\rho,\sigma$ with $\|\rho-\sigma\|_1\ge\epsilon$ that falls into none of the three listed cases is an explicit counterexample to the upper-bound algorithm. Alternatively, for a concrete small case such as $d=2$, $\sigma=\operatorname{diag}(0.9,0.1)$, $\epsilon=0.1$, and a traceless perturbation of operator norm $0.02$, Monte-Carlo evaluate the exponential-moment inequality in Lemma 4.5 at the claimed cutoff; the inequality either holds or fails there, settling the lower-bound step.

Watch

Extended reading notes

Core claim

The paper's central claim is that the optimal copy complexity of $\epsilon$-certifying $\sigma$ with entangled measurements is $\tilde{\Theta}(\|\sigma^*\|_{1/2}/\epsilon^2)$, where $\sigma^*$ is $\sigma$ with eigenvalues of total mass $O(\epsilon)$ zeroed out (lower bound) or $O(\epsilon^2)$ zeroed out (upper bound) and then normalized. In fidelity language this is $\tilde{\Theta}(d\cdot F(\sigma^*, I/d)/\epsilon^2)$, making it the quantum counterpart of the classical instance-optimal identity-testing formula. The lower bound (Theorem 5.1) holds for all $\epsilon<1/12$ up to log factors and is built from block-diagonal perturbations of eigenvalue buckets, with a separate corner-case argument for states whose largest eigenvalue exceeds $1/2$. The upper bound (Theorem 6.1) is obtained by substituting an entangled Hilbert–Schmidt tester into the unentangled instance-optimal algorithm and testing separately for excess tail mass, diagonal-block deviations, and off-diagonal deviations. The authors state that the bounds are optimal in both extremes: $\Theta(1/\epsilon^2)$ for pure states and, up to log factors, $\Theta(d/\epsilon^2)$ for the maximally mixed state.

Load-bearing premise

The load-bearing premise is that the imported three-case decomposition for how a far state can differ from the hypothesis (Lemma 6.6, inherited from the unentangled algorithm with its constants corrected) is complete and correct, and that the Haar-measure concentration inequality used everywhere (Lemma 3.8, inherited from standard log-Sobolev results) holds with the constants used; if either premise fails, the claimed upper and lower bounds do not follow from the text alone.

Editorial extensions

If this is right

Pure states: no eigenvalue mass is removed and the bound collapses to $\tilde{\Theta}(1/\epsilon^2)$, matching the known simple algorithm.
Maximally mixed state: the bound becomes $\tilde{\Theta}(d/\epsilon^2)$, and Theorem 1.3 removes the log factors, giving a new proof of the optimal $\Omega(d/\epsilon^2)$ lower bound.
A rank-$r$ state with roughly equal eigenvalues needs $\tilde{\Theta}(r/\epsilon^2)$ copies, a factor of $\sqrt{r}$ fewer than the unentangled-measurement regime.
Up to polylog factors, $n=\tilde{\Theta}(d\cdot F(\sigma^*, I/d)/\epsilon^2)$ is the complete characterization for entangled-measurement testers; only constants and log factors remain open.
The block-diagonal perturbation instance alone suffices for the lower bound, so diagonal-block deviations are as costly to test as full certification in the entangled setting.

Reading between the lines

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

Editorial extension: the quantum Ingster–Suslina method should transfer to other state-testing tasks with fully entangled measurements, such as closeness testing or purity estimation, whenever the null state admits unitarily invariant mean-zero perturbations.
The corner case for states with a dominant eigenvalue suggests the sharp constant for near-pure certification may depend on the gap between the two largest eigenvalues of $\sigma$, a dependence the polylog slack currently hides.
Because the upper bound is a subroutine substitution inside the unentangled algorithm, any future improvement to entangled Hilbert–Schmidt testing would automatically improve instance-optimal certification.
A testable extension is to apply the same $\chi^2$ method in the unentangled-measurement model and see whether it reproduces the known $\Omega(d^{3/2}/\epsilon^2)$ mixedness-testing lower bound with simpler constants.

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

Colleague—quick take on arXiv:2507.06010. The lower-bound technique is genuinely new: a quantum analogue of Ingster–Suslina via quantum chi^2, with Haar concentration. It recovers the mixedness-testing lower bound in a few lines and extends cleanly to bucketed states. That's real progress and worth publishing on its own. But the advertised instance-optimal characterization, Theorem 1.2 with its informal matching bounds, doesn't follow from the stated theorems.

The problem is that sigma* in the lower bound (Def 5.2) and sigma* in the upper bound (Def 6.3) are not the same object, and they're not comparable. The lower-bound version removes up to 12epsilon mass, sorting by lambda_i/d_{j(i)}; the upper-bound version removes epsilon^2/20 mass, sorting by lambda_i. The paper flags this difference but never bridges it. The stress-test example is correct: take sigma = diag(1-epsilon, epsilon^4, ..., epsilon^4) with d~epsilon^{-3}. Under the lower-bound removal, all epsilon^4 eigenvalues go into Stail because their total mass is epsilon <= 12epsilon and the normalized values are tiny; the resulting sigma* has ||.||_{1/2} ~ 1, so Thm 5.1 gives only Omega(1/epsilon^2). Under the upper-bound removal, only about 1/(20epsilon^2) of the epsilon^4 entries are zeroed, leaving ||sigma*||_{1/2} ~ 1/epsilon^2, so Thm 6.1 gives O(1/epsilon^4). That's a gap of 1/epsilon^2, and it's robust: projecting onto the retained block needs Omega(1/epsilon^4) copies. So the formal bounds are not instance-optimal for this sigma, and the matching claim is unsupported.

The rest of the paper is in decent shape. The lower-bound algebra in Lemmas 4.3, 4.5, 4.7 checks out; the corner-case lemmas (5.14, 5.15) are fine; the upper-bound algorithm is a straightforward adaptation of CLO22 and BOW19 and is plausibly correct given its imported decomposition. The dependence on [CLO22] is explicit and standard, though not fully self-contained. The citation pattern looks appropriate.

Bottom line: the Ingster–Suslina method is a solid contribution that will be cited; the upper bound is a reasonable algorithm; but the central "nearly instance-optimal" theorem overclaims. A serious referee should ask for a proof that the two sigma* quantities are within polylog factors, or a revised statement that separates the lower and upper bounds. As written, I would not accept without substantial revision. If the comparability can be fixed, this becomes a strong paper. Worth sending to a good venue and letting the authors repair it.

Referee Report

3 major / 3 minor

Summary. The paper studies quantum state certification with fully entangled measurements and claims nearly instance-optimal copy complexity. The proposed characterization is: for any hypothesis state σ, the copy complexity of ε-certifying σ is, up to polylog(d/ε) factors, ∥σ*∥_{1/2}/ε², where σ* is obtained by removing a small amount of eigenvalue mass and ∥·∥_{1/2} is the Schatten 1/2-quasinorm. The lower bound is proved through a new quantum analogue of the Ingster–Suslina method, using Haar-random unitary perturbations of diagonal blocks and concentration of measure; this also yields a new proof of the Ω(d/ε²) mixedness-testing lower bound. The upper bound adapts the bucketing-based algorithm of [CLO22], replacing the unentangled Hilbert–Schmidt tester with the entangled tester of [BOW19].

Significance. If the central matching claim were established, this would resolve the open question of instance-optimal state certification with entangled measurements and would substantially strengthen the known worst-case Θ(d/ε²) bounds. The quantum Ingster–Suslina method is elegant and likely to be of independent interest; in particular, the simple proof of the mixedness-testing lower bound is a genuine contribution. The paper also gives a clean comparison with the unentangled setting, showing that block-diagonal perturbations suffice for the entangled lower bound. However, the advertised near-optimality is not actually supported by the two formal theorems as stated, because the lower- and upper-bound theorems use incompatible mass-removal schemes; this is a load-bearing issue that needs to be resolved before the central claim can be accepted.

major comments (3)

[Theorem 5.1 / Definition 5.2 and Theorem 6.1 / Definition 6.3] The lower and upper bounds use different mass-removal schemes, and the gap between them can be polynomial, not merely polylogarithmic. In Theorem 5.1, Definition 5.2 removes up to 12ε eigenvalue mass, ordering eigenvalues by λ_i/d_{j(i)}; in Theorem 6.1, Definition 6.3 removes only ε²/20 mass, ordering by λ_i. For ε small, set d = ⌈ε^{-3}⌉ and take σ = diag(1−ε, ε^4, …, ε^4) with d−1 trailing eigenvalues ε^4. The total mass of the small eigenvalues is ε, so the lower-bound scheme puts all of them into Stail; hence ∥σ*_lower∥_{1/2} ≈ 1 and Theorem 5.1 gives only Ω~(1/ε²). The upper-bound scheme, by contrast, removes only about 1/(20ε²) of the ε^4 entries, leaving roughly 1/ε mass in the small block; therefore ∥σ*_upper∥_{1/2} ≈ 1/ε² and Theorem 6.1 gives O~(1/ε^4). This is a factor 1/ε² gap, not a polylog factor. Thus Theorems 5.1 and 6.1 do not, as written, imply the informal near-optimal characterization in Theorem 1.2. The lower-bound proof would need to be reworked so that the same mass-removal threshold is used, or the theorems and the main claim need to be weakened accordingly.
[Section 6.2, Lemma 6.6] The upper bound relies on Lemma 6.6, which is imported from [CLO22] and then modified: the paper replaces their threshold .1ε/m² by .05ε/m² and states this corrects a 'minor typo/bug'. Since the three-case decomposition in Lemma 6.6 is the backbone of the upper-bound proof and the authors explicitly say the presentation is not completely self-contained, the reader cannot verify that the claimed decomposition holds with the corrected constants. Given that this lemma is load-bearing for Theorem 6.1, the paper should either state and prove Lemma 6.6 in full, or at least provide a precise appendix proof of the corrected version.
[Section 5.4, Lemma 5.16] The proof of the main lower bound in the corner case uses Lemma 5.16, imported from [CLO22] (their Lemma 5.26), with the note that it is 'not hard' to adapt it to the new bucketing scheme. Because the bucketing and mass-removal scheme in Definition 5.2 differs from that in [CLO22] (different sorting order and different mass removed), the adaptation is not automatic. A complete proof of Lemma 5.16, or a precise derivation for the current scheme, should be included; the lower-bound theorem currently depends on an unverified external lemma at a critical point.

minor comments (3)

[Notation, Theorem 1.2 and footnotes] The symbol σ* is used for two different states: one in Theorem 5.1/Definition 5.2 and one in Theorem 6.1/Definition 6.3. The paper acknowledges this in a footnote, but the shared notation makes the incompatibility easy to miss; renaming the two variants (e.g., σ_lb and σ_ub) would improve clarity and prevent reader confusion.
[Fact 5.3 proof] In the proof of Fact 5.3, the expression 'λ_{i_1} ≥ 11ε/(d d_{j(i+1)})' appears to contain a typo: the subscript 'i+1' is undefined. It should presumably be 'd_{j(i_1)}' or a fixed bucket size; this should be corrected.
[Section 2.2, display after Eq. (2.9)] The notation in Eq. (2.9) and the surrounding text is slightly inconsistent: Z(θ, θ′) is defined with ρ_θ, ρ_θ′, while later in Eq. (2.12) the same function is written with U,V. The authors should consistently use one parameter convention throughout the overview.

Circularity Check

0 steps flagged · score 1.0 of 10

No circularity: the lower and upper bounds are proved by independent arguments, but the differing σ* definitions undermine the advertised near-optimality claim.

full rationale

The paper's central derivations are not circular. The lower bound is a new quantum Ingster–Suslina argument (Sections 4–5) and the upper bound adapts published subroutines, notably HSCertify from [BOW19] and the three-case decomposition from [CLO22], while adding new entangled-measurement analyses in Lemmas 6.7 and 6.8. The imported results are published with explicit proofs and do not assume the present theorem, so the self-citations are legitimate evidence under the independent-support rule. The paper itself flags the cost of this dependence: 'With apologies to the reader, this means our presentation cannot be completely self-contained, lest we copy large portions of [CLO22]' (Section 6.2). This is a reliance on prior work, not a circular reduction. A genuine correctness concern is the mismatch between the two definitions of σ*: Definition 5.2 removes up to 12ε mass sorting by λ_i/d_j(i), while Definition 6.3 removes ε²/20 mass sorting by λ_i, with footnote 6 admitting 'a few subtle differences'. The skeptic's example shows these can differ by 1/ε², so the informal 'nearly instance-optimal' statement does not follow from the stated Theorems 5.1 and 6.1. That is a gap in the claimed characterization, but it is not a case where a prediction is defined by its inputs or where a fitted parameter is renamed as a prediction. No circular step satisfying the required quote-and-reduction standard was found.

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

No new physical entities are introduced. The bounds rest on standard quantum-information inequalities, Haar-measure concentration, and prior testing results ([VV17], [BOW19], [CLO22], [TKR+10]); the truly novel ingredient is the quantum Ingster-Suslina divergence calculation. The free parameters listed are internal analytic choices, not fits to data.

free parameters (2)

Bucket perturbation magnitudes ε_j = ε_j = min{2^{-j-1}, α d_j^{1/3} 2^{-2(j+1)/3}}
Chosen by hand in Lemma 5.8 to optimize the lower-bound expression from Corollary 5.9; α is fixed by requiring total trace distance exactly ε. These are internal proof optimizers, not fits to experimental data.
Mass-removal thresholds (12ε lower bound; ε²/20 upper bound) = 12ε (Definition 5.2), ε²/20 (Definition 6.3)
Ad hoc constants controlling how much eigenvalue mass is discarded before computing ∥σ*∥_{1/2}; different thresholds are used in the lower and upper bounds.

assumptions (5)

standard math Lemma 3.8: mean-zero L-Lipschitz functions on U(d)^k satisfy E exp(f) ≤ exp(3L²/d), via log-Sobolev inequality with constant C=6/d
Imported from Meckes-Meckes [MM13, Cor 17] and Ledoux [Led99]; every Ingster-Suslina lower bound in Section 4 uses this.
standard math Quantum χ²-divergence Dχ²(ρ||σ)=tr(σ^{-1}(ρ-σ)²) satisfies dtr ≤ (1/2)√(Dχ²)
Lemma 3.2 from Temme et al. [TKR+10]; used in Fact 4.2 to convert divergence bounds into distinguishing lower bounds.
domain assumption VV17 classical identity-testing lower bound Ω(∥q^{-max}_{-ε}∥_{2/3}/ε²)
Used in Corollary 5.7 for the singleton-bucket corner case; valid for quantum certification of diagonal states because the n-copy state is classical.
domain assumption HSCertify (Lemma 6.2): Hilbert-Schmidt closeness testing with O(log(1/δ)/ε²) copies [BOW19]
External algorithm used as subroutine in the upper bound (Cases 2 and 3).
domain assumption CLO22 three-case decomposition (Lemma 6.6) and supporting facts (Fact 5.3, Fact 5.11, Lemma 5.16, Lemma 6.4, Fact 6.5)
Upper bound and parts of lower-bound corner analysis rely on these published results; the paper states its presentation cannot be fully self-contained.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Instance-Optimal Quantum State Certification with Entangled Measurements." pith.science (2026). https://pith.science/paper/EK3THGEK

@misc{pith2026250706010,
  author       = {Pith},
  title        = {Pith review of: Instance-Optimal Quantum State Certification with Entangled Measurements},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EK3THGEK}},
  note         = {Machine review of arXiv:2507.06010}
}

abstract

We consider the task of quantum state certification: given a description of a hypothesis state $\sigma$ and multiple copies of an unknown state $\rho$, a tester aims to determine whether the two states are equal or $\epsilon$-far in trace distance. It is known that $\Theta(d/\epsilon^2)$ copies of $\rho$ are necessary and sufficient for this task, assuming the tester can make entangled measurements over all copies [CHW07,OW15,BOW19]. However, these bounds are for a worst-case $\sigma$, and it is not known what the optimal copy complexity is for this problem on an instance-by-instance basis. While such instance-optimal bounds have previously been shown for quantum state certification when the tester is limited to measurements unentangled across copies [CLO22,CLHL22], they remained open when testers are unrestricted in the kind of measurements they can perform. We address this open question by proving nearly instance-optimal bounds for quantum state certification when the tester can perform fully entangled measurements. Analogously to the unentangled setting, we show that the optimal copy complexity for certifying $\sigma$ is given by the worst-case complexity times the fidelity between $\sigma$ and the maximally mixed state. We prove our lower bounds using a novel quantum analogue of the Ingster-Suslina method, which is likely to be of independent interest. This method also allows us to recover the $\Omega(d/\epsilon^2)$ lower bound for mixedness testing [OW15], i.e., certification of the maximally mixed state, with a surprisingly simple proof.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

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

Instance-optimal high-precision shadow tomography with few-copy measurements: A metrological approach
quant-ph 2026-02 conditional novelty 8.0 of 10

High-precision shadow tomography of unknown quantum states has sample complexity Θ~(Γ_p/ε²), with Γ_p characterized by the inverse Fisher information matrix of the optimal single-copy measurement.

Reference graph

Works this paper leans on

31 extracted references · 22 canonical work pages · cited by 1 Pith paper

[1]

Distributed quantum inner product estimation

Anurag Anshu, Zeph Landau, and Yunchao Liu. Distributed quantum inner product estimation. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 44--51, 2022

work page 2022
[2]

Distribution testing lower bounds via reductions from communication complexity

Eric Blais, Cl \'e ment Canonne, and Tom Gur. Distribution testing lower bounds via reductions from communication complexity. ACM Transactions on Computation Theory (TOCT) , 11(2):1--37, 2019

work page 2019
[3]

Entanglement is necessary for optimal quantum property testing

Sebastien Bubeck, Sitan Chen, and Jerry Li. Entanglement is necessary for optimal quantum property testing. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 692--703. IEEE, 2020

2020
[4]

Hamiltonian property testing

Andreas Bluhm, Matthias C Caro, and Aadil Oufkir. Hamiltonian property testing. arXiv preprint arXiv:2403.02968 , 2024

arXiv 2024
[5]

Quantum state certification

Costin B a descu, Ryan O'Donnell, and John Wright. Quantum state certification. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages 503--514, 2019

work page 2019
[6]

A survey on distribution testing: Your data is big

Cl \'e ment Canonne. A survey on distribution testing: Your data is big. but is it blue? Theory of Computing , pages 1--100, 2020

work page 2020
[7]

Topics and techniques in distribution testing: A biased but representative sample

Cl \'e ment Canonne. Topics and techniques in distribution testing: A biased but representative sample. Foundations and Trends in Communications and Information Theory , 19(6):1032--1198, 2022

work page 2022
[8]

A hierarchy for replica quantum advantage

Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. A hierarchy for replica quantum advantage. arXiv preprint arXiv:2111.05874 , 2021

arXiv 2021

Show all 31 references

[9]

Exponential separations between learning with and without quantum memory

Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. Exponential separations between learning with and without quantum memory. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 574--585. IEEE, 2022

2021
[10]

Optimal tradeoffs for estimating pauli observables

Sitan Chen, Weiyuan Gong, and Qi Ye. Optimal tradeoffs for estimating pauli observables. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1086--1105. IEEE, 2024

2024
[11]

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
[12]

Tight bounds for quantum state certification with incoherent measurements

Sitan Chen, Jerry Li, Brice Huang, and Allen Liu. Tight bounds for quantum state certification with incoherent measurements. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 1205--1213. IEEE, 2022

2022
[13]

Toward instance-optimal state certification with incoherent measurements

Sitan Chen, Jerry Li, and Ryan O’Donnell. Toward instance-optimal state certification with incoherent measurements. In Conference on Learning Theory , pages 2541--2596. PMLR, 2022

2022
[14]

Unitarity estimation for quantum channels

Kean Chen, Qisheng Wang, Peixun Long, and Mingsheng Ying. Unitarity estimation for quantum channels. IEEE Transactions on Information Theory , 69(8):5116--5134, 2023

2023
[15]

A new approach for testing properties of discrete distributions

Ilias Diakonikolas and Daniel M Kane. A new approach for testing properties of discrete distributions. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) , pages 685--694. IEEE, 2016

2016
[16]

Quantum channel certification with incoherent measurements

Omar Fawzi, Nicolas Flammarion, Aur \'e lien Garivier, and Aadil Oufkir. Quantum channel certification with incoherent measurements. In The Thirty Sixth Annual Conference on Learning Theory , pages 1822--1884. PMLR, 2023

2023
[17]

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. arXiv preprint arXiv:2506.11355 , 2025

2025 arXiv
[18]

On the sample complexity of purity and inner product estimation

Weiyuan Gong, Jonas Haferkamp, Qi Ye, and Zhihan Zhang. On the sample complexity of purity and inner product estimation. arXiv preprint arXiv:2410.12712 , 2024

2024 arXiv
[19]

Introduction to property testing

Oded Goldreich. Introduction to property testing . Cambridge University Press, 2017

2017
[20]

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
[21]

Nonparametric goodness-of-fit testing under Gaussian models , volume 169

Yuri Ingster and Irina A Suslina. Nonparametric goodness-of-fit testing under Gaussian models , volume 169. Springer Science & Business Media, 2012

2012
[22]

Fidelity for mixed quantum states

Richard Jozsa. Fidelity for mixed quantum states. Journal of Modern Optics , 41(12):2315--2323, 1994

1994
[23]

Concentration of measure and logarithmic S obolev inequalities

Michel Ledoux. Concentration of measure and logarithmic S obolev inequalities. In S\' e minaire de P robabilit\' e s, XXXIII , volume 1709 of Lecture Notes in Math. , pages 120--216. Springer, Berlin, 1999

1999
[24]

A survey of quantum property testing

Ashley Montanaro and Ronald de Wolf. A survey of quantum property testing. Theory of Computing , pages 1--81, 2016

2016
[25]

Spectral measures of powers of random matrices

Elizabeth Meckes and Mark Meckes. Spectral measures of powers of random matrices . Electronic Communications in Probability , 18:1 -- 13, 2013

2013
[26]

Quantum computation and quantum information

Michael Nielsen and Isaac Chuang. Quantum computation and quantum information . Cambridge university press, 2010

2010
[27]

Quantum spectrum testing

Ryan O'Donnell and John Wright. Quantum spectrum testing. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing , pages 529--538, 2015

2015
[28]

A coincidence-based test for uniformity given very sparsely sampled discrete data

Liam Paninski. A coincidence-based test for uniformity given very sparsely sampled discrete data. IEEE Transactions on Information Theory , 54(10):4750--4755, 2008

2008
[29]

The ^2 -divergence and mixing times of quantum markov processes

Kristan Temme, Michael James Kastoryano, Mary Beth Ruskai, Michael Marc Wolf, and Frank Verstraete. The ^2 -divergence and mixing times of quantum markov processes. Journal of Mathematical Physics , 51(12), 2010

2010
[30]

An automatic inequality prover and instance optimal identity testing

Gregory Valiant and Paul Valiant. An automatic inequality prover and instance optimal identity testing. SIAM Journal on Computing , 46(1):429--455, 2017

2017
[31]

Lecture notes on information-theoretic methods for high-dimensional statistics

Yihong Wu. Lecture notes on information-theoretic methods for high-dimensional statistics. Lecture Notes for ECE598YW (UIUC) , 16:15, 2017

2017

Pith tools

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

[1] [1]

Distributed quantum inner product estimation

Anurag Anshu, Zeph Landau, and Yunchao Liu. Distributed quantum inner product estimation. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 44--51, 2022

work page 2022

[2] [2]

Distribution testing lower bounds via reductions from communication complexity

Eric Blais, Cl \'e ment Canonne, and Tom Gur. Distribution testing lower bounds via reductions from communication complexity. ACM Transactions on Computation Theory (TOCT) , 11(2):1--37, 2019

work page 2019

[3] [3]

Entanglement is necessary for optimal quantum property testing

Sebastien Bubeck, Sitan Chen, and Jerry Li. Entanglement is necessary for optimal quantum property testing. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 692--703. IEEE, 2020

2020

[4] [4]

Hamiltonian property testing

Andreas Bluhm, Matthias C Caro, and Aadil Oufkir. Hamiltonian property testing. arXiv preprint arXiv:2403.02968 , 2024

arXiv 2024

[5] [5]

Quantum state certification

Costin B a descu, Ryan O'Donnell, and John Wright. Quantum state certification. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages 503--514, 2019

work page 2019

[6] [6]

A survey on distribution testing: Your data is big

Cl \'e ment Canonne. A survey on distribution testing: Your data is big. but is it blue? Theory of Computing , pages 1--100, 2020

work page 2020

[7] [7]

Topics and techniques in distribution testing: A biased but representative sample

Cl \'e ment Canonne. Topics and techniques in distribution testing: A biased but representative sample. Foundations and Trends in Communications and Information Theory , 19(6):1032--1198, 2022

work page 2022

[8] [8]

A hierarchy for replica quantum advantage

Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. A hierarchy for replica quantum advantage. arXiv preprint arXiv:2111.05874 , 2021

arXiv 2021