Learning about physical systems from quantum-enhanced experiments can outperform learning from experiments in which only classical memory and processing are available. Whereas quantum advantages have been established for state learning, quantum process learning is less understood. We establish an exponential quantum advantage for learning an unknown n -qubit quantum process \(\mathcal {N}\) . We show that a quantum memory allows to efficiently solve the following tasks: (a) learning the Pauli transfer matrix (PTM) of an arbitrary \(\mathcal {N}\) , (b) predicting expectation values of Pauli-sparse observables measured on the output of an arbitrary \(\mathcal {N}\) upon input of a Pauli-sparse state, and (c) predicting expectation values of arbitrary observables measured on the output of an unknown \(\mathcal {N}\) with sparse PTM upon input of an arbitrary state. With quantum memory, these tasks can be solved using linearly-in- n many copies of the Choi state of \(\mathcal {N}\) . In contrast, any learner without quantum memory requires exponentially-in- n many queries, even when using adaptively designed experiments. In proving this separation, we extend existing shadow tomography bounds from states to channels. Moreover, we combine PTM learning with polynomial interpolation to learn arbitrary Hamiltonians from short-time dynamics. Our results highlight the power of quantum-enhanced experiments for learning highly complex quantum dynamics.
Learning about physical systems from quantum-enhanced experiments can outperform learning from experiments in which only classical memory and processing are available. Whereas quantum advantages have been established for state learning, quantum process learning is less understood. We establish an exponential quantum advantage for learning an unknown n -qubit quantum process (\mathcal {N}) . We show that a quantum memory allows to efficiently solve the following tasks: (a) learning the Pauli transfer matrix (PTM) of an arbitrary (\mathcal {N}) , (b) predicting expectation values of Pauli-sparse observables measured on the output of an arbitrary (\mathcal {N}) upon input of a Pauli-sparse state, and (c) predicting expectation values of arbitrary observables measured on the output of an unknown (\mathcal {N}) with sparse PTM upon input of an arbitrary state. With quantum memory, these tasks can be solved using linearly-in- n many copies of the Choi state of (\mathcal {N}) . In contrast, any learner without quantum memory requires exponentially-in- n many queries, even when using adaptively designed experiments. In proving this separation, we extend existing shadow tomography bounds from states to channels. Moreover, we combine PTM learning with polynomial interpolation to learn arbitrary Hamiltonians from short-time dynamics. Our results highlight the power of quantum-enhanced experiments for learning highly complex quantum dynamics.
Quantum process tomography, the task of learning an unknown quantum channel from black-box access, is a central problem in quantum information. In this setting, protocols with quantum memory can coherently store and jointly process quantum information obtained from multiple channel uses, whereas protocols without quantum memory must measure after each use and retain only a classical transcript of the measurement outcomes. A fundamental open question is whether quantum memory provides a query-complexity advantage even when protocols without quantum memory may adapt their experiments based on all previous outcomes with unbounded classical computational power. In this work, we show that it does. We determine the optimal query complexity of quantum process tomography without quantum memory up to a constant factor to be Θ(din3dout3/ε2), where din and dout are the channel input and output dimensions, respectively, and ε is the target diamond-norm accuracy. More precisely, we prove that any incoherent protocol for this task, including adaptive protocols, requires Ω(din3dout3/ε2) queries, even when each channel use may be assisted by arbitrary fresh ancilla, and we present a non-adaptive, ancilla-free incoherent protocol achieving the matching upper bound O(din3dout3/ε2). Our results thereby generalize the optimal sample-complexity bounds for single-copy state tomography, recovered as the special case din=1. By contrast, coherent protocols with quantum memory achieve query complexity Θ(din2dout2/ε2). Hence, our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.
Among recent insights into learning quantum states, online learning and shadow tomography procedures are notable for their ability to accurately predict expectation values even of adaptively chosen observables. In contrast to the state case, quantum process learning tasks with a similarly adaptive nature have received little attention. In this work, we investigate online learning tasks for quantum processes. Whereas online learning is infeasible for general quantum channels, we show that channels of bounded gate complexity as well as Pauli channels can be online learned in the regret and mistake-bounded models of online learning. In fact, we can online learn probabilistic mixtures of any exponentially large set of known channels. We also provide a provably sample-efficient shadow tomography procedure for Pauli channels. Our results extend beyond quantum channels to non-Markovian multi-time processes, with favorable regret and mistake bounds, as well as a shadow tomography procedure. We complement our online learning upper bounds with mistake as well as computational lower bounds. On the technical side, we make use of the multiplicative weights update algorithm, classical adaptive data analysis, and Bell sampling, as well as tools from the theory of quantum combs for multi-time quantum processes. Our work initiates a study of online learning for classes of quantum channels and, more generally, non-Markovian quantum processes. Given the importance of online learning for state shadow tomography, this may serve as a step towards quantum channel variants of adaptive shadow tomography.
We present an efficient machine learning (ML) algorithm for predicting any unknown quantum process E over n qubits. For a wide range of distributions D on arbitrary n-qubit states, we show that this ML algorithm can learn to predict any local property of the output from the unknown process~E, with a small average error over input states drawn from D. The ML algorithm is computationally efficient even when the unknown process is a quantum circuit with exponentially many gates. Our algorithm combines efficient procedures for learning properties of an unknown state and for learning a low-degree approximation to an unknown observable. The analysis hinges on proving new norm inequalities, including a quantum analogue of the classical Bohnenblust-Hille inequality, which we derive by giving an improved algorithm for optimizing local Hamiltonians. Numerical experiments on predicting quantum dynamics with evolution time up to 106 and system size up to 50 qubits corroborate our proof. Overall, our results highlight the potential for ML models to predict the output of complex quantum dynamics much faster than the time needed to run the process itself.
We present an efficient machine-learning (ML) algorithm for predicting any unknown quantum process E over n qubits.For a wide range of distributions D on arbitrary n-qubit states, we show that this ML algorithm can learn to predict any local property of the output from the unknown process E, with a small average error over input states drawn from D. The ML algorithm is computationally efficient even when the unknown process is a quantum circuit with exponentially many gates.Our algorithm combines efficient procedures for learning properties of an unknown state and for learning a low-degree approximation to an unknown observable.The analysis hinges on proving new norm inequalities, including a quantum analogue of the classical Bohnenblust-Hille inequality, which we derive by giving an improved algorithm for optimizing local Hamiltonians.Numerical experiments on predicting quantum dynamics with evolution time up to 10 6 and system size up to 50 qubits corroborate our proof.Overall, our results highlight the potential for ML models to predict the output of complex quantum dynamics much faster than the time needed to run the process itself.
Quantum resources enable us to achieve an exponential advantage in learning the properties of unknown physical systems by employing quantum memory. While entanglement with quantum memory is recognized as a necessary qualitative resource, its quantitative role remains less understood. In this work, we distinguish between two fundamental resources provided by quantum memory—entanglement and ancilla qubits—and analyze their separate contributions to the sampling complexity of quantum learning. Focusing on the task of Pauli channel learning, a prototypical example of quantum channel learning, remarkably, we prove that vanishingly small entanglement in the input state already suffices to accomplish the learning task with only a polynomial number of channel queries in the number of qubits. In contrast, we show that without a sufficient number of ancilla qubits, even learning partial information about the channel demands an exponentially large sample complexity. Thus, our findings reveal that while a large amount of entanglement is not necessary, the dimension of the quantum memory is a crucial resource. Hence, by identifying how the two resources contribute differently, our work offers deeper insight into the nature of the quantum learning advantage. While it is known that entanglement plays a role in learning the properties of unknown physical systems, the detailed quantitative dependence is unclear. Here, the authors investigate the fundamental resources behind quantum advantage in channel learning, revealing that while extensive entanglement is unnecessary, the number of ancilla qubits is crucial.
Quantum channels can be characterized by their action on an orthogonal operator basis, where these operators are related to observable properties of the quantum system. For qudit and multimode bosonic systems, this is encoded respectively in the Heisenberg--Weyl transfer matrix estimated from the Choi-state, and in the characteristic-function transfer map estimated from a two-mode squeezed vacuum based Choi-state. We derive sample-complexity bounds for estimating entries of the transfer matrix/map to additive accuracy ε with success probability ≥1−δ, under different resources: access to the complex-conjugate channel E∗ and/or parallel access to c copies. In all settings, the learner uses parallel channel calls with adaptively chosen, ancilla-assisted input states and measurements. Absolute values of transfer-matrix entries can be learned efficiently with simultaneous access to E and E∗, with tight scaling ε−4. Without conjugate access, any c<d copies are insufficient for efficient learning, requiring sample complexity exponential in the number of (d-level) qudits n (for prime d). Efficiency is recovered at c=d, with tight scaling ε−2d. For bosonic systems, exponential sample complexity holds in terms of an effective dimension induced by an energy constraint for all c=O(1/ε). Although the task is learning a particular state, these bounds carry stronger implications than standard state-learning bounds since the learner controls the inputs and has ancillary assistance. This establishes a hierarchy of channel-learning resources: self-complex-conjugate channels require two-copy ancilla-assisted access for efficient learning, while for every square-free d, some channels require d-copy access. As a corollary, we derive tighter lower bounds for state learning with limited multi-copy access.