Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.17411

Sharp bounds for perfect quantum state classification beyond antidistinguishability

Nathaniel Johnston, Benjamin Lovitz, Vincent Russo, Jamie Sikora

quant-phSubmitted Sep 15, 2026• Announced Sep 16, 2026• 1 citation
arXivHTMLPDF

Abstract

A multiset of pure quantum states is said to be k-learnable if there is a measurement strategy that always narrows an unknown sample drawn from the list down to one of at most k candidates. The parameter k interpolates between distinguishability and antidistinguishability, and provides a unified framework for partial state identification. We prove two universal, and optimal, Gram-matrix criteria for k-learnability: a Frobenius-norm sufficient condition and an entrywise-$\ell_1$ necessary condition. We apply them to derive explicit learnability and copy-complexity guarantees for several well-known sets of states including SIC-POVMs, mutually unbiased bases, and stabilizer states. We further apply our results to zero-error mutation detection problems such as anomaly detection and changepoint detection.

AI Summary

Queued: an LLM will read the paper as soon as there is capacity.

Comments
32 pages. Comments welcome

Related papers

Tight bounds for antidistinguishability and circulant sets of pure quantum states

Nathaniel Johnston, Vincent Russo, Jamie Sikora

A set of pure quantum states is said to be antidistinguishable if upon sampling one at random, there exists a measurement to perfectly determine some state that was not sampled. We show that antidistinguishability of a set of n pure states is equivalent to a property of its Gram matrix called ( n − 1 ) -incoherence, thus establishing a connection with quantum resource theories that lets us apply a wide variety of new tools to antidistinguishability. As a particular application of our result, we present an explicit formula (not involving any semidefinite programming) that determines whether or not a set with a circulant Gram matrix is antidistinguishable. We also show that if all inner products are smaller than ( n − 2 ) / ( 2 n − 2 ) then the set must be antidistinguishable, and we show that this bound is tight when n ≤ 4 . We also give a simpler proof that if all the inner products are strictly larger than ( n − 2 ) / ( n − 1 ) , then the set cannot be antidistinguishable, and we show that this bound is tight for all n .

arXiv:2311.17047•Quantum•Feb 4, 2025•22 citations

The complexity of perfect quantum state classification

Nathaniel Johnston, Benjamin Lovitz, Russo, Vincent +1 more

The problem of quantum state classification asks how accurately one can identify an unknown quantum state that is promised to be drawn from a known set of pure states. In this work, we introduce the notion of $k$-learnability, which captures the ability to identify the correct state using at most $k$ guesses, with zero error. We show that deciding whether a given family of states is $k$-learnable can be solved via semidefinite programming. When there are $n$ states, we present polynomial-time (in $n$) algorithms for determining $k$-learnability for two cases: when $k$ is a fixed constant or the dimension of the states is a fixed constant. When both $k$ and the dimension of the states are part of the input, we prove that there exist succinct certificates placing the problem in NP, and we establish NP-hardness by a reduction from the classical $k$-clique problem. Together, our findings delineate the boundary between efficiently solvable and intractable instances of quantum state classification in the perfect (zero-error) regime.

arXiv:2510.20789•Oct 23, 2025•2 citations

Pretty simple bounds on quantum state discrimination

Ashley Montanaro

We show that the quantum measurement known as the pretty good measurement can be used to identify an unknown quantum state picked from any set of $n$ mixed states that have pairwise fidelities upper-bounded by a constant below 1, given $O(\log n)$ copies of the unknown state, with high success probability in the worst case. If the unknown state is promised to be pure, there is an explicit measurement strategy which solves this worst-case quantum state discrimination problem with $\widetilde{O}(\|G\|)$ copies, where $G$ is the Gram matrix of the states.

arXiv:1908.08312•Aug 22, 2019•19 citations

Instance-optimal high-precision shadow tomography with few-copy measurements: A metrological approach

Senrui Chen, Weiyuan Gong, Sisi Zhou

We study the sample complexity of shadow tomography in the high-precision regime under realistic measurement constraints. Given an unknown $d$-dimensional quantum state $ρ$ and a known set of observables $\{O_i\}_{i=1}^m$, the goal is to estimate expectation values $\{\mathrm{tr}(O_iρ)\}_{i=1}^m$ to accuracy $ε$ in $L_p$-norm, using possibly adaptive measurements that act on $O(\mathrm{polylog}(d))$ number of copies of $ρ$ at a time. We focus on the regime where $ε$ is below an instance-dependent threshold. Our main contribution is an instance-optimal characterization of the sample complexity as $\tildeΘ(Γ_p/ε^2)$, where $Γ_p$ is a function of $\{O_i\}_{i=1}^m$ defined via an optimization formula involving the inverse Fisher information matrix. Previously, tight bounds were known only in special cases, e.g. Pauli shadow tomography with $L_\infty$-norm error. Concretely, we first analyze a simpler oblivious variant where the goal is to estimate an observable of the form $\sum_{i=1}^m α_i O_i$ with $\|α\|_q = 1$ (where $q$ is dual to $p$) revealed after the measurement. For single-copy measurements, we obtain a sample complexity of $Θ(Γ^{\mathrm{ob}}_p/ε^2)$. We then show $\tildeΘ(Γ_p/ε^2)$ is necessary and sufficient for the original problem, with the lower bound applying to unbiased, bounded estimators. Our upper bounds rely on a two-step algorithm combining coarse tomography with local estimation. Notably, $Γ^{\mathrm{ob}}_\infty = Γ_\infty$. In both cases, allowing $c$-copy measurements improves the sample complexity by at most $Ω(1/c)$. Our results establish a quantitative correspondence between quantum learning and metrology, unifying asymptotic metrological limits with finite-sample learning guarantees.

quant-pharXiv:2602.04952•Feb 6, 2026•10 citations

Online learning of quantum states*

Scott Aaronson, Xinyi Chen, Elad Hazan +2 more

Abstract Suppose we have many copies of an unknown n -qubit state . We measure some copies of using a known two-outcome measurement E 1 , then other copies using a measurement E 2 , and so on. At each stage t , we generate a current hypothesis about the state , using the outcomes of the previous measurements. We show that it is possible to do this in a way that guarantees that , the error in our prediction for the next measurement, is at least at most times. Even in the ‘non-realizable’ setting—where there could be arbitrary noise in the measurement outcomes—we show how to output hypothesis states that incur at most excess loss over the best possible state on the first T measurements. These results generalize a 2007 theorem by Aaronson on the PAC-learnability of quantum states, to the online and regret-minimization settings. We give three different ways to prove our results—using convex optimization, quantum postselection, and sequential fat-shattering dimension—which have different advantages in terms of parameters and portability.

arXiv:1802.09025•Journal of Statistical Mechanics Theory and Experiment•Dec 1, 2019•67 citations

Single-Copy Stabilizer Testing

Marcel Hinsche, Jonas Helsen

We consider the problem of testing whether an unknown $n$-qubit quantum state $|ψ\rangle$ is a stabilizer state, with only single-copy access. We give an algorithm solving this problem using $O(n)$ copies, and conversely prove that $Ω(\sqrt{n})$ copies are required for any algorithm. The main observation behind our algorithm is that when repeatedly measuring in a randomly chosen stabilizer basis, stabilizer states are the most likely among the set of all pure states to exhibit linear dependencies in measurement outcomes. Our algorithm is designed to probe deviations from this extremal behavior. For the lower bound, we first reduce stabilizer testing to the task of distinguishing random stabilizer states from the maximally mixed state. We then argue that, without loss of generality, it is sufficient to consider measurement strategies that a) lie in the commutant of the tensor action of the Clifford group and b) satisfy a Positive Partial Transpose (PPT) condition. By leveraging these constraints, together with novel results on the partial transposes of the generators of the Clifford commutant, we derive the lower bound on the sample complexity.

arXiv:2410.07986•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•18 citations
A multiset of pure quantum states is said to be k-learnable if there is a measurement strategy that always narrows an unknown sample drawn from the list down to one of at most k candidates. The parameter k interpolates between distinguishability and antidistinguishability, and provides a unified framework for partial state identification. We prove two universal, and optimal, Gram-matrix criteria for k-learnability: a Frobenius-norm sufficient condition and an entrywise-ℓ1\ell_1ℓ1​ necessary condition. We apply them to derive explicit learnability and copy-complexity guarantees for several well-known sets of states including SIC-POVMs, mutually unbiased bases, and stabilizer states. We further apply our results to zero-error mutation detection problems such as anomaly detection and changepoint detection.
A set of pure quantum states is said to be antidistinguishable if upon sampling one at random, there exists a measurement to perfectly determine some state that was not sampled. We show that antidistinguishability of a set of n pure states is equivalent to a property of its Gram matrix called ( n − 1 ) -incoherence, thus establishing a connection with quantum resource theories that lets us apply a wide variety of new tools to antidistinguishability. As a particular application of our result, we present an explicit formula (not involving any semidefinite programming) that determines whether or not a set with a circulant Gram matrix is antidistinguishable. We also show that if all inner products are smaller than ( n − 2 ) / ( 2 n − 2 ) then the set must be antidistinguishable, and we show that this bound is tight when n ≤ 4 . We also give a simpler proof that if all the inner products are strictly larger than ( n − 2 ) / ( n − 1 ) , then the set cannot be antidistinguishable, and we show that this bound is tight for all n .
The problem of quantum state classification asks how accurately one can identify an unknown quantum state that is promised to be drawn from a known set of pure states. In this work, we introduce the notion of kkk-learnability, which captures the ability to identify the correct state using at most kkk guesses, with zero error. We show that deciding whether a given family of states is kkk-learnable can be solved via semidefinite programming. When there are nnn states, we present polynomial-time (in nnn) algorithms for determining kkk-learnability for two cases: when kkk is a fixed constant or the dimension of the states is a fixed constant. When both kkk and the dimension of the states are part of the input, we prove that there exist succinct certificates placing the problem in NP, and we establish NP-hardness by a reduction from the classical kkk-clique problem. Together, our findings delineate the boundary between efficiently solvable and intractable instances of quantum state classification in the perfect (zero-error) regime.
We show that the quantum measurement known as the pretty good measurement can be used to identify an unknown quantum state picked from any set of nnn mixed states that have pairwise fidelities upper-bounded by a constant below 1, given O(log⁡n)O(\log n)O(logn) copies of the unknown state, with high success probability in the worst case. If the unknown state is promised to be pure, there is an explicit measurement strategy which solves this worst-case quantum state discrimination problem with O~(∥G∥)\widetilde{O}(\|G\|)O(∥G∥) copies, where GGG is the Gram matrix of the states.
We study the sample complexity of shadow tomography in the high-precision regime under realistic measurement constraints. Given an unknown ddd-dimensional quantum state ρρρ and a known set of observables {Oi}i=1m\{O_i\}_{i=1}^m{Oi​}i=1m​, the goal is to estimate expectation values {tr(Oiρ)}i=1m\{\mathrm{tr}(O_iρ)\}_{i=1}^m{tr(Oi​ρ)}i=1m​ to accuracy εεε in LpL_pLp​-norm, using possibly adaptive measurements that act on O(polylog(d))O(\mathrm{polylog}(d))O(polylog(d)) number of copies of ρρρ at a time. We focus on the regime where εεε is below an instance-dependent threshold. Our main contribution is an instance-optimal characterization of the sample complexity as Θ~(Γp/ε2)\tildeΘ(Γ_p/ε^2)Θ~(Γp​/ε2), where ΓpΓ_pΓp​ is a function of {Oi}i=1m\{O_i\}_{i=1}^m{Oi​}i=1m​ defined via an optimization formula involving the inverse Fisher information matrix. Previously, tight bounds were known only in special cases, e.g. Pauli shadow tomography with L∞L_\inftyL∞​-norm error. Concretely, we first analyze a simpler oblivious variant where the goal is to estimate an observable of the form ∑i=1mαiOi\sum_{i=1}^m α_i O_i∑i=1m​αi​Oi​ with ∥α∥q=1\|α\|_q = 1∥α∥q​=1 (where qqq is dual to ppp) revealed after the measurement. For single-copy measurements, we obtain a sample complexity of Θ(Γpob/ε2)Θ(Γ^{\mathrm{ob}}_p/ε^2)Θ(Γpob​/ε2). We then show Θ~(Γp/ε2)\tildeΘ(Γ_p/ε^2)Θ~(Γp​/ε2) is necessary and sufficient for the original problem, with the lower bound applying to unbiased, bounded estimators. Our upper bounds rely on a two-step algorithm combining coarse tomography with local estimation. Notably, Γ∞ob=Γ∞Γ^{\mathrm{ob}}_\infty = Γ_\inftyΓ∞ob​=Γ∞​. In both cases, allowing ccc-copy measurements improves the sample complexity by at most Ω(1/c)Ω(1/c)Ω(1/c). Our results establish a quantitative correspondence between quantum learning and metrology, unifying asymptotic metrological limits with finite-sample learning guarantees.
Abstract Suppose we have many copies of an unknown n -qubit state . We measure some copies of using a known two-outcome measurement E 1 , then other copies using a measurement E 2 , and so on. At each stage t , we generate a current hypothesis about the state , using the outcomes of the previous measurements. We show that it is possible to do this in a way that guarantees that , the error in our prediction for the next measurement, is at least at most times. Even in the ‘non-realizable’ setting—where there could be arbitrary noise in the measurement outcomes—we show how to output hypothesis states that incur at most excess loss over the best possible state on the first T measurements. These results generalize a 2007 theorem by Aaronson on the PAC-learnability of quantum states, to the online and regret-minimization settings. We give three different ways to prove our results—using convex optimization, quantum postselection, and sequential fat-shattering dimension—which have different advantages in terms of parameters and portability.
We consider the problem of testing whether an unknown nnn-qubit quantum state ∣ψ⟩|ψ\rangle∣ψ⟩ is a stabilizer state, with only single-copy access. We give an algorithm solving this problem using O(n)O(n)O(n) copies, and conversely prove that Ω(n)Ω(\sqrt{n})Ω(n​) copies are required for any algorithm. The main observation behind our algorithm is that when repeatedly measuring in a randomly chosen stabilizer basis, stabilizer states are the most likely among the set of all pure states to exhibit linear dependencies in measurement outcomes. Our algorithm is designed to probe deviations from this extremal behavior. For the lower bound, we first reduce stabilizer testing to the task of distinguishing random stabilizer states from the maximally mixed state. We then argue that, without loss of generality, it is sufficient to consider measurement strategies that a) lie in the commutant of the tensor action of the Clifford group and b) satisfy a Positive Partial Transpose (PPT) condition. By leveraging these constraints, together with novel results on the partial transposes of the generators of the Clifford commutant, we derive the lower bound on the sample complexity.