Optimal Quantum State Testing Even with Limited Entanglement
Pith reviewed 2026-05-10 17:25 UTC · model grok-4.3
The pith
Quantum state certification achieves near-optimal copy rates using measurements on only d squared copies at a time.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We prove a smooth upper bound on the number of copies needed for state certification as a function of t, achieving rates close to the information-theoretic optimum when t equals d squared. In the regime epsilon less than 1 over square root d, this uses less entanglement than the fully joint measurement protocol. The approach relies on novel reductions from testing to learning that leverage recent tomography results without extra overhead, and the same bounds hold for mixedness testing and purity estimation.
What carries the argument
Smooth upper bound on copy complexity as a function of the entanglement parameter t, derived from reductions of testing to learning combined with non-black-box quantum state tomography.
If this is right
- High-precision certification of d-dimensional states becomes possible without requiring full joint entanglement over all copies.
- Optimal rates for mixedness testing and purity estimation are achieved at the same t equals d squared threshold.
- Joint measurements must involve at least d to the Omega of 1 copies to reach the optimal rates in high precision.
- Testing tasks can be solved by first obtaining a learning-based approximation and then verifying closeness to the target.
Where Pith is reading between the lines
- The reduction technique could be applied to other quantum property testing problems such as estimating entanglement or verifying channel properties.
- Experimental implementations on near-term devices with limited multi-qubit gates might now reach information-theoretic rates for these tasks.
- Intermediate values of t between poly log d and d squared may admit further refined bounds that the current smoothness result leaves open.
Load-bearing premise
The reductions from testing to learning introduce no extra copy overhead that would invalidate the stated bounds.
What would settle it
A concrete quantum state and measurement strategy showing that for t much smaller than d squared the number of copies required exceeds Theta of d over epsilon squared in the high-precision regime would disprove the upper bound.
read the original abstract
In this work, we consider the fundamental task of quantum state certification: given copies of an unknown quantum state $\rho$, test whether it matches some target state $\sigma$ or is $\epsilon$-far from it. For certifying $d$-dimensional states, $\Theta(d/\epsilon^2)$ copies of $\rho$ are known to be necessary and sufficient. However, the algorithm achieving this complexity makes fully entangled measurements over all $O(d/\epsilon^2)$ copies of $\rho$. Often, one is interested in certifying states to a high precision; this makes such joint measurements intractable even for low-dimensional states. Thus, we study whether one can obtain optimal rates for quantum state certification and related testing problems while only performing measurements on $t$ copies at once, for some $1 < t \ll d/\epsilon^2$. While it is well-understood how to use intermediate entanglement to achieve optimal quantum state learning, the only protocol known to achieve optimal testing is the one using fully entangled measurements. Our main result is a smooth copy complexity upper bound for state certification as a function of $t$, which achieves a near-optimal rate at $t = d^2$. In the high-precision regime, i.e., for $\epsilon < \frac{1}{\sqrt{d}}$, this is a strict improvement over the entanglement used by the aforementioned optimal protocol. We also extend our techniques to develop new algorithms for the related tasks of mixedness testing and purity estimation, and show tradeoffs achieving the optimal rates for these problems at $t = d^2$ as well. Our algorithms are based on novel reductions from testing to learning and leverage recent advances in quantum state tomography in a non-black-box fashion. We complement our upper bounds with smooth lower bounds that imply joint measurements on $t \geq d^{\Omega(1)}$ copies are necessary to achieve optimal rates for certification in the high-precision regime.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript develops algorithms for quantum state certification (and extensions to mixedness testing and purity estimation) that achieve the optimal Θ(d/ε²) copy complexity while restricting measurements to at most t copies at a time. The central upper bound is a smooth function of t that becomes near-optimal at t = d² and yields a strict improvement over fully entangled protocols in the high-precision regime ε < 1/√d. The algorithms rely on novel reductions from testing to learning together with non-black-box use of recent quantum state tomography results; these are complemented by lower bounds showing that t = d^Ω(1) is necessary to attain optimal rates in the high-precision regime.
Significance. If the reductions preserve the claimed copy complexity exactly, the result is significant for both theory and practice: it shows that optimal quantum testing rates do not require full entanglement over all copies, which is especially relevant for high-precision certification where joint measurements on O(d/ε²) copies become intractable. The smooth t-dependence, the non-black-box leverage of tomography advances, and the matching lower bounds provide a clean characterization of the entanglement-copy-complexity tradeoff. These features would make the work a useful reference for subsequent work on limited-entanglement quantum algorithms.
major comments (2)
- [Abstract] Abstract and introduction: the claimed smooth upper bound and strict improvement for ε < 1/√d rest on the reductions from certification to learning preserving an O(d/ε²) total copy count without extra polynomial or logarithmic factors in d or 1/ε. The description does not indicate how the non-black-box invocation of tomography results avoids the usual testing-to-learning overhead that would erase the high-precision advantage.
- [Lower bounds section] Lower-bound section: while the lower bounds correctly establish that t ≥ d^Ω(1) is necessary for optimal rates, the upper-bound construction at t = d² must be shown to meet the same threshold exactly; any hidden d- or ε-dependent overhead in the reduction would make the upper and lower bounds fail to match in the high-precision regime.
minor comments (1)
- [Introduction] The parameter t is introduced as the number of copies measured jointly, but its precise relation to the total number of copies and to the entanglement resource should be stated explicitly in the first technical section.
Simulated Author's Rebuttal
We thank the referee for their careful reading of our manuscript and for the constructive comments. We respond to each major comment below.
read point-by-point responses
-
Referee: [Abstract] Abstract and introduction: the claimed smooth upper bound and strict improvement for ε < 1/√d rest on the reductions from certification to learning preserving an O(d/ε²) total copy count without extra polynomial or logarithmic factors in d or 1/ε. The description does not indicate how the non-black-box invocation of tomography results avoids the usual testing-to-learning overhead that would erase the high-precision advantage.
Authors: We appreciate this comment. The non-black-box use of tomography in our reduction allows us to bypass the typical overhead by using the tomography estimates directly for the certification statistic, incurring only a constant multiplicative factor rather than polynomial or logarithmic ones in d or 1/ε. This is explained in detail in the technical sections of the paper. We will update the abstract and introduction to explicitly note that the total copy complexity remains O(d/ε²) and to briefly describe how the non-black-box approach avoids the overhead, thereby preserving the strict improvement in the high-precision regime. revision: yes
-
Referee: [Lower bounds section] Lower-bound section: while the lower bounds correctly establish that t ≥ d^Ω(1) is necessary for optimal rates, the upper-bound construction at t = d² must be shown to meet the same threshold exactly; any hidden d- or ε-dependent overhead in the reduction would make the upper and lower bounds fail to match in the high-precision regime.
Authors: We agree that explicit verification is important. Our upper-bound construction at t = d² achieves exactly the optimal Θ(d/ε²) copy complexity, as the smooth dependence on t is designed such that at t = d² it matches the known optimal rate without additional factors. The lower bounds are matched asymptotically in the high-precision regime. We will revise the lower bounds section to include a direct comparison showing that the upper bound meets the lower bound threshold exactly, confirming no hidden overheads affect the matching. revision: yes
Circularity Check
No significant circularity: upper bounds via novel reductions to learning/tomography; lower bounds independent
full rationale
The derivation chain for the smooth copy-complexity upper bound rests on explicitly described novel reductions from state certification to quantum state learning, followed by non-black-box invocation of prior tomography results. These steps are algorithmic constructions that do not reduce by definition or fitting to the target bound itself. The complementary lower bounds are derived separately via direct information-theoretic arguments showing necessity of t = d^Ω(1) entanglement in the high-precision regime, providing independent grounding rather than self-referential closure. No self-definitional equations, fitted-input predictions, or load-bearing self-citation chains appear in the central claims; the result is therefore self-contained against external benchmarks.
Axiom & Free-Parameter Ledger
Reference graph
Works this paper leans on
-
[1]
[ADLY25b] Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu, and Nengkun Yu
Cited on page 12. [ADLY25b] Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu, and Nengkun Yu. Pauli measure- ments are not optimal for single-copy tomography. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 718–729, 2025. Cited on page 12. 42 [AISW20] Jayadev Acharya, Ibrahim Issa, Nirmal V Shende, and Aaron B Wagner. Estimat...
work page 2025
-
[2]
[ALL22] Anurag Anshu, Zeph Landau, and Yunchao Liu
Cited on pages 4 and 12. [ALL22] Anurag Anshu, Zeph Landau, and Yunchao Liu. Distributed quantum inner product es- timation. InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 44–51, 2022. Cited on page 12. [AS25] Srinivasan Arunachalam and Louis Schatzki. Generalized inner product estimation with limited quantum communica...
-
[3]
[CLSW26] Andrea Coladangelo, Jerry Li, Joseph Slote, and Ellen Wu
Cited on pages 3, 5, 8, 9, 11, 26, and 27. [CLSW26] Andrea Coladangelo, Jerry Li, Joseph Slote, and Ellen Wu. The power of two bases: Robust and copy-optimal certification of nearly all quantum states with few-qubit measurements. arXiv preprint arXiv:2602.11616, 2026. Cited on page 12. [DK16] Ilias Diakonikolas and Daniel M Kane. A new approach for testin...
-
[4]
Cited on page 12. [GHO25] Meghal Gupta, William He, and Ryan O’Donnell. Few single-qubit measurements suffice to certify any quantum state.arXiv preprint arXiv:2506.11355, 2025. Cited on page 12. [GHYZ24] Weiyuan Gong, Jonas Haferkamp, Qi Ye, and Zhihan Zhang. On the sample complexity of purity and inner product estimation.arXiv preprint arXiv:2410.12712,...
-
[5]
Cited on page 14. [Hay98] Masahito Hayashi. Asymptotic estimation theory for a finite-dimensional pure state model. Journal of Physics A: Mathematical and General, 31(20):4633, 1998. Cited on page 15. [HHJ+16] Jeongwan Haah, Aram W Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample- optimal tomography of quantum states. InProceedings of the forty-eig...
-
[6]
[NTGK25] Jan N¨ oller, Viet T Tran, Mariami Gachechiladze, and Richard Kueng
Cited on page 12. [NTGK25] Jan N¨ oller, Viet T Tran, Mariami Gachechiladze, and Richard Kueng. An infinite hierarchy of multi-copy quantum learning tasks.arXiv preprint arXiv:2510.08070, 2025. Cited on page 12. [OW15] Ryan O’Donnell and John Wright. Quantum spectrum testing. InProceedings of the forty- seventh annual ACM symposium on Theory of computing,...
-
[7]
Cited on page 12. [YNM25] Satoshi Yoshida, Ryotaro Niwa, and Mio Murao. Random dilation superchannel.arXiv preprint arXiv:2512.21260, 2025. Cited on page 12. 45
work page internal anchor Pith review arXiv 2025
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.