Solomonoff's universal inductive inference [Inf. Control. 1964] is one of the most general frameworks for learning from sequential data and predicting future observations. It provides prediction guarantees for any computable stochastic source. We ask whether an analogous universal theory of induction can be developed for quantum systems. To this end, we introduce universal quantum inductive inference, a framework for learning and predicting quantum sources that may exhibit arbitrary correlations and entanglement across time. Given the outcomes of past measurements and the corresponding post-measurement quantum systems, the learner produces a joint state that predicts the next measurement outcome and post-measurement system while preserving correlations with the past systems. We model a quantum source as a multipartite quantum state whose description is generated by an unknown $s$-bit program within a given time bound. The learner is required to produce a state that is $ε$-close in trace distance to the target with probability at least $1-δ$. We establish an information-theoretic inference algorithm with round complexity $O(sε^{-2}δ^{-1})$. We further prove a matching lower bound in the relevant parameter regime, even for classical sources. As a second result, we construct a non-i.i.d. state tomography algorithm that outputs a classical description of the conditional state of the next system given past measurement outcomes. Our information-theoretic tomography algorithm achieves round complexity $O(sn^2ε^{-4}δ^{-2})$, where $n$ is the number of qubits received in each round. Finally, we investigate the computational hardness of universal quantum inductive inference under quantum cryptographic assumptions.
AI Summary
The paper asks whether Solomonoff-style prediction extends to quantum sources with arbitrary temporal correlations and entanglement. A source is an $mn$-qubit state whose preparation circuit is generated within time $t$ by an unknown program of length at most $s$. Given measurement history and one copy of the retained post-measurement prefix, the learner must produce a joint state approximating the next measurement outcome, next post-measurement system, and their correlations with the past.
An information-theoretic learner achieves trace-distance error $\epsilon$ with probability at least $1-\delta$ using $O(s\epsilon^{-2}\delta^{-1})$ rounds, independent of register size $n$ and preparation-time bound $t$. The construction combines a time-bounded universal density matrix with an averaged rotated Petz recovery map. Universal domination bounds total relative entropy by $O(s)$; telescoping recovery inequalities bound cumulative squared prediction error. A classical lower bound matches this scaling in the stated parameter regime.
A separate non-i.i.d. tomography procedure outputs a classical description of the next conditional marginal using $O(sn^2\epsilon^{-4}\delta^{-2})$ rounds. Its proof combines entropy-minimizing prefix measurements, recovery estimates, and multiplicative weights. Infinitely-often one-way puzzles rule out efficient universal inference with polynomial round complexity; for prediction of classical POVM outcomes alone, their existence is equivalent to average-case hardness at the specified near-optimal round complexity.
The guarantees concern a uniformly random round, not every sufficiently late round. The algorithms are information-theoretic, without efficient implementation guarantees. Tomography permits learner-chosen measurements and targets their conditional next state. A converse cryptographic characterization for full quantum-state inference remains open.
Little sign of AI-generated textAI use disclosed
We used generative AI tools, OpenAI GPT-5.6 Sol and GPT-6 Astra, to assist with improving the presentation of the manuscript and refining proof arguments in \cref{sec:uqii,sec:POVM,sec:tomography}.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Comments
42 pages, 1 figure; v2: Improved the round complexity bound for non-i.i.d. tomography from exponential to polynomial in the source description length and the number of qubits per register (Section 6)
Solomonoff's universal inductive inference [Inf. Control. 1964] is one of the most general frameworks for learning from sequential data and predicting future observations. It provides prediction guarantees for any computable stochastic source. We ask whether an analogous universal theory of induction can be developed for quantum systems. To this end, we introduce universal quantum inductive inference, a framework for learning and predicting quantum sources that may exhibit arbitrary correlations and entanglement across time. Given the outcomes of past measurements and the corresponding post-measurement quantum systems, the learner produces a joint state that predicts the next measurement outcome and post-measurement system while preserving correlations with the past systems. We model a quantum source as a multipartite quantum state whose description is generated by an unknown s-bit program within a given time bound. The learner is required to produce a state that is ε-close in trace distance to the target with probability at least 1−δ. We establish an information-theoretic inference algorithm with round complexity O(sε−2δ−1). We further prove a matching lower bound in the relevant parameter regime, even for classical sources. As a second result, we construct a non-i.i.d. state tomography algorithm that outputs a classical description of the conditional state of the next system given past measurement outcomes. Our information-theoretic tomography algorithm achieves round complexity O(sn2ε−4δ−2), where n is the number of qubits received in each round. Finally, we investigate the computational hardness of universal quantum inductive inference under quantum cryptographic assumptions.
The paper asks whether Solomonoff-style prediction extends to quantum sources with arbitrary temporal correlations and entanglement. A source is an mn-qubit state whose preparation circuit is generated within time t by an unknown program of length at most s. Given measurement history and one copy of the retained post-measurement prefix, the learner must produce a joint state approximating the next measurement outcome, next post-measurement system, and their correlations with the past.
An information-theoretic learner achieves trace-distance error ϵ with probability at least 1−δ using O(sϵ−2δ−1) rounds, independent of register size n and preparation-time bound t. The construction combines a time-bounded universal density matrix with an averaged rotated Petz recovery map. Universal domination bounds total relative entropy by O(s); telescoping recovery inequalities bound cumulative squared prediction error. A classical lower bound matches this scaling in the stated parameter regime.
A separate non-i.i.d. tomography procedure outputs a classical description of the next conditional marginal using O(sn2ϵ−4δ−2) rounds. Its proof combines entropy-minimizing prefix measurements, recovery estimates, and multiplicative weights. Infinitely-often one-way puzzles rule out efficient universal inference with polynomial round complexity; for prediction of classical POVM outcomes alone, their existence is equivalent to average-case hardness at the specified near-optimal round complexity.
The guarantees concern a uniformly random round, not every sufficiently late round. The algorithms are information-theoretic, without efficient implementation guarantees. Tomography permits learner-chosen measurements and targets their conditional next state. A converse cryptographic characterization for full quantum-state inference remains open.
How many samples of a quantum state are required to learn a complete description of it? As we will see in this thesis, the fine-grained answer depends on the measurements available to the learner, but in general it is at least Ω(d^2/ϵ^2) where d is the dimension of the state and ϵ the trace distance accuracy. Optimal algorithms for this task -- known as quantum state tomography -- make use of powerful, yet highly impractical entangled measurements, where some joint measurement is performed on all copies of the state. What can be accomplished without such measurements, where one must perform measurements on individual copies of the states? \n \nIn Chapter 2 we show a relationship between the recently proposed quantum online learning framework and quantum state tomography. Specifically, we show that tomography can be accomplished using online learning algorithms in a black-box manner and O(d^4/ϵ^4) two-outcome measurements on separate copies of the state. The interpretation of this approach is that the experimentalist uses informative measurements to teach the learner by helping it make "mistakes" on measurements as early as possible. \n \nWe move on to proving lower bounds on tomography in Chapter 3. First, we review a known lower bound for entangled measurements as well as a Ω(d^3/ϵ^2) lower bound in the setting where non-entangled measurements are made non-adaptively, both due to Ref.[18]. We then derive a novel bound of Ω(d^4/ϵ^2) samples when the learner is further restricted to observing a constant number of outcomes (e.g., two-outcome measurements). This implies that the folklore "Pauli tomography" algorithm is optimal in this setting. \n \nUnderstanding the power of adaptive measurements, where measurement choices can depend on previous outcomes, is currently an open problem. In Chapter 4 we present two scenarios in which adapting on previous outcomes makes no difference to the number of samples required. In the first, the learner is limited to adapting on at most o(d^2/ϵ^2) of the previous outcomes. In the second, measurements are drawn from some set of at most exp(O(d)) measurements. In particular, this second lower bound implies that adaptivity makes no difference in the regime of efficiently implementable measurements, in the context of quantum computing. \n \nFinally, we apply the above technique to the problems of classical shadows and shadow tomography to obtain similar lower bounds. Here, one is interested only in determining the expectations of some fixed set of observables. We once again find that, for the worst-case input of observables, adaptivity makes no difference to the sample complexity when considering efficient, non-entangled measurements. As a corollary, we find a straightforward algorithm for shadow tomography is optimal in this setting.
With quantum sensors, simulators and networks emerging, a future of quantum technology may produce quantum states as data---that is, coherently rather than as classical measurement records---thus motivating the study of suitable quantum generalisations of modern machine learning, including the automated, unsupervised extraction of useful representations. Two ingredients are central to the latter: inference, mapping observations to latent representations, and generation, mapping latent states back to synthetic data. Both are related to each other and to joint distributions for training models by the chain-rule of classical probability theory. The fact that quantum states however lack such universal, standard factorisation property thus poses a challenge. Here we develop a conceptual and mathematical framework for unsupervised representation learning from quantum data. Models are joint quantum states over visible and latent systems; state-over-time maps provide a notion of factorisation into a marginal state and inference (generation) channel; models with inference (generation) are ambiguous states---states for which such factorisation obtains---subject to a further consistency condition on extended inference maps as data extension. These stipulations are restrictive: we show that non-trivial models must feature non-linear such maps to the extended space. For three representative state-over-time maps, we completely characterise the ambiguous states, uncovering a hierarchy tied to the positive-partial-transpose (PPT) criterion from entanglement theory. Notably, the Leifer-Spekkens construction supports inference and generation exactly for model classes of PPT states, thus allowing genuinely quantum visible-latent correlations. We also formulate quantum counterparts of exact and approximate inference training, explore weaker notions of data extension and sketch a future research programme.
Data-driven inference was recently introduced as a protocol that, upon the input of a set of data, outputs a mathematical description for a physical device able to explain the data. The device so inferred is automatically self-consistent, that is, capable of generating all given data, and least committal, that is, consistent with a minimal superset of the given dataset. When applied to the inference of an unknown device, data-driven inference has been shown to output always the "true" device whenever the dataset has been produced by means of an observationally complete setup, which plays here the same role played by informationally complete setups in conventional quantum tomography. In this paper we develop a unified formalism for the data-driven inference of states and measurements. In the case of qubits, in particular, we provide an explicit implementation of the inference protocol as a convex programming algorithm for the machine learning of states and measurements. We also derive a complete characterization of observational completeness for general systems, from which it follows that only spherical 2-designs achieve observational completeness for qubit systems. This result provides symmetric informationally complete sets and mutually unbiased bases with a new theoretical and operational justification.
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.
Over decades traditional information theory of source and channel coding advances toward learning and effective extraction of information from data. We propose to go one step further and offer a theoretical foundation for learning classical patterns from quantum data. However, there are several roadblocks to lay the groundwork for such a generalization. First, classical data must be replaced by a density operator over a Hilbert space. Hence, deviated from problems such as state tomography, our samples are i.i.d density operators. The second challenge is even more profound since we must realize that our only interaction with a quantum state is through a measurement which - due to no-cloning quantum postulate - loses information after measuring it. With this in mind, we present a quantum counterpart of the well-known probably approximately correct (PAC) framework. Based on that, we propose a quantum analogous of the Empirical Risk Minimization (ERM) algorithm for learning measurement hypothesis classes. Then, we establish upper bounds on the quantum sample complexity quantum concept classes.
Constructing optimal quantum information protocols without complete knowledge of the underlying states or channels is a central challenge. We address this challenge by developing universal correlation detection as a common building block for quantum communication. Our detectors distinguish a bipartite state from the product of its marginals and attain the same first-order asymptotic performance as optimal tests constructed with complete state information. For general bipartite quantum states, knowledge of a single marginal suffices: a detector depending only on that marginal is first-order optimal for every compatible state. For classical-quantum states, the detector is fully universal and requires no prior state information. By combining these detectors with position-based decoding and convex splitting, we construct channel-independent coding schemes that achieve capacity for a range of communication tasks. These results turn universal correlation detection into a systematic tool for universal protocol design, providing a unified route to designing capacity-achieving protocols for many communication tasks over unknown quantum channels.