Abstract Stochastic processes abound in nature and accurately modeling them is essential across the quantitative sciences. They can be described by hidden Markov models or by their quantum extensions. These models explain and give rise to process outputs in terms of an observed system interacting with an unobserved memory. Although there are infinitely many models that can generate a given process, they can vary greatly in their memory requirements. It is therefore of great fundamental and practical importance to identify memory-minimal models. This task is known to be hard in general, due to both the number of generating models, and the lack of invariant features that determine elements of the set. In general, it is forbiddingly difficult to ascertain that a given model is minimal. Addressing this challenge, we here identify spectral invariants of a process that can be calculated from any model that generates it. This allows us to determine strict bounds on the quantum generative complexity of the process—its minimal memory requirement. We then show that the bound is raised quadratically when we restrict to classical operations. This is an entirely quantum-coherent effect, as we express precisely, using the resource theory of coherence. Finally, we demonstrate that the classical bound can be violated by quantum models.
Abstract Stochastic processes abound in nature and accurately modeling them is essential across the quantitative sciences. They can be described by hidden Markov models or by their quantum extensions. These models explain and give rise to process outputs in terms of an observed system interacting with an unobserved memory. Although there are infinitely many models that can generate a given process, they can vary greatly in their memory requirements. It is therefore of great fundamental and practical importance to identify memory-minimal models. This task is known to be hard in general, due to both the number of generating models, and the lack of invariant features that determine elements of the set. In general, it is forbiddingly difficult to ascertain that a given model is minimal. Addressing this challenge, we here identify spectral invariants of a process that can be calculated from any model that generates it. This allows us to determine strict bounds on the quantum generative complexity of the process—its minimal memory requirement. We then show that the bound is raised quadratically when we restrict to classical operations. This is an entirely quantum-coherent effect, as we express precisely, using the resource theory of coherence. Finally, we demonstrate that the classical bound can be violated by quantum models.
To make sense of the world around us, we develop models, constructed to enable us to replicate, describe, and explain the behaviours we see. Focusing on the broad case of sequences of correlated random variables, i.e., classical stochastic processes, we tackle the question of determining whether or not two different models produce the same observable behavior. This is the problem of identifiability. Curiously, the physics of the model need not correspond to the physics of the observations; recent work has shown that it is even advantageous -- in terms of memory and thermal efficiency -- to employ quantum models to generate classical stochastic processes. We resolve the identifiability problem in this regime, providing a means to compare any two models of a classical process, be the models classical, quantum, or `post-quantum', by mapping them to a canonical `generalized' hidden Markov model. Further, this enables us to place (sometimes tight) bounds on the minimal dimension required of a quantum model to generate a given classical stochastic process.
What makes one quantum process more complex than another? We adopt an operational approach inspired by classical complexity science, which characterises structure through the memory required for causal generation. We develop a fully-quantum extension of computational mechanics for quantum space series: Correlated sequences of quantum outputs that do not return to interact with their generator. For stationary, memoryful quantum space series admitting finite-dimensional, primitive causal models, we show that any memory-minimal causal generator can be chosen to produce outputs isometrically, without a discarded environment. The resulting canonical matrix product state representation uniquely determines the irreducible memory required for generation. In particular, the minimum memory entropy is exactly the entanglement entropy across the past-future bipartition, giving entanglement a direct operational interpretation as irreducible memory for causal generation. The same structure determines the minimum memory dimension through the corresponding Schmidt rank. Within this class, we further show that the fundamental entropy rate vanishes, that causal generation is symmetric under time reversal, and that all memoryful processes possess infinite quantum Markov order with respect to arbitrary sharp measurements. These results establish an operational framework for quantifying intrinsic quantum structure, revealing deep connections between causal generation, complexity, memory, entropy, and entanglement.
Understanding temporal processes and their correlations in time is of paramount importance for the development of near-term technologies that operate under realistic conditions. Capturing the complete multi-time statistics that define a stochastic process lies at the heart of any proper treatment of memory effects. This is well understood in classical theory, where a hierarchy of joint probability distributions completely characterizes the process at hand. However, attempting to generalize this notion to quantum mechanics is problematic: observing realizations of a quantum process necessarily disturbs the state of the system, breaking an implicit, and crucial, assumption in the classical setting. This issue can be overcome by separating the experimental interventions from the underlying process, enabling an unambiguous description of the process itself and accounting for all possible multi-time correlations for any choice of interrogating instruments. In this paper, using a novel framework for the characterization of quantum stochastic processes, we first solve the long standing question of unambiguously describing the memory length of a quantum processes. This is achieved by constructing a quantum Markov order condition, which naturally generalizes its classical counterpart for the quantification of finite-length memory effects. As measurements are inherently invasive in quantum mechanics, one has no choice but to define Markov order with respect to the interrogating instruments that are used to probe the process at hand: different memory effects are exhibited depending on how one addresses the system, in contrast to the standard classical setting. We then fully characterize the structural constraints imposed on quantum processes with finite Markov order, shedding light on a variety of memory effects that can arise through various examples. Finally, we introduce an instrument-specific notion of memory strength that allows for a meaningful quantification of the temporal correlations between the history and the future of a process for a given choice of experimental intervention. These findings are directly relevant to both characterizing and exploiting memory effects that persist for a finite duration. In particular, immediate applications range from developing efficient compression and recovery schemes for the description of quantum processes with memory to designing coherent control protocols that efficiently perform information-theoretic tasks, amongst a plethora of others.
Among several tasks in Machine Learning, is the problem of inferring the latent variables of a system and their causal relations with the observed behavior. A paradigmatic instance of such problem is the task of inferring the Hidden Markov Model underlying a given stochastic process. This is known as the positive realization problem (PRP) [Benvenuti,Farina(2004)] and constitutes a central problem in machine learning. The PRP and its solutions have far-reaching consequences in many areas of systems and control theory, and is nowadays an important piece in the broad field of positive systems theory [Luenberger(1979)]. We consider the scenario where the latent variables are quantum (e.g., quantum states of a finite-dimensional system), and the system dynamics is constrained only by physical transformations on the quantum system. The observable dynamics is then described by a quantum instrument, and the task is to determine which quantum instrument-if any-yields the process at hand by iterative application. We take as a starting point the theory of quasi-realizations, whence a description of the dynamics of the process is given in terms of linear maps on state vectors and probabilities are given by linear functionals on the state vectors. This description, despite its remarkable resemblance with the Hidden Markov Model, or the iterated quantum instrument, is however devoid from any stochastic or quantum mechanical interpretation, as said maps fail to satisfy any positivity conditions. The Completely-Positive realization problem then consists in determining whether an equivalent quantum mechanical description of the same process exists. We generalize some key results of stochastic realization theory, and show that the problem has deep connections with operator systems theory, giving possible insight to the lifting problem in quotient operator systems. Our results have potential applications in quantum machine learning, device-independent characterization and reverse-engineering of stochastic processes and quantum processors, and more generally, of dynamical processes with quantum memory [Guta(2011), Guta&Yamamoto(2013)].
Stochastic modeling is an essential component of the quantitative sciences, with hidden Markov models (HMMs) often playing a central role. Concurrently, the rise of quantum technologies promises a host of advantages in computational problems, typically in terms of the scaling of requisite resources such as time and memory. HMMs are no exception to this, with recent results highlighting quantum implementations of deterministic HMMs exhibiting superior memory and thermal efficiency relative to their classical counterparts. In many contexts, however, nondeterministic HMMs are viable alternatives; compared to them, the advantages of current quantum implementations do not always hold. Here, we provide a systematic prescription for constructing quantum implementations of nondeterministic HMMs that reestablish the quantum advantages against this broader class. Crucially, we show that whenever the classical implementation suffers from thermal dissipation due to its need to process information in a time-local manner, our quantum implementations will both mitigate some of this dissipation and achieve an advantage in memory compression.
Among the predictive hidden Markov models that describe a given stochastic process, the ϵ-machine is strongly minimal in that it minimizes every Rényi-based memory measure. Quantum models can be smaller still. In contrast with the ϵ-machine ’s unique role in the classical setting, however, among the class of processes described by pure-state hidden quantum Markov models, there are those for which there does not exist any strongly minimal model. Quantum memory optimization then depends on which memory measure best matches a given problem’s circumstance.