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.
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 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 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.
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(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∥) copies, where G 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 d-dimensional quantum state ρ and a known set of observables {Oi}i=1m, the goal is to estimate expectation values {tr(Oiρ)}i=1m to accuracy ε in Lp-norm, using possibly adaptive measurements that act on 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), where Γp is a function of {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∞-norm error. Concretely, we first analyze a simpler oblivious variant where the goal is to estimate an observable of the form ∑i=1mαiOi with ∥α∥q=1 (where q is dual to p) revealed after the measurement. For single-copy measurements, we obtain a sample complexity of Θ(Γpob/ε2). We then show Θ~(Γ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=Γ∞. 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.
We consider the problem of testing whether an unknown n-qubit quantum state ∣ψ⟩ is a stabilizer state, with only single-copy access. We give an algorithm solving this problem using O(n) copies, and conversely prove that Ω(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.
The sample complexity of identifying an unknown pure stabilizer state has been a longstanding problem in quantum information. In this paper, we resolve the entire exact critical crossover for the uniform ensemble of pure n-qubit stabilizer states under arbitrary collective measurements and without side information. For k=n+c, with fixed integer c, the optimal success probability converges to an explicit positive series P∞(c). In particular, P∞(0)=0.1760837896…, while its two tails obey a quadratic-exponential law below threshold and 1−P∞(c)∼2−c above threshold. The pretty-good measurement is exactly optimal for every finite n and k. The proof diagonalizes the stabilizer Gram operator through Clifford tensor-power duality and a defect filtration, including the exceptional binary sectors. The resulting integer-scale law quantifies the n+O(1) copy threshold.