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:2409.03684

Predicting quantum channels over general product distributions

Sitan Chen, Pont, Jaume de Dios, Jun-Ting Hsieh, Hsin-Yuan Huang, Jane Lange, Jerry Zheng Li

Published Sep 5, 2024• 0 citations
arXivHTMLPDF

Abstract

We investigate the problem of predicting the output behavior of unknown quantum channels. Given query access to an $n$-qubit channel $E$ and an observable $O$, we aim to learn the mapping \begin{equation*} ρ\mapsto \mathrm{Tr}(O E[ρ]) \end{equation*} to within a small error for most $ρ$ sampled from a distribution $D$. Previously, Huang, Chen, and Preskill proved a surprising result that even if $E$ is arbitrary, this task can be solved in time roughly $n^{O(\log(1/ε))}$, where $ε$ is the target prediction error. However, their guarantee applied only to input distributions $D$ invariant under all single-qubit Clifford gates, and their algorithm fails for important cases such as general product distributions over product states $ρ$. In this work, we propose a new approach that achieves accurate prediction over essentially any product distribution $D$, provided it is not "classical" in which case there is a trivial exponential lower bound. Our method employs a "biased Pauli analysis," analogous to classical biased Fourier analysis. Implementing this approach requires overcoming several challenges unique to the quantum setting, including the lack of a basis with appropriate orthogonality properties. The techniques we develop to address these issues may have broader applications in quantum information.

DOI
10.48550/arxiv.2409.03684

Related papers

Learning to predict arbitrary quantum processes

Hsin-Yuan Huang, Sitan Chen, John P. Preskill

We present an efficient machine learning (ML) algorithm for predicting any unknown quantum process $\mathcal{E}$ over $n$ qubits. For a wide range of distributions $\mathcal{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~$\mathcal{E}$, with a small average error over input states drawn from $\mathcal{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.

arXiv:2210.14894•Oct 26, 2022•1 citation

Learning to Predict Arbitrary Quantum Processes

Hsin-Yuan Huang, Sitan Chen, John P. Preskill

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.

PRX Quantum•Dec 6, 2023•71 citations

Quantum learning Boolean linear functions w.r.t. product distributions

Matthias C. Caro

Abstract The problem of learning Boolean linear functions from quantum examples w.r.t. the uniform distribution can be solved on a quantum computer using the Bernstein–Vazirani algorithm (Bernstein and Vazirani, in: Kosaraju (ed) Proceedings of the twenty-fifth annual ACM symposium on theory of computing, ACM, New York, 1993. 10.1145/167088.167097 ). A similar strategy can be applied in the case of noisy quantum training data, as was observed in Grilo et al. (Learning with errors is easy with quantum samples, 2017). However, extensions of these learning algorithms beyond the uniform distribution have not yet been studied. We employ the biased quantum Fourier transform introduced in Kanade et al. (Learning dnfs under product distributions via $$\mu $$ μ -biased quantum Fourier sampling, 2018) to develop efficient quantum algorithms for learning Boolean linear functions on n bits from quantum examples w.r.t. a biased product distribution. Our first procedure is applicable to any (except full) bias and requires $$\mathcal {O}(\ln (n))$$ O(ln(n)) quantum examples. The number of quantum examples used by our second algorithm is independent of n, but the strategy is applicable only for small bias. Moreover, we show that the second procedure is stable w.r.t. noisy training data and w.r.t. faulty quantum gates. This also enables us to solve a version of the learning problem in which the underlying distribution is not known in advance. Finally, we prove lower bounds on the classical and quantum sample complexities of the learning problem. Whereas classically, $$\varOmega (n)$$ Ω(n) examples are necessary independently of the bias, we are able to establish a quantum sample complexity lower bound of $$\varOmega (\ln (n))$$ Ω(ln(n)) only under an assumption of large bias. Nevertheless, this allows for a discussion of the performance of our suggested learning algorithms w.r.t. sample complexity. With our analysis, we contribute to a more quantitative understanding of the power and limitations of quantum training data for learning classical functions.

arXiv:1902.08753•Quantum Information Processing•Apr 20, 2020•5 citations

Predicting properties of quantum systems by regression on a quantum computer

Andrey Kardashin, Yerassyl Balkybek, Vladimir V. Palyulin +1 more

Quantum computers can be considered as a natural means for performing machine learning tasks for inherently quantum labeled data. Many quantum machine learning techniques have been developed for solving classification problems, such as distinguishing between phases of matter or quantum processes. Similarly, one can consider a more general problem of regression, when the aim is to predict continuous labels quantifying properties of quantum states, such as purity or entanglement. In this work, we propose a method for predicting such properties. The method is based on the notion of parametrized quantum circuits, and it seeks to find an observable the expectation of which gives the prediction of the property of interest with a low variance. We numerically test our approach in learning to predict (i) the parameter of a parametrized channel given its output state, (ii) entanglement of two-qubit states, and (iii) the parameter of a parametrized Hamiltonian given its ground state. The results show that the proposed method is able to find observables such that they provide highly accurate predictions of the considered properties, and in some cases even saturate the Cramer-Rao bound, which characterizes the prediction error. We also compare our method with the Bayesian approach, and find that the latter prefers to minimize the prediction variance, having therefore a larger bias.

arXiv:2407.08847•Physical Review Research•Feb 25, 2025•4 citations

Nearly Query-Optimal Classical Shadow Estimation of Unitary Channels

Zihao Li, Changhao Yi, You Zhou +1 more

Classical shadow estimation (CSE) is a powerful tool for learning the properties of quantum states and quantum processes. Here we consider the CSE task for quantum unitary channels. By querying an unknown unitary channel U multiple times in quantum experiments, the goal is to learn a classical description from which one can accurately predict many different linear properties of the channel, i.e., the expectation values of arbitrary observables measured on the output of U upon arbitrary input states. Based on collective measurements on multiple systems, we propose a query-efficient protocol for this task, whose query complexity has a quadratic advantage over the previous best approach for this problem, and almost saturates the information-theoretic lower bound. To further enhance practicality, we also present a variant protocol using only single-copy measurements, which still offers much better query performance than previous protocols that do not use quantum memory, and can serve as a key subroutine for learning an arbitrary unknown Hamiltonian from dynamics. In addition to linear properties of unitary channels, our protocol can also be applied to simultaneously predict many nonlinear properties, such as out-of-time-ordered correlators.

arXiv:2410.14538•PRX Quantum•Aug 1, 2025•2 citations

On Testing and Learning Quantum Junta Channels

Zongbo Bao, Penghui Yao

We consider the problems of testing and learning quantum -junta channels, which are -qubit to -qubit quantum channels acting non-trivially on at most out of qubits and leaving the rest of qubits unchanged. We show the following. 1) An -query algorithm to distinguish whether the given channel is -junta channel or is far from any -junta channels, and a lower bound on the number of queries; 2) An -query algorithm to learn a -junta channel, and a lower bound on the number of queries. This partially answers an open problem raised by [1]. In order to settle these problems, we develop a Fourier analysis framework over the space of superoperators and prove several fundamental properties, which extends the Fourier analysis over the space of operators introduced in [2]. The distance metric we consider in this paper is obtained by Fourier analysis, which is essentially the L2-distance between Choi representations. Besides, we introduce INFLUENCE-SAMPLE to replace FOURIER-SAMPLE proposed in(Atici and Servedio, 2007). Our INFLUENCE-SAMPLE includes only single-qubit operations and results in only constant-factor decrease in efficiency.

arXiv:2305.12097•IEEE Transactions on Pattern Analysis and Machine Intelligence•Jan 13, 2025•2 citations
We investigate the problem of predicting the output behavior of unknown quantum channels. Given query access to an nnn-qubit channel EEE and an observable OOO, we aim to learn the mapping \begin{equation*} ρ\mapsto \mathrm{Tr}(O E[ρ]) \end{equation*} to within a small error for most ρρρ sampled from a distribution DDD. Previously, Huang, Chen, and Preskill proved a surprising result that even if EEE is arbitrary, this task can be solved in time roughly nO(log⁡(1/ε))n^{O(\log(1/ε))}nO(log(1/ε)), where εεε is the target prediction error. However, their guarantee applied only to input distributions DDD invariant under all single-qubit Clifford gates, and their algorithm fails for important cases such as general product distributions over product states ρρρ. In this work, we propose a new approach that achieves accurate prediction over essentially any product distribution DDD, provided it is not "classical" in which case there is a trivial exponential lower bound. Our method employs a "biased Pauli analysis," analogous to classical biased Fourier analysis. Implementing this approach requires overcoming several challenges unique to the quantum setting, including the lack of a basis with appropriate orthogonality properties. The techniques we develop to address these issues may have broader applications in quantum information.
We present an efficient machine learning (ML) algorithm for predicting any unknown quantum process E\mathcal{E}E over nnn qubits. For a wide range of distributions D\mathcal{D}D on arbitrary nnn-qubit states, we show that this ML algorithm can learn to predict any local property of the output from the unknown process~E\mathcal{E}E, with a small average error over input states drawn from D\mathcal{D}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 10610^6106 and system size up to 505050 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.
Abstract The problem of learning Boolean linear functions from quantum examples w.r.t. the uniform distribution can be solved on a quantum computer using the Bernstein–Vazirani algorithm (Bernstein and Vazirani, in: Kosaraju (ed) Proceedings of the twenty-fifth annual ACM symposium on theory of computing, ACM, New York, 1993. 10.1145/167088.167097 ). A similar strategy can be applied in the case of noisy quantum training data, as was observed in Grilo et al. (Learning with errors is easy with quantum samples, 2017). However, extensions of these learning algorithms beyond the uniform distribution have not yet been studied. We employ the biased quantum Fourier transform introduced in Kanade et al. (Learning dnfs under product distributions via μ\mu μ μ -biased quantum Fourier sampling, 2018) to develop efficient quantum algorithms for learning Boolean linear functions on n bits from quantum examples w.r.t. a biased product distribution. Our first procedure is applicable to any (except full) bias and requires O(ln⁡(n))\mathcal {O}(\ln (n))O(ln(n)) O(ln(n)) quantum examples. The number of quantum examples used by our second algorithm is independent of n, but the strategy is applicable only for small bias. Moreover, we show that the second procedure is stable w.r.t. noisy training data and w.r.t. faulty quantum gates. This also enables us to solve a version of the learning problem in which the underlying distribution is not known in advance. Finally, we prove lower bounds on the classical and quantum sample complexities of the learning problem. Whereas classically, Ω(n)\varOmega (n)Ω(n) Ω(n) examples are necessary independently of the bias, we are able to establish a quantum sample complexity lower bound of Ω(ln⁡(n))\varOmega (\ln (n))Ω(ln(n)) Ω(ln(n)) only under an assumption of large bias. Nevertheless, this allows for a discussion of the performance of our suggested learning algorithms w.r.t. sample complexity. With our analysis, we contribute to a more quantitative understanding of the power and limitations of quantum training data for learning classical functions.
Quantum computers can be considered as a natural means for performing machine learning tasks for inherently quantum labeled data. Many quantum machine learning techniques have been developed for solving classification problems, such as distinguishing between phases of matter or quantum processes. Similarly, one can consider a more general problem of regression, when the aim is to predict continuous labels quantifying properties of quantum states, such as purity or entanglement. In this work, we propose a method for predicting such properties. The method is based on the notion of parametrized quantum circuits, and it seeks to find an observable the expectation of which gives the prediction of the property of interest with a low variance. We numerically test our approach in learning to predict (i) the parameter of a parametrized channel given its output state, (ii) entanglement of two-qubit states, and (iii) the parameter of a parametrized Hamiltonian given its ground state. The results show that the proposed method is able to find observables such that they provide highly accurate predictions of the considered properties, and in some cases even saturate the Cramer-Rao bound, which characterizes the prediction error. We also compare our method with the Bayesian approach, and find that the latter prefers to minimize the prediction variance, having therefore a larger bias.
Classical shadow estimation (CSE) is a powerful tool for learning the properties of quantum states and quantum processes. Here we consider the CSE task for quantum unitary channels. By querying an unknown unitary channel U multiple times in quantum experiments, the goal is to learn a classical description from which one can accurately predict many different linear properties of the channel, i.e., the expectation values of arbitrary observables measured on the output of U upon arbitrary input states. Based on collective measurements on multiple systems, we propose a query-efficient protocol for this task, whose query complexity has a quadratic advantage over the previous best approach for this problem, and almost saturates the information-theoretic lower bound. To further enhance practicality, we also present a variant protocol using only single-copy measurements, which still offers much better query performance than previous protocols that do not use quantum memory, and can serve as a key subroutine for learning an arbitrary unknown Hamiltonian from dynamics. In addition to linear properties of unitary channels, our protocol can also be applied to simultaneously predict many nonlinear properties, such as out-of-time-ordered correlators.
We consider the problems of testing and learning quantum -junta channels, which are -qubit to -qubit quantum channels acting non-trivially on at most out of qubits and leaving the rest of qubits unchanged. We show the following. 1) An -query algorithm to distinguish whether the given channel is -junta channel or is far from any -junta channels, and a lower bound on the number of queries; 2) An -query algorithm to learn a -junta channel, and a lower bound on the number of queries. This partially answers an open problem raised by [1]. In order to settle these problems, we develop a Fourier analysis framework over the space of superoperators and prove several fundamental properties, which extends the Fourier analysis over the space of operators introduced in [2]. The distance metric we consider in this paper is obtained by Fourier analysis, which is essentially the L2-distance between Choi representations. Besides, we introduce INFLUENCE-SAMPLE to replace FOURIER-SAMPLE proposed in(Atici and Servedio, 2007). Our INFLUENCE-SAMPLE includes only single-qubit operations and results in only constant-factor decrease in efficiency.