We show that the sample complexity required in quantum learning theory within a general parametric framework is fundamentally governed by the inverse Fisher information matrix. More specifically, we derive upper and lower bounds on the number of samples required to estimate the parameters of a quantum system within a prescribed small additive error, with high success probability under maximum-likelihood estimation. Notably, both the upper and lower bounds are determined by the supremum of the maximum diagonal entry of the inverse Fisher information matrix. We then apply the general bounds to Pauli channel learning and Pauli expectation value learning, which serve as representative tasks in quantum channel and state learning, respectively, in the asymptotic small-error regime. Furthermore, we identify the structural origin of exponential sample complexity in Pauli channel learning without entanglement and in Pauli expectation value learning without quantum memory by comparing the quantum Fisher information matrix and the classical Fisher information matrix. We then extend the analysis to an error criterion based on the Euclidean distance between the true parameter values and their estimators, deriving the corresponding upper and lower bounds on the sample complexity, which are likewise characterized by the inverse Fisher information matrix. As an application, we consider Pauli channel learning with entangled probes. We highlight two fundamental contributions to quantum learning theory. First, we establish a systematic framework that determines the task-independent sample complexity under maximum-likelihood estimation. Second, we show that, in the small-error regime, the learning sample complexity is governed by the inverse Fisher information matrix, which is the central quantity in quantum metrology that determines the ultimate achievable mean squared error.
We show that entangled measurements provide an exponential advantage in sample complexity for Pauli channel estimation, which is both a fundamental problem and a practically important subroutine for benchmarking near-term quantum devices. The specific task we consider is to simultaneously learn all the eigenvalues of an
n-qubit Pauli channel to $\ifmmode\pm\else\textpm\fi{}\ensuremath{\varepsilon}$ precision. We give an estimation protocol with an
n-qubit ancilla that succeeds with high probability using only $O(n/{\ensuremath{\varepsilon}}^{2})$ copies of the Pauli channel, while proving that any ancilla-free protocol (possibly with adaptive control and channel concatenation) would need at least $\mathrm{\ensuremath{\Omega}}({2}^{n/3})$ rounds of measurement. We further study the advantages provided by a small number of ancillas. For the case that a
k-qubit ancilla ($k\ensuremath{\le}n$) is available, we obtain a sample complexity lower bound of $\mathrm{\ensuremath{\Omega}}({2}^{(n\ensuremath{-}k)/3})$ for any nonconcatenating protocol, and a stronger lower bound of $\mathrm{\ensuremath{\Omega}}(n{2}^{n\ensuremath{-}k})$ for any nonadaptive, nonconcatenating protocol, which is shown to be tight. We also show how to apply the ancilla-assisted estimation protocol to a practical quantum benchmarking task in a noise-resilient and sample-efficient manner, given reasonable noise assumptions. Our results provide a practically interesting example for quantum advantages in learning and also bring insights for quantum benchmarking.
This paper presents tight upper and lower bounds for minimum number of samples (copies of a quantum state) required to attain a prescribed accuracy (measured by error variance) for scalar parameters estimation using unbiased estimators under quantum local differential privacy for qubits. Particularly, the best-case (optimal) scenario is considered by minimizing the sample complexity over all differentially-private channels; the worst-case channels can be arbitrarily uninformative and render the problem ill-defined. In the small privacy budget regime, i.e., 1, the sample complexity scales as (-2). This bound matches that of classical parameter estimation under local differential privacy. The lower bound however loosens in the large privacy budget regime, i.e., 1. The upper bound for the minimum number of samples is generalized to qudits (with dimension d) resulting in sample complexity of O(d-2).
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.
A fundamental question in PAC learning is determining the number of labeled examples required to learn a concept class to a desired accuracy and confidence. In classical learning theory, this quantity is characterized by the VC-dimension, while several quantum generalizations have established analogous results when examples are provided in quantum superposition. In this work, we study a distinct quantum PAC-learning model in which concepts are functions acting on quantum states. We demonstrate that the VC-dimension, although still relevant, fails to fully capture the sample complexity of this model. To further characterize this setting, we develop a new lower bound on the required number of samples and establish an upper bound when the states in the domain are linearly independent. Remarkably, this upper bound has a form similar to the classical PAC-learning bound. We further examine a setting in which the learner receives more informative data and show that the limitations of the VC-dimension persist in this extended model.
Estimating properties of unknown unitary operations is a fundamental task in quantum information science. While full unitary tomography requires a number of samples to the unknown unitary scaling linearly with the dimension (implying exponentially with the number of qubits), estimating specific functions of a unitary can be significantly more efficient. In this paper, we present a unified framework for the sample-efficient estimation of arbitrary square integrable functions
f:U(d)→C, using only access to the controlled-unitary operation. We first provide a tight characterization of the optimal sample complexity when the accuracy is measured by the averaged bias over the unitary
U(d). We then construct a sample-efficient estimation algorithm that becomes optimal under the Probably Approximately Correct (PAC) learning criterion for various classes of functions. Applications include optimal estimation of matrix elements of irreducible representations, the trace, determinant, and general polynomial functions on
U(d). Our technique generalize the Hadamard test and leverage tools from representation theory, yielding both lower and upper bound on sample complexity.
Although a concept class may be learnt more efficiently using quantum samples as compared with classical samples in certain scenarios, quantum learners are asymptotically no more efficient than classical ones in the quantum PAC and Agnostic learning models. Lower bounds on sample complexity in these models were previously established via quantum state identification and Fourier analysis. In this paper, we derive optimal lower bounds for quantum sample complexity in both models via an information-theoretic approach. The proofs are arguably simpler, and the same ideas can potentially be used to derive optimal bounds for other problems in quantum learning theory. We then turn to a quantum analogue of the Coupon Collector problem, a classic problem from probability theory also of importance in the study of PAC learning. The quantum sample complexity of this problem has been characterised up to constant factors. First, we show that the information-theoretic approach mentioned above provably does not yield the optimal lower bound. As a by-product, we get a natural ensemble of pure states in arbitrarily high dimensions which are not easily (simultaneously) distinguishable, whereas the ensemble has close to maximal Holevo information. Second, we discover that the information-theoretic approach yields an asymptotically optimal bound for an approximation variant of the problem. Finally, we derive a sharper lower bound for the Quantum Coupon Collector problem via the generalised Holevo-Curlander bounds. All the aspects of the problem we study rest on properties of the spectrum of the associated Gram matrix, which may be of independent interest.