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

Learning k-qubit Quantum Operators via Pauli Decomposition

Mohsen Heidari, Wojciech Szpankowski A

Published Feb 10, 2021• 1 citation
arXivHTMLPDF

Abstract

Motivated by the limited qubit capacity of current quantum systems, we study the quantum sample complexity of $k$-qubit quantum operators, i.e., operations applicable on only $k$ out of $d$ qubits. The problem is studied according to the quantum probably approximately correct (QPAC) model abiding by quantum mechanical laws such as no-cloning, state collapse, and measurement incompatibility. With the delicacy of quantum samples and the richness of quantum operations, one expects a significantly larger quantum sample complexity. This paper proves the contrary. We show that the quantum sample complexity of $k$-qubit quantum operations is comparable to the classical sample complexity of their counterparts (juntas), at least when $\frac{k}{d}\ll 1$. This is surprising, especially since sample duplication is prohibited, and measurement incompatibility would lead to an exponentially larger sample complexity with standard methods. Our approach is based on the Pauli decomposition of quantum operators and a technique that we name Quantum Shadow Sampling (QSS) to reduce the sample complexity exponentially. The results are proved by developing (i) a connection between the learning loss and the Pauli decomposition; (ii) a scalable QSS circuit for estimating the Pauli coefficients; and (iii) a quantum algorithm for learning $k$-qubit operators with sample complexity $O(\frac{k4^k}{ε^2}\log d)$.

DOI
10.48550/arxiv.2102.05209

Related papers

New Bounds on Quantum Sample Complexity of Measurement Classes

Mohsen Heidari, Wojciech Szpankowski A

This paper studies quantum supervised learning for classical inference from quantum states. In this model, a learner has access to a set of labeled quantum samples as the training set. The objective is to find a quantum measurement that predicts the label of the unseen samples. The hardness of learning is measured via sample complexity under a quantum counterpart of the well-known probably approximately correct (PAC). Quantum sample complexity is expected to be higher than classical one, because of the measurement incompatibility and state collapse. Recent efforts showed that the sample complexity of learning a finite quantum concept class$\mathcal{C}$scales as$O(\vert \mathcal{C}\vert)$. This is significantly higher than the classical sample complexity that grows logarithmically with the class size. This work improves the sample complexity bound to$O\left(V_{\mathcal{C}^*} \log \left\vert\mathcal{C}^*\right\vert\right)$, where$\mathcal{C}^*$is the set of extreme points of the convex closure of$\mathcal{C}$and$V_{\mathcal{C}^*}$is the shadow-norm of this set. We show the tightness of our bound for the class of bounded Hilbert-Schmidt norm, scaling as$O\left(\log \left\vert\mathcal{C}^*\right\vert\right)$. Our approach is based on a new quantum empirical risk minimization (ERM) algorithm equipped with a shadow tomography method.

arXiv:2408.12683•IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•1 citation

Estimating properties of a quantum state by importance-sampled operator shadows

Naixu Guo, Pan, Feng, Patrick Rebentrost

Measuring properties of quantum systems is a fundamental problem in quantum mechanics. We provide a simple method for estimating the expectation value of observables with an unknown quantum state. The idea is to use a data structure to sample the terms of observables based on the Pauli decomposition proportionally to their importance. We call this technique operator shadow as a shorthand for the procedure of preparing a sketch of an operator to estimate properties. Only when the numbers of observables are small for multiple local observables, the sample complexity of this method is better than the classical shadow technique. However, if we want to estimate the expectation value of a linear combination of local observables, for example the energy of a local Hamiltonian, the sample complexity is better on all parameters. The time complexity to construct the data structure is $2^{O(k)}$ for $k$-local observables, similar to the post-processing time of classical shadows.

arXiv:2305.09374•May 16, 2023•0 citations

Quantum State Classification via Quantum Fourier.

Mohsen Heidari, Wojciech Szpankowski A

We study learning from quantum data, in particular quantum state classification which has applications, among others, in classifying the separability of quantum states. In this learning model, there are $n$ quantum states with classical labels as the training samples. Predictors are quantum measurements that when applied to the next unseen quantum state predict its classical label. By integrating learning theory with quantum information, we introduce a quantum counterpart of the PAC framework for learning with respect to classes of measurements. We argue that major challenges arising from the quantum nature of the problem are measurement incompatibility and the no-cloning principle -- prohibiting sample reuse. Then, after introducing a Fourier expansion through Pauli's operators, we study learning with respect to an infinite class of quantum measurements whose operator's Fourier spectrum is concentrated on low degree terms. We propose a quantum learning algorithm and show that the quantum sample complexity depends on the ``compatibility structure of such measurement classes -- the more compatible the class is, the lower the quantum sample complexity will be. We further introduce $k$-junta measurements as a special class of low-depth quantum circuits whose Fourier spectrum is concentrated on low degrees.

•Feb 10, 2021•0 citations

Sample Complexity for Embedded Multipartite Entanglement Witness via Pauli and Clifford Classical Shadows

Ziran Zhang

Detecting multipartite entanglement in many qubit systems is measurement-intensive, motivating protocols that estimate only selected observables with provable efficiency. In this work we use the classical shadow protocol to study the sample complexity required to estimate a family of subsystem $n$-partite entanglement witness embedded in an larger $N$-qubit system. We derive ensemble dependent variance bounds that lead to qualitatively distinct scaling for the snapshots cost at fixed additive error $ε$ with numerical simulations confirm these trends, exhibiting a clear crossover from Pauli favorable performance for local witness to Clifford favorable performance as the witness becomes more global.

quant-pharXiv:2601.00859•Dec 31, 2025•0 citations

Operator Relaxation and the Optimal Depth of Classical Shadows

Matteo Ippoliti, Yaodong Li, Tibor Rakovszky +1 more

Classical shadows are a powerful method for learning many properties of quantum states in a sample-efficient manner, by making use of randomized measurements. Here we study the sample complexity of learning the expectation value of Pauli operators via "shallow shadows," a recently proposed version of classical shadows in which the randomization step is effected by a local unitary circuit of variable depth t. We show that the shadow norm (the quantity controlling the sample complexity) is expressed in terms of properties of the Heisenberg time evolution of operators under the randomizing ("twirling") circuit-namely the evolution of the weight distribution characterizing the number of sites on which an operator acts nontrivially. For spatially contiguous Pauli operators of weight k, this entails a competition between two processes: operator spreading (whereby the support of an operator grows over time, increasing its weight) and operator relaxation (whereby the bulk of the operator develops an equilibrium density of identity operators, decreasing its weight). From this simple picture we derive (i) an upper bound on the shadow norm which, for depth t∼log(k), guarantees an exponential gain in sample complexity over the t=0 protocol in any spatial dimension, and (ii) quantitative results in one dimension within a mean-field approximation, including a universal subleading correction to the optimal depth, found to be in excellent agreement with infinite matrix product state numerical simulations. Our Letter connects fundamental ideas in quantum many-body dynamics to applications in quantum information science, and paves the way to highly optimized protocols for learning different properties of quantum states.

arXiv:2212.11963•Physical Review Letters•Jun 9, 2023•37 citations

Efficient information recovery from Pauli noise via classical shadow

Yifei Chen, Yu, Zhan, Chenghong Zhu +1 more

The rapid advancement of quantum computing has led to an extensive demand for effective techniques to extract classical information from quantum systems, particularly in fields like quantum machine learning and quantum chemistry. However, quantum systems are inherently susceptible to noises, which adversely corrupt the information encoded in quantum systems. In this work, we introduce an efficient algorithm that can recover information from quantum states under Pauli noise. The core idea is to learn the necessary information of the unknown Pauli channel by post-processing the classical shadows of the channel. For a local and bounded-degree observable, only partial knowledge of the channel is required rather than its complete classical description to recover the ideal information, resulting in a polynomial-time algorithm. This contrasts with conventional methods such as probabilistic error cancellation, which requires the full information of the channel and exhibits exponential scaling with the number of qubits. We also prove that this scalable method is optimal on the sample complexity and generalise the algorithm to the weight contracting channel. Furthermore, we demonstrate the validity of the algorithm on the 1D anisotropic Heisenberg-type model via numerical simulations. As a notable application, our method can be severed as a sample-efficient error mitigation scheme for Clifford circuits.

arXiv:2305.04148•May 6, 2023•1 citation
Motivated by the limited qubit capacity of current quantum systems, we study the quantum sample complexity of kkk-qubit quantum operators, i.e., operations applicable on only kkk out of ddd qubits. The problem is studied according to the quantum probably approximately correct (QPAC) model abiding by quantum mechanical laws such as no-cloning, state collapse, and measurement incompatibility. With the delicacy of quantum samples and the richness of quantum operations, one expects a significantly larger quantum sample complexity. This paper proves the contrary. We show that the quantum sample complexity of kkk-qubit quantum operations is comparable to the classical sample complexity of their counterparts (juntas), at least when kd≪1\frac{k}{d}\ll 1dk​≪1. This is surprising, especially since sample duplication is prohibited, and measurement incompatibility would lead to an exponentially larger sample complexity with standard methods. Our approach is based on the Pauli decomposition of quantum operators and a technique that we name Quantum Shadow Sampling (QSS) to reduce the sample complexity exponentially. The results are proved by developing (i) a connection between the learning loss and the Pauli decomposition; (ii) a scalable QSS circuit for estimating the Pauli coefficients; and (iii) a quantum algorithm for learning kkk-qubit operators with sample complexity O(k4kε2log⁡d)O(\frac{k4^k}{ε^2}\log d)O(ε2k4k​logd).
This paper studies quantum supervised learning for classical inference from quantum states. In this model, a learner has access to a set of labeled quantum samples as the training set. The objective is to find a quantum measurement that predicts the label of the unseen samples. The hardness of learning is measured via sample complexity under a quantum counterpart of the well-known probably approximately correct (PAC). Quantum sample complexity is expected to be higher than classical one, because of the measurement incompatibility and state collapse. Recent efforts showed that the sample complexity of learning a finite quantum concept classC\mathcal{C}Cscales asO(∣C∣)O(\vert \mathcal{C}\vert)O(∣C∣). This is significantly higher than the classical sample complexity that grows logarithmically with the class size. This work improves the sample complexity bound toO(VC∗log⁡∣C∗∣)O\left(V_{\mathcal{C}^*} \log \left\vert\mathcal{C}^*\right\vert\right)O(VC∗​log∣C∗∣), whereC∗\mathcal{C}^*C∗is the set of extreme points of the convex closure ofC\mathcal{C}CandVC∗V_{\mathcal{C}^*}VC∗​is the shadow-norm of this set. We show the tightness of our bound for the class of bounded Hilbert-Schmidt norm, scaling asO(log⁡∣C∗∣)O\left(\log \left\vert\mathcal{C}^*\right\vert\right)O(log∣C∗∣). Our approach is based on a new quantum empirical risk minimization (ERM) algorithm equipped with a shadow tomography method.
Measuring properties of quantum systems is a fundamental problem in quantum mechanics. We provide a simple method for estimating the expectation value of observables with an unknown quantum state. The idea is to use a data structure to sample the terms of observables based on the Pauli decomposition proportionally to their importance. We call this technique operator shadow as a shorthand for the procedure of preparing a sketch of an operator to estimate properties. Only when the numbers of observables are small for multiple local observables, the sample complexity of this method is better than the classical shadow technique. However, if we want to estimate the expectation value of a linear combination of local observables, for example the energy of a local Hamiltonian, the sample complexity is better on all parameters. The time complexity to construct the data structure is 2O(k)2^{O(k)}2O(k) for kkk-local observables, similar to the post-processing time of classical shadows.
We study learning from quantum data, in particular quantum state classification which has applications, among others, in classifying the separability of quantum states. In this learning model, there are nnn quantum states with classical labels as the training samples. Predictors are quantum measurements that when applied to the next unseen quantum state predict its classical label. By integrating learning theory with quantum information, we introduce a quantum counterpart of the PAC framework for learning with respect to classes of measurements. We argue that major challenges arising from the quantum nature of the problem are measurement incompatibility and the no-cloning principle -- prohibiting sample reuse. Then, after introducing a Fourier expansion through Pauli's operators, we study learning with respect to an infinite class of quantum measurements whose operator's Fourier spectrum is concentrated on low degree terms. We propose a quantum learning algorithm and show that the quantum sample complexity depends on the ``compatibility structure of such measurement classes -- the more compatible the class is, the lower the quantum sample complexity will be. We further introduce kkk-junta measurements as a special class of low-depth quantum circuits whose Fourier spectrum is concentrated on low degrees.
Detecting multipartite entanglement in many qubit systems is measurement-intensive, motivating protocols that estimate only selected observables with provable efficiency. In this work we use the classical shadow protocol to study the sample complexity required to estimate a family of subsystem nnn-partite entanglement witness embedded in an larger NNN-qubit system. We derive ensemble dependent variance bounds that lead to qualitatively distinct scaling for the snapshots cost at fixed additive error εεε with numerical simulations confirm these trends, exhibiting a clear crossover from Pauli favorable performance for local witness to Clifford favorable performance as the witness becomes more global.
Classical shadows are a powerful method for learning many properties of quantum states in a sample-efficient manner, by making use of randomized measurements. Here we study the sample complexity of learning the expectation value of Pauli operators via "shallow shadows," a recently proposed version of classical shadows in which the randomization step is effected by a local unitary circuit of variable depth t. We show that the shadow norm (the quantity controlling the sample complexity) is expressed in terms of properties of the Heisenberg time evolution of operators under the randomizing ("twirling") circuit-namely the evolution of the weight distribution characterizing the number of sites on which an operator acts nontrivially. For spatially contiguous Pauli operators of weight k, this entails a competition between two processes: operator spreading (whereby the support of an operator grows over time, increasing its weight) and operator relaxation (whereby the bulk of the operator develops an equilibrium density of identity operators, decreasing its weight). From this simple picture we derive (i) an upper bound on the shadow norm which, for depth t∼log(k), guarantees an exponential gain in sample complexity over the t=0 protocol in any spatial dimension, and (ii) quantitative results in one dimension within a mean-field approximation, including a universal subleading correction to the optimal depth, found to be in excellent agreement with infinite matrix product state numerical simulations. Our Letter connects fundamental ideas in quantum many-body dynamics to applications in quantum information science, and paves the way to highly optimized protocols for learning different properties of quantum states.
The rapid advancement of quantum computing has led to an extensive demand for effective techniques to extract classical information from quantum systems, particularly in fields like quantum machine learning and quantum chemistry. However, quantum systems are inherently susceptible to noises, which adversely corrupt the information encoded in quantum systems. In this work, we introduce an efficient algorithm that can recover information from quantum states under Pauli noise. The core idea is to learn the necessary information of the unknown Pauli channel by post-processing the classical shadows of the channel. For a local and bounded-degree observable, only partial knowledge of the channel is required rather than its complete classical description to recover the ideal information, resulting in a polynomial-time algorithm. This contrasts with conventional methods such as probabilistic error cancellation, which requires the full information of the channel and exhibits exponential scaling with the number of qubits. We also prove that this scalable method is optimal on the sample complexity and generalise the algorithm to the weight contracting channel. Furthermore, we demonstrate the validity of the algorithm on the 1D anisotropic Heisenberg-type model via numerical simulations. As a notable application, our method can be severed as a sample-efficient error mitigation scheme for Clifford circuits.