Quantum multi-anomaly detection

A source assumed to prepare a specified reference state sometimes prepares an anomalous one. We address the task of identifying these anomalous states in a series of n preparations with k anomalies. We analyze the minimum-error protocol and the zero-error (unambiguous) protocol and obtain closed expressions for the success probability when both reference and anomalous states are known to the observer and anomalies can appear equally likely in any position of the preparation series. We find the solution using results from association schemes theory, thus establishing a connection between graph theory and quantum hypothesis testing. In particular, we use the Johnson association scheme which arises naturally from the Gram matrix of this problem. We also study the regime of large n and obtain the expression of the success probability that is non-vanishing. Finally, we address the case in which the observer is blind to the reference and the anomalous states. This scenario requires a universal protocol for which we prove that in the asymptotic limit, the success probability corresponds to the average of the known state scenario.