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

arXiv:2209.11225 · Communications in Mathematical Physics

Quantum Theory in Finite Dimension Cannot Explain Every General Process with Finite Memory

Marco Fanizza, Josep Lumbreras, Andreas Winter

Published Feb 1, 2024• 4 citations
arXivHTMLPDF

Abstract

Abstract Arguably, the largest class of stochastic processes generated by means of a finite memory consists of those that are sequences of observations produced by sequential measurements in a suitable generalized probabilistic theory (GPT). These are constructed from a finite-dimensional memory evolving under a set of possible linear maps, and with probabilities of outcomes determined by linear functions of the memory state. Examples of such models are given by classical hidden Markov processes, where the memory state is a probability distribution, and at each step it evolves according to a non-negative matrix, and hidden quantum Markov processes, where the memory is a finite-dimensional quantum system, and at each step it evolves according to a completely positive map. Here we show that the set of processes admitting a finite-dimensional explanation do not need to be explainable in terms of either classical probability or quantum mechanics. To wit, we exhibit families of processes that have a finite-dimensional explanation, defined manifestly by the dynamics of an explicitly given GPT, but that do not admit a quantum, and therefore not even classical, explanation in finite dimension. Furthermore, we present a family of quantum processes on qubits and qutrits that do not admit a classical finite-dimensional realization, which includes examples introduced earlier by Fox, Rubin, Dharmadikari and Nadkarni as functions of infinite-dimensional Markov chains, and lower bound the size of the memory of a classical model realizing a noisy version of the qubit processes.

DOI
10.1007/s00220-023-04913-4

Related papers

Interpreting Quantum Learning Models via Stochastic Processes

Johannes Fankhauser, Lukas J. Fiderer, Hans J. Briegel

Quantum machine learning models define probabilistic input--output maps through coherent quantum evolution and measurement. While such models can exhibit computational advantages, their internal functioning and decision making generally resists interpretation in terms of stochastic trajectories through intermediate configurations. In contrast to classical (Markovian) stochastic processes, quantum dynamics generically violates the Chapman--Kolmogorov divisibility condition, preventing a decomposition into probabilistically meaningful intermediate transitions. We develop a probabilistic framework for representing quantum learning models as stochastic processes over configuration spaces where the dynamics are modeled as linear maps on probability distributions. Starting from a fixed POVM, arbitrary quantum channels induce transition kernels on the associated probability representation. For informationally complete POVMs, and in particular SIC-POVMs, these kernels are Markovian but generally quasi-stochastic, with non-classicality appearing as negativity. By contrast, projective spaces admit positive stochastic kernels but generally require non-Markovian dynamics due to the failure of Chapman--Kolmogorov divisibility. This yields a trade-off between negativity and dependence on past configurations, i.e. quantum dynamics can be represented either by Markovian quasi-stochastic maps or by positive stochastic processes with higher Markov order. We discuss how such representations of quantum dynamics can be interpreted as stochastic walks through a memory space in the spirit of Projective Simulation, a model of learning and agency in which decisions arise from random walks over an episodic memory network. We further outline how finite-order stochastic kernels can approximate such quantum deliberation processes and show in what regimes the classical machine learning model is recovered.

quant-pharXiv:2607.17327•Jul 21, 2026•0 citations

Quantum learning of classical stochastic processes: The completely positive realization problem

Alex Monràs, Andreas Winter

Among several tasks in Machine Learning, a specially important one is the problem of inferring the latent variables of a system and their causal relations with the observed behavior. A paradigmatic instance of this is the task of inferring the hidden Markov model underlying a given stochastic process. This is known as the positive realization problem (PRP), [L. Benvenuti and L. Farina, IEEE Trans. Autom. Control 49(5), 651–664 (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. We consider the scenario where the latent variables are quantum (i.e., 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 of 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 [M. Guţă, Phys. Rev. A 83(6), 062324 (2011); M. Guţă and N. Yamamoto, e-print arXiv:1303.3771(2013)].

arXiv:1412.3634•Journal of Mathematical Physics•Jan 1, 2016•21 citations

Hidden quantum Markov processes

Luigi Accardi, El Gheteb Soueidi, Yun Gang Lu +1 more

Starting from the notion of algebraic hidden processes introduced in Ref. 9 , we propose a definition of quantum hidden Markov process which extends the notion of quantum Markov chain (QMC) in the same sense in which classical hidden Markov processes (HMPs) extend classical Markov chains. We give several structure theorems for this new family of quantum states which shares with the QMCs the unique property that the finite dimensional joint expectations are explicitly given without these states being linearly equivalent to product states (as the Gaussian ones). The special feature of this new class of quantum states is best exemplified by looking at their restrictions to diagonal sub-algebras: we prove that they lead to a new family of classical stochastic processes that generalize in a non-trivial way the classical HMPs.

Infinite Dimensional Analysis Quantum Probability and Related Topics•May 9, 2024•9 citations

Memory effects in quantum processes

Philip Taranto

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.

arXiv:1909.05245•International Journal of Quantum Information•Jan 7, 2020•12 citations

Structure of quantum stochastic processes with finite Markov order

Philip Taranto, Simon Milz, Felix A. Pollock +1 more

Non-Markovian quantum processes exhibit different memory effects when measured in different ways; an unambiguous characterization of memory length requires accounting for the sequence of instruments applied to probe the system dynamics. This instrument-specific notion of quantum Markov order displays stark differences to its classical counterpart. Here, we explore the structure of quantum stochastic processes with finite memory length in detail. We begin by examining a generalized collision model with memory, before framing this instance within the general theory. We detail the constraints that are placed on the underlying system-environment dynamics for a process to exhibit finite Markov order with respect to natural classes of probing instruments, including deterministic (unitary) operations and sequences of generalized quantum measurements with informationally complete repreparations. Lastly, we show how processes with vanishing quantum conditional mutual information form a special case of the theory. Throughout, we provide a number of representative, pedagogical examples to display the salient features of memory effects in quantum processes.

arXiv:1810.10809•Physical Review A•Apr 9, 2019•65 citations

Witnessing Quantum Bayesian Inference beyond Classical Learning

Francesco Buscemi

Can an agent's predictions reveal whether its reasoning is based on a classical or a quantum model? Using known results on matrix factorizations, here we show that quantum Bayesian retrodiction can produce one-step-ahead forecasts incompatible with every classical Bayesian explanation based on learning about a fixed but unknown sampling law from conditionally independent observations. The separation has a sharp threshold in the number of outcomes: for any measurement with at most four outcomes, the quantum predictions admit a classical realization, irrespective of the prior state and the finite Hilbert-space dimension, whereas a five-outcome measurement on a single qubit already violates an explicit classical bound. This bound holds for arbitrary classical latent states, prior probabilities, and sampling laws, and involves only the agent's initial and updated predictions. Thus, in this setting, quantum Bayesian retrodiction is strictly more expressive than classical Bayesian learning, and this difference can be witnessed without observing or specifying the agent's internal description.

quant-pharXiv:2610.09293•Oct 8, 2026•0 citations
Abstract Arguably, the largest class of stochastic processes generated by means of a finite memory consists of those that are sequences of observations produced by sequential measurements in a suitable generalized probabilistic theory (GPT). These are constructed from a finite-dimensional memory evolving under a set of possible linear maps, and with probabilities of outcomes determined by linear functions of the memory state. Examples of such models are given by classical hidden Markov processes, where the memory state is a probability distribution, and at each step it evolves according to a non-negative matrix, and hidden quantum Markov processes, where the memory is a finite-dimensional quantum system, and at each step it evolves according to a completely positive map. Here we show that the set of processes admitting a finite-dimensional explanation do not need to be explainable in terms of either classical probability or quantum mechanics. To wit, we exhibit families of processes that have a finite-dimensional explanation, defined manifestly by the dynamics of an explicitly given GPT, but that do not admit a quantum, and therefore not even classical, explanation in finite dimension. Furthermore, we present a family of quantum processes on qubits and qutrits that do not admit a classical finite-dimensional realization, which includes examples introduced earlier by Fox, Rubin, Dharmadikari and Nadkarni as functions of infinite-dimensional Markov chains, and lower bound the size of the memory of a classical model realizing a noisy version of the qubit processes.
Quantum machine learning models define probabilistic input--output maps through coherent quantum evolution and measurement. While such models can exhibit computational advantages, their internal functioning and decision making generally resists interpretation in terms of stochastic trajectories through intermediate configurations. In contrast to classical (Markovian) stochastic processes, quantum dynamics generically violates the Chapman--Kolmogorov divisibility condition, preventing a decomposition into probabilistically meaningful intermediate transitions. We develop a probabilistic framework for representing quantum learning models as stochastic processes over configuration spaces where the dynamics are modeled as linear maps on probability distributions. Starting from a fixed POVM, arbitrary quantum channels induce transition kernels on the associated probability representation. For informationally complete POVMs, and in particular SIC-POVMs, these kernels are Markovian but generally quasi-stochastic, with non-classicality appearing as negativity. By contrast, projective spaces admit positive stochastic kernels but generally require non-Markovian dynamics due to the failure of Chapman--Kolmogorov divisibility. This yields a trade-off between negativity and dependence on past configurations, i.e. quantum dynamics can be represented either by Markovian quasi-stochastic maps or by positive stochastic processes with higher Markov order. We discuss how such representations of quantum dynamics can be interpreted as stochastic walks through a memory space in the spirit of Projective Simulation, a model of learning and agency in which decisions arise from random walks over an episodic memory network. We further outline how finite-order stochastic kernels can approximate such quantum deliberation processes and show in what regimes the classical machine learning model is recovered.
Among several tasks in Machine Learning, a specially important one is the problem of inferring the latent variables of a system and their causal relations with the observed behavior. A paradigmatic instance of this is the task of inferring the hidden Markov model underlying a given stochastic process. This is known as the positive realization problem (PRP), [L. Benvenuti and L. Farina, IEEE Trans. Autom. Control 49(5), 651–664 (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. We consider the scenario where the latent variables are quantum (i.e., 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 of 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 [M. Guţă, Phys. Rev. A 83(6), 062324 (2011); M. Guţă and N. Yamamoto, e-print arXiv:1303.3771(2013)].
Starting from the notion of algebraic hidden processes introduced in Ref. 9 , we propose a definition of quantum hidden Markov process which extends the notion of quantum Markov chain (QMC) in the same sense in which classical hidden Markov processes (HMPs) extend classical Markov chains. We give several structure theorems for this new family of quantum states which shares with the QMCs the unique property that the finite dimensional joint expectations are explicitly given without these states being linearly equivalent to product states (as the Gaussian ones). The special feature of this new class of quantum states is best exemplified by looking at their restrictions to diagonal sub-algebras: we prove that they lead to a new family of classical stochastic processes that generalize in a non-trivial way the classical HMPs.
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.
Non-Markovian quantum processes exhibit different memory effects when measured in different ways; an unambiguous characterization of memory length requires accounting for the sequence of instruments applied to probe the system dynamics. This instrument-specific notion of quantum Markov order displays stark differences to its classical counterpart. Here, we explore the structure of quantum stochastic processes with finite memory length in detail. We begin by examining a generalized collision model with memory, before framing this instance within the general theory. We detail the constraints that are placed on the underlying system-environment dynamics for a process to exhibit finite Markov order with respect to natural classes of probing instruments, including deterministic (unitary) operations and sequences of generalized quantum measurements with informationally complete repreparations. Lastly, we show how processes with vanishing quantum conditional mutual information form a special case of the theory. Throughout, we provide a number of representative, pedagogical examples to display the salient features of memory effects in quantum processes.
Can an agent's predictions reveal whether its reasoning is based on a classical or a quantum model? Using known results on matrix factorizations, here we show that quantum Bayesian retrodiction can produce one-step-ahead forecasts incompatible with every classical Bayesian explanation based on learning about a fixed but unknown sampling law from conditionally independent observations. The separation has a sharp threshold in the number of outcomes: for any measurement with at most four outcomes, the quantum predictions admit a classical realization, irrespective of the prior state and the finite Hilbert-space dimension, whereas a five-outcome measurement on a single qubit already violates an explicit classical bound. This bound holds for arbitrary classical latent states, prior probabilities, and sampling laws, and involves only the agent's initial and updated predictions. Thus, in this setting, quantum Bayesian retrodiction is strictly more expressive than classical Bayesian learning, and this difference can be witnessed without observing or specifying the agent's internal description.