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

On the distinguishability of random quantum states

Ashley Montanaro

Published Jan 1, 2006• 42 citations
OpenAlex

Abstract

We develop two analytic lower bounds on the probability of success p of identifying a state picked from a known ensemble of pure states: a bound based on the pairwise inner products of the states, and a bound based on the eigenvalues of their Gram matrix. We use the latter to lower bound the asymptotic distinguishability of ensembles of n random quantum states in d dimensions, where n/d approaches a constant. In particular, for almost all ensembles of n states in n dimensions, p>0.72. An application to distinguishing Boolean functions (the "oracle identification problem") in quantum computation is given.

Related papers

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•4 citations

Entropic Lower Bound for Distinguishability of Quantum States

Seung-Ho Yang, Jinhyoung Lee, Hyunseok Jeong

For a system randomly prepared in a number of quantum states, we present a lower bound for the distinguishability of the quantum states, that is, the success probability of determining the states in the form of entropy. When the states are all pure, acquiring the entropic lower bound requires only the density operator and the number of the possible states. This entropic bound shows a relation between the von Neumann entropy and the distinguishability.

•Jan 1, 2015•2 citations

Sharp bounds for perfect quantum state classification beyond antidistinguishability

Nathaniel Johnston, Benjamin Lovitz, Vincent Russo +1 more

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.

quant-pharXiv:2609.17411•Sep 16, 2026•0 citations

Entropic Lower Bound for Distinguishability of Quantum States

Seungho Yang, Jinhyoung Lee, Hyunseok Jeong

For a system randomly prepared in a number of quantum states, we present a lower bound for the distinguishability of the quantum states, that is, the success probability of determining the states in the form of entropy. When the states are all pure, acquiring the entropic lower bound requires only the density operator and the number of the possible states. This entropic bound shows a relation between the von Neumann entropy and the distinguishability.

arXiv:1511.02309•Advances in Mathematical Physics•Jan 1, 2015•0 citations

Distinguishability of states and von Neumann entropy

Richard Jozsa, J. Schlienz

Let ${|{\ensuremath{\psi}}_{1}〉,\dots{},|{\ensuremath{\psi}}_{n}〉{;p}_{1},\dots{}{,p}_{n}}$ be an ensemble of pure quantum states. We show that it is possible to increase all of the pairwise overlaps $|〈{\ensuremath{\psi}}_{i}|{\ensuremath{\psi}}_{j}〉|,$ i.e., make each constituent pair of the states more parallel (while keeping the prior probabilities the same), in such a way that the von Neumann entropy S is increased, and dually, make all pairs more orthogonal while decreasing S. We show that this phenomenon cannot occur for ensembles in two dimensions but that it is a feature of almost all ensembles of three states in three dimensions. It is known that the von Neumann entropy characterizes the classical and quantum information capacities of the ensemble and we argue that information capacity, in turn, is a manifestation of the distinguishability of the signal states. Hence, our result shows that the notion of distinguishability within an ensemble is a global property that cannot be reduced to considering distinguishability of each constituent pair of states.

arXiv:quant-ph/9911009•Physical Review A•Jun 5, 2000•101 citations

Bound on the number of functions that can be distinguished with k quantum queries

Edward Farhi, Jeffrey Goldstone, Sam Gutmann +1 more

Suppose an oracle is known to hold one of a given set of D two-valued functions. To successfully identify which function the oracle holds with k classical queries, it must be the case that D is at most ${2}^{k}.$ In this paper we derive a bound for how many functions can be distinguished with k quantum queries.

arXiv:quant-ph/9901012•Physical Review A•Dec 1, 1999•25 citations
We develop two analytic lower bounds on the probability of success p of identifying a state picked from a known ensemble of pure states: a bound based on the pairwise inner products of the states, and a bound based on the eigenvalues of their Gram matrix. We use the latter to lower bound the asymptotic distinguishability of ensembles of n random quantum states in d dimensions, where n/d approaches a constant. In particular, for almost all ensembles of n states in n dimensions, p>0.72. An application to distinguishing Boolean functions (the "oracle identification problem") in quantum computation is given.
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.
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.
Let ${|{\ensuremath{\psi}}_{1}〉,\dots{},|{\ensuremath{\psi}}_{n}〉{;p}_{1},\dots{}{,p}_{n}}$ be an ensemble of pure quantum states. We show that it is possible to increase all of the pairwise overlaps $|〈{\ensuremath{\psi}}_{i}|{\ensuremath{\psi}}_{j}〉|,$ i.e., make each constituent pair of the states more parallel (while keeping the prior probabilities the same), in such a way that the von Neumann entropy S is increased, and dually, make all pairs more orthogonal while decreasing S. We show that this phenomenon cannot occur for ensembles in two dimensions but that it is a feature of almost all ensembles of three states in three dimensions. It is known that the von Neumann entropy characterizes the classical and quantum information capacities of the ensemble and we argue that information capacity, in turn, is a manifestation of the distinguishability of the signal states. Hence, our result shows that the notion of distinguishability within an ensemble is a global property that cannot be reduced to considering distinguishability of each constituent pair of states.
Suppose an oracle is known to hold one of a given set of D two-valued functions. To successfully identify which function the oracle holds with k classical queries, it must be the case that D is at most 2k.{2}^{k}.2k. In this paper we derive a bound for how many functions can be distinguished with k quantum queries.