On the Power of Adaptivity in Testing Quantum States in Fidelity
Abstract
We study the problems of quantum state certification, equivalence testing and independence testing. In certification, given samples of an unknown quantum state ρ and the description of a state σ, the goal is to test whether ρ=σ, or whether ρ and σ are far in a given distance measure. In equivalence testing, σ is also unknown and only accessible via samples. Independence testing decides whether ρAC=ρA⊗ρC, or is far from being a product. The sample complexities of these problems are now well-understood for a decision gap ε in trace distance: in the single-copy measurement setting with d-dimensional states, all three tasks can be solved using the same non-adaptive approach, which uses Θ(d3/2/ε2) samples and is optimal in general, even without adaptivity. In this work, we consider decision gaps expressed in fidelity and study possible separations between these problems and how adaptivity can help. We prove that certification with respect to fidelity for a state σ of rank r does not benefit from adaptivity and requires Θ̃(r3/2/ε) samples. For equivalence testing and independence testing, we provide adaptive algorithms using Õ(min{d3/2/ε2,d9/4/ε}) and Õ(min{(dAdC)3/2/ε2,dA9/4dC3/4/ε}) samples, for dA≥ dC, respectively. Our main technique is a framework that uses partial learning and a reduction to testing in ℓ2-distance, adapted from the distribution testing literature. We show that adaptivity matters for equivalence testing in fidelity by proving that Ω̃(1/ε2) samples are necessary in the non-adaptive case even for qubits, showing a separation from certification.
Related
- Entangling power and fidelity diagnostic for bipartite quantum channels
- Efficient Fidelity Estimation of General Quantum Resource States via Clifford Circuits
- Parallel Quantum Advantage with Limited Adaptivity Requires Structure
- Testing and Diagnosing Parameter Miscalibration in Probabilistic Error Cancellation via Direct Fidelity Estimation
- Qubit-Based Benchmarking of InP HEMT LNAs: Readout Fidelity Versus Power Consumption
BibTeX
@misc{seyfried2026power,
title = {{On the Power of Adaptivity in Testing Quantum States in Fidelity}},
author = {Jan Seyfried and Sayantan Sen and Marco Tomamichel},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.08733},
eprint = {2609.08733},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08733},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the Power of Adaptivity in Testing Quantum States in Fidelity
AU - Jan Seyfried
AU - Sayantan Sen
AU - Marco Tomamichel
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2609.08733
UR - https://arxiv.org/abs/2609.08733
AB - We study the problems of quantum state certification, equivalence testing and independence testing. In certification, given samples of an unknown quantum state ρ and the description of a state σ, the goal is to test whether ρ=σ, or whether ρ and σ are far in a given distance measure. In equivalence testing, σ is also unknown and only accessible via samples. Independence testing decides whether ρ_AC=ρ_A⊗ρ_C, or is far from being a product. The sample complexities of these problems are now well-understood for a decision gap ε in trace distance: in the single-copy measurement setting with d-dimensional states, all three tasks can be solved using the same non-adaptive approach, which uses Θ(d^3/2/ε^2) samples and is optimal in general, even without adaptivity. In this work, we consider decision gaps expressed in fidelity and study possible separations between these problems and how adaptivity can help. We prove that certification with respect to fidelity for a state σ of rank r does not benefit from adaptivity and requires Θ̃(r^3/2/ε) samples. For equivalence testing and independence testing, we provide adaptive algorithms using Õ(min{d^3/2/ε^2,d^9/4/ε}) and Õ(min{(d_Ad_C)^3/2/ε^2,d_A^9/4d_C^3/4/ε}) samples, for d_A≥ d_C, respectively. Our main technique is a framework that uses partial learning and a reduction to testing in ℓ_2-distance, adapted from the distribution testing literature. We show that adaptivity matters for equivalence testing in fidelity by proving that Ω̃(1/ε^2) samples are necessary in the non-adaptive case even for qubits, showing a separation from certification.
ER -