We consider online detection strategies for identifying a change point in a stream of quantum particles allegedly prepared in identical states. We show that the identification of the change point can be done without error via sequential local measurements while attaining the optimal performance bound set by quantum mechanics. In this way, we establish the task of exactly identifying a quantum change point as an instance where local protocols are as powerful as global ones. The optimal online detection strategy requires only one bit of memory between subsequent measurements, and it is amenable to experimental realization with current technology.
We consider online detection strategies for identifying a change point in a stream of quantum particles allegedly prepared in identical states. We show that the identification of the change point can be done without error via sequential local measurements while attaining the optimal performance bound set by quantum mechanics. In this way, we establish the task of exactly identifying a quantum change point as an instance where local protocols are as powerful as global ones. The optimal online detection strategy requires only one bit of memory between subsequent measurements, and it is amenable to experimental realization with current technology.
The detection of change points is a pivotal task in statistical analysis. In the quantum realm, it is a new primitive where one aims at identifying the point where a source that supposedly prepares a sequence of particles in identical quantum states starts preparing a mutated one. We obtain the optimal procedure to identify the change point with certainty-naturally at the price of having a certain probability of getting an inconclusive answer. We obtain the analytical form of the optimal probability of successful identification for any length of the particle sequence. We show that the conditional success probabilities of identifying each possible change point show an unexpected oscillatory behavior. We also discuss local (online) protocols and compare them with the optimal procedure.
Sudden changes are ubiquitous in nature. Identifying them is crucial for a number of applications in biology, medicine, and social sciences. Here we take the problem of detecting sudden changes to the quantum domain. We consider a source that emits quantum particles in a default state, until a point where a mutation occurs that causes the source to switch to another state. The problem is then to find out where the change occurred. We determine the maximum probability of correctly identifying the change point, allowing for collective measurements on the whole sequence of particles emitted by the source. Then, we devise online strategies where the particles are measured individually and an answer is provided as soon as a new particle is received. We show that these online strategies substantially underperform the optimal quantum measurement, indicating that quantum sudden changes, although happening locally, are better detected globally.
Detecting abrupt changes in data streams is crucial because they are often triggered by events that have important consequences if left unattended. Quickest change-point detection has become a vital sequential analysis primitive that aims at designing procedures that minimize the expected detection delay of a change subject to a bounded expected false alarm time. We put forward the quantum counterpart of this fundamental primitive on streams of quantum data. We give a lower bound on the mean minimum delay when the expected time of a false alarm is asymptotically large, under the most general quantum detection strategy, which is given by a sequence of adaptive collective (potentially weak) measurements on the growing string of quantum data. In addition, we give particular strategies based on repeated measurements on independent blocks of samples that asymptotically attain the lower bound and thereby establish the ultimate quantum limit for quickest change-point detection. Finally, we discuss online change-point detection in quantum channels.
Detecting a change point is a crucial task in statistics that has been recently extended to the quantum realm. A source state generator that emits a series of single photons in a default state suffers an alteration at some point and starts to emit photons in a mutated state. The problem consists in identifying the point where the change took place. In this Rapid Communication, we build a pseudo-on-demand single-photon source to prepare the photon sequences, and consider a learning agent that applies Bayesian inference on experimental data to solve this problem. This learning machine adjusts the measurement over each photon according to the past experimental results and finds the change position in an online fashion. Our results show that the local-detection success probability can be largely improved by using such a machine-learning technique. This protocol provides a tool for improvement in many applications where a sequence of identical quantum states is required.
Online learning is a framework for interfacing with environments whose structure is revealed through interactions; quantum information theory is a means of representing data and its processing consistent with modern understanding of physics. Their union is symbiotic---sequential processing is light on precious quantum resources, and quantum algorithms can surpass known bounds of classical algorithms---their combination being an area of independent interest. This thesis aims to exemplify the above point via five case studies on tomography, change detection, and function evaluation. In the process of deriving efficient tomography procedures, prior work has shown that quantum states can be learned in online adversarial environments. We extend this notion to subsets of positive semidefinite operators, including general quantum objects such as states, measurements, channels, strategies, co-strategies, and Gram matrices. We tailor a regularized follow-the-leader algorithm and achieve sublinear regret. As a byproduct, we show a generalization of Pinsker's inequality that accounts for differences in trace, its proof method more broadly applicable to general divergences. We further extend online learnability to objects in arbitrary physical theories. We derive mappings between Euclidean Jordan algebras and generalized probabilistic theories, using methods for the former to show that states in the latter are learnable. Specifically, we develop a projective version of the symmetric cone multiplicative weights update algorithm that achieves sublinear regret when learning states of generalized probabilistic theories. We consider the task of detecting changes in sequences of unknown quantum states with a constraint of no false positives, developing efficient and optimal online quantum algorithms. These include online algorithms with small amounts of quantum memory based on the swap test, and optimal algorithms projecting onto the symmetric subspace. We find circuit constructions for these algorithms, analyze their complexity, and show their equivalence under certain memory limitations. The proposed algorithms are applicable to quality control and anomaly detection in quantum devices, and may be of independent interest for identity testing and optimal cloning. We elaborate on the quality control aspect of changepoint methods by developing procedures for aiding the calibration of near-term quantum devices. These consist of algorithms for certification and changepoint detection in Hamiltonian dynamics, which enable continuous monitoring and trigger recalibration procedures. Using a cumulative sum procedure, we attain an asymptotically-optimal scaling of the average times to detection versus false positive, dependent primarily on Hamiltonian norm bounds. Lastly, we quantify the effect of memory limits on Boolean function evaluation of quantum sequences---a task applicable to distributed sensing and quantum reading of classical memories, among others. We show that minimum-error function evaluation in the memoryless regime is equivalent to the so-called pretty good measurement and hence shares its performance guarantee. Additionally, we characterize the precise set of functions on which this strategy performs optimally---affine functions. The above studies reveal insights about learnability as a universal property and the tradeoffs between performance and resource requirements in online settings, informing the choice of quantum settings best-suited for online learning. We conclude by summarizing these takeaways, along with listing remaining open questions.
We consider online strategies for discriminating between symmetric pure states with zero error when n copies of the states are provided. Optimized online strategies involve local, possibly adaptive measurements on each copy and are optimal at each step, which makes them robust in front of particle losses or an abrupt termination of the discrimination process. We first review previous results on binary minimum and zero error discrimination with local measurements that achieve the maximum success probability set by optimizing over global measurements, highlighting their online features. We then extend these results to the case of zero error identification of three symmetric states with constant overlap. We provide optimal online schemes that attain global performance for any n if the state overlaps are positive, and for odd n if overlaps have a negative value. For arbitrary complex overlaps, we show compelling evidence that online schemes fail to reach optimal global performance. The online schemes that we describe only require to store the last outcome obtained in a classical memory, and adaptiveness of the measurements reduce to at most two changes, regardless of the value of n .