CS Paper Radar

On the Power of Adaptivity in Testing Quantum States in Fidelity

Jan Seyfried, Sayantan Sen, Marco Tomamichel

cs.DS quant-ph ·submitted 2026-09-08 13:30 UTC · v2
theoryhot direction

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\otimesρ_C$, or is far from being a product. The sample complexities of these problems are now well-understood for a decision gap $\varepsilon$ 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}/\varepsilon^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 $\widetildeΘ(r^{3/2}/\varepsilon)$ samples. For equivalence testing and independence testing, we provide adaptive algorithms using $\widetilde{O}(\min\{d^{3/2}/\varepsilon^2,d^{9/4}/\varepsilon\})$ and $\widetilde{O}(\min\{(d_Ad_C)^{3/2}/\varepsilon^2,d_A^{9/4}d_C^{3/4}/\varepsilon\})$ samples, for $d_A\geq d_C$, respectively. Our main technique is a framework that uses partial learning and a reduction to testing in $\ell_2$-distance, adapted from the distribution testing literature. We show that adaptivity matters for equivalence testing in fidelity by proving that $\widetildeΩ(1/\varepsilon^2)$ samples are necessary in the non-adaptive case even for qubits, showing a separation from certification.

Comment
49 pages. Minor updates from previous version

Closest papers

Nearest neighbours by meaning across the whole index.

Near-Optimal Mixedness Testing with Pauli Measurements

cs.CC quant-phcs.IT ·2026-08-19 ·Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu, Nengkun Yu
theory similarity 0.70
Abstract · Added determinstic Pauli mixedness testing results, fixed typos

We consider a fundamental problem of \emph{mixedness testing}: Given $n$ copies of an $N$-qubit state $ρ$, determine whether $ρ= \mathbb{I}_d/d$ or $\|ρ-\mathbb{I}_d/d\|_1 \geq \varepsilon$ with high probability, where $d = 2^N$. In particular, we focus on performing this task with simple single-qubit measurements, i.e. measurements that are prepared independently on each qubit. We provide a nearly complete picture of single-qubit mixedness testing by showing that its copy-complexity is $\tildeΘ\left(\sqrt{10}^N/\varepsilon^2\right)$. To establish our lower bound, we introduce a new measurement-dependent lower bound framework for adaptive single-copy state certification. For the upper bound, we present a randomized Pauli basis measurement protocol, which relies on a new primitive for computationally efficient uniformity testing of correlation-concentrated distributions on the Boolean hypercube. In conjunction, we provide lower and upper bounds for mixedness testing with fixed Pauli measurement protocols.

0.31

Distributed Quantum Property Testing with Quantum Carrier Pigeons

cs.DS quant-ph ·2026-09-08 ·Kenny Chen, Mina Doosti, Ryan Sweke, Chirag Wadhwa
theory similarity 0.68
Abstract · Merges and subsumes arXiv:2604.05962 and arXiv:2606.31753, and includes additional/improved results. 67 pages, 1 figure, 1 table

We introduce a framework for distributed quantum inference under communication constraints. In our model, $m$ distributed nodes each receive one copy of an unknown $d$-dimensional quantum state $ρ$, before communicating via a constrained one-way communication channel with a central node, which aims to infer some property of $ρ$. This framework generalizes the classical distributed inference framework introduced by Acharya, Canonne, and Tyagi [COLT 2019], by allowing quantum resources such as quantum communication and shared entanglement. Within this setting, we focus on the fundamental problem of quantum state certification: Given a complete description of some state $σ$, decide whether $ρ=σ$ or $\|ρ-σ\|_1\geq ε$. Additionally, we focus on the case of limited communication between distributed nodes and the central node: we assume each communication channel is limited to only $n_c$ bits and $n_q$ qubits with $n_c + n_q \leq \log d$. When all nodes can make use of a shared source of randomness, we show that the copy complexity of distributed state certification is $Θ(\frac{d^2}{2^{n_q} 2^{n_c/2}ε^2})$. We further demonstrate that shared randomness is necessary to achieve the above complexity, by proving an $Ω(\frac{d^3}{4^{n_q} 2^{n_c} ε^2})$ lower bound in the $\textit{private-coin}$ setting. Moreover, we develop a private-coin algorithm that matches this bound up to a $\sqrt{\log d}$ factor, showing this complexity is near-optimal. Together, our work establishes a general framework for distributed quantum inference with communication constraints and characterizes the complexity of distributed state certification with limited communication.

0.44

Optimal fidelity estimation when one state is pure via algorithmic Uhlmann transform

cs.DS quant-phcs.IT ·2026-08-11 ·Yupan Liu, Qisheng Wang
similarity 0.67
Abstract · 11 pages, 1 algorithm, 1 table, 3 figures

The Uhlmann fidelity ${\rm F}(ρ_0,ρ_1) = {\rm tr}|\sqrt{ρ_0}\sqrt{ρ_1}|$ is one of the most fundamental quantities in quantum information theory for quantifying the closeness between two quantum states. Estimating the Uhlmann fidelity to within additive error $\varepsilon$ requires a number of copies of the states, or queries to their state-preparation circuits, that depends at least linearly on the smaller of the ranks of $ρ_0$ and $ρ_1$. Consequently, this rank dependence disappears when either state is pure, in which case the query and sample complexities depend only polynomially on $1/\varepsilon$. However, the known optimal estimator for ${\rm F}(ρ,|ψ\rangle\!\langleψ|)$ due to Fang and Wang (ESA 2025) requires prior knowledge of which state is pure. In this work, we remove this mathematically unnecessary prior-knowledge requirement and establish an optimal estimator for ${\rm F}(ρ, |ψ\rangle\!\langleψ|)$ under the sole promise that one of the two states is pure, without knowing which one. Our estimator is obtained by specializing the refined algorithmic Uhlmann transform of Utsumi, Nakata, Wang, and Takagi (2025) to the case where one state is pure. In this setting, the Uhlmann fidelity can be recovered as follows: apply a unitary dilation of ${\rm tr}_{\sf A}(|ψ_0\rangle\!\langleψ_1|)$ (or its inverse) to the reference register $\sf R$ of the purification $|ψ_1\rangle$ (or $|ψ_0\rangle$) on the registers $\sf A$ and $\sf R$, estimate the corresponding square-root amplitude in each case, and take the maximum of the resulting two estimates.

0.38

Robustness of quantum spectrum estimation: weak Schur sampling under noisy inputs

cs.IT quant-phmath.RT ·2026-10-02 ·Vladyslav Visnevskyi, Laura Mančinska
similarity 0.65
Abstract · v3: slight correction to the statement of Theorem 3 in Preliminaries; expanded the proof of Proposition 45 in the Appendix for clarity; unif…

We initiate the study of weak Schur sampling (WSS) under noisy inputs. Many optimal quantum learning algorithms rely on this measurement, for instance in quantum spectrum estimation (QSE) and quantum state tomography (QST). The standard analysis of WSS, QSE and QST assumes that the $n$ input copies of the target state $ρ$ are identical, i.e. $ρ^{\otimes n}$. We study what happens when they are not, a more realistic noisy scenario that breaks the very permutation symmetry on which WSS is built. In the simplest model the input is a noisy product state: the copies are independent but not necessarily identical and each is $ε$-close in trace distance to the $d$-dimensional target state $ρ$. A naive argument via the data-processing inequality allows the per-copy errors to accumulate to $nε$ on the measurement outcome. We show that for QSE via WSS this does not happen: the expected estimation error in total variation is at most $ε+η(n,d)$, where $η(n,d)=O(d/\sqrt n)$ is the noiseless error, and the additive noise term $ε$ is optimal. The output error does not grow with $n$ even though the input error does; in this sense WSS is robust. Beyond noisy product states, for arbitrary input $ω$ we show that the error is at most $η(n,d)+\frac{1}{n}\|ω-ρ^{\otimes n}\|_{W_1}$, where $W_1$ is the quantum Wasserstein distance of De Palma et al. In particular, our results imply, for the first time, noise-robustness of Keyl and Werner's seminal algorithm for QSE, more than two decades after its introduction. Finally, we show that the noise cannot be too bad: within our model of robustness the promise on the input cannot be weakened to closeness of single-copy marginals or to a global trace-distance budget alone, as in both cases some inputs defeat every measurement and estimator.

0.21

Quantum simultaneous decoding via pretty-good measurements of tilted states

cs.IT quant-ph ·2026-10-11 ·Mark M. Wilde
theory similarity 0.64
Abstract · 92 pages, 18 figures

A multiple-access channel transmits messages from several senders to one receiver. For quantum outputs, the receiver must distinguish states depending on all messages, while tests for different decoding errors may not commute. In this paper, we give a self-contained account of simultaneous decoding, in which one joint measurement recovers the messages at the established achievable rates using independent codebooks. The proof combines Sen's tilted-subspace method with Cheng's analysis of the pretty-good measurement, a standard measurement for distinguishing quantum states. Auxiliary labels close to a common reference state separate the geometric directions associated with different errors. A Gram-matrix bound then allows separately chosen binary tests to certify the performance of one measurement. The labels are removed from the completed decoder, leading to a deterministic packing theorem that applies to finite state ensembles, including unequal priors. We develop the two-sender case first, with worked examples and figures, before treating any fixed number of senders. Sharper finite-error guarantees for the same decoder are developed separately, with sharp bounds for two specified steps of the analysis rather than a claim of globally optimal decoding. Applications recover known achievable rates for unassisted and entanglement-assisted classical communication, distributed classical compression with quantum side information, and coherent-state communication through a beamsplitter or passive multiport device. The common proof makes the geometric mechanism and its quantitative consequences available without repeating the construction for each application.

0.10

Optimal spectrum estimation

cs.CC quant-phcs.DS ·2026-09-24 ·Ainesh Bakshi, Apoorv Vikram Singh, Xinyu Tan
theoryhighly cited similarity 0.64
Abstract · 37 pages

We prove that the spectrum of an unknown $d$-dimensional quantum state can be estimated to error $\varepsilon$ in total variation distance using \[ O\!\left(d^2\min\left\{ \frac{1}{(\varepsilon\log d)^4},\; \frac{1}{(\varepsilon\log d)^2} \right\}\right) \] copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of $d$ in copy complexity, which we conjecture to be optimal. We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron--Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound.

0.35

Tight Lower Bounds for State Tomography with Limited Entanglement

cs.IT quant-phcs.LG ·2026-09-04 ·Ufuk Keskin, Jason Luo, Mahbod Majid, Matthew Radzihovsky
theoryhighly cited similarity 0.63
Abstract · 36 pages

We study state tomography when each measurement acts on at most $k$ fresh copies and no quantum memory is retained between blocks. We prove a lower bound matching the upper bound in [arXiv:2510.07788]. Thus the copy complexity of estimating an arbitrary $d$-dimensional state to trace distance $ε$ is, up to absolute constant factors, $\max\{d^3/(\sqrt{k}ε^2),d^2/ε^2\}$ for every $k$ and all sufficiently small $ε$. This removes the earlier restriction that $k$ be small as a function of the accuracy. The lower bound applies to arbitrary measurements within each block and adaptive choices between blocks. The lower bound already applies in a small neighborhood of any state whose smallest eigenvalue is of order $1/d$, even when the center is known. The main ingredient is a uniform Fisher information bound for one measurement block that depends only on the smallest eigenvalue of the state. The proof avoids the perturbative expansion responsible for the restriction in [arXiv:2402.16353]. Fano's inequality for metric balls and a log-Sobolev comparison between mutual and Fisher information then reduce the adaptive protocol to this block bound [arXiv:1607.00550, arXiv:1902.08582].

0.41

Convex splitting by binary quantum hypothesis testing

cs.IT quant-ph ·2026-11-19 ·Mark M. Wilde
similarity 0.62
Abstract · 44 pages, 4 figures

How many independent quantum systems does it take to hide one system that is correlated with a reference? An observer can measure all the systems together with the reference to detect the correlation. We turn any such measurement into binary tests on a single system and the reference. For each test we bound the probability of declaring a signal when an independent pair was prepared. Averaging the largest signal acceptance probabilities allowed by these bounds controls the normalized trace distance in the convex-split lemma. A second bound gives a sufficient number of systems by minimizing the hypothesis-testing relative entropy over the state of the reference. Both bounds hold for density operators on separable Hilbert spaces. Comparing two distributions for the location of the hidden system gives one-shot bounds for private communication and one-way secret key distillation, including the public information available to an eavesdropper. For a fixed finite-alphabet model with separable quantum outputs and positive information advantage and variances, we recover the known Gaussian corrections to the attainable number of private or key bits from $n$ independent repetitions and bound the remaining loss by $\log_2 n+O(1)$ at fixed errors. The position-based key distillation protocol attains this bound with $O(n)$ public bits.

0.34