Universal Sample Complexity Bounds in Quantum Learning Theory via Fisher Information matrix

• URL: http://arxiv.org/abs/2602.21510v1
• Date: Wed, 25 Feb 2026 02:51:49 GMT
• Title: Universal Sample Complexity Bounds in Quantum Learning Theory via Fisher Information matrix
• Authors: Hyukgun Kwon, Seok Hyung Lie, Liang Jiang,
• Abstract summary: We show that the sample complexity required in quantum learning theory is governed by the inverse Fisher information matrix.<n>We identify the structural origin of exponential sample complexity in Pauli channel learning without entanglement.<n>As an application, we consider Pauli expectation estimation with entangled probes.
• Score: 0.6738870040008694
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we show that the sample complexity (equivalently, the number of measurements) 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 and with high success probability under maximum likelihood estimation. The upper bound is governed by the supremum of the largest diagonal entry of the inverse Fisher information matrix, while the lower bound is characterized by any diagonal element evaluated at arbitrary parameter values. We then apply the general bounds to Pauli channel learning and to the estimation of Pauli expectation values in the asymptotic small-error regime, and recover the previously established sample complexity through considerably streamlined derivations. Furthermore, we identify the structural origin of exponential sample complexity in Pauli channel learning without entanglement and in Pauli expectation value estimation without quantum memory. We then extend the analysis to an error criterion based on the Euclidean distance between the true parameter values and their estimators. We derive 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 expectation estimation with entangled probes. Finally, 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, learning sample complexity is governed by the inverse Fisher information matrix.

Related papers

• Training-Free Certified Bounds for Quantum Regression: A Scalable Framework [0.0]
  We present a training-free, certified error bound for quantum regression derived from Pauli expectation values.<n>We provide non-asymptotic statistical guarantees to certify performance within a practical measurement budget.
  arXiv  Detail & Related papers  (2026-01-02T17:05:48Z)
• Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning [50.81240969750462]
  We present first finite-sample analysis of policy evaluation in robust average Markov Decision Processes (PMDs)<n>We show that the robust Bellman operator is a contraction under a carefully constructed semi-norm, and developing a framework with controlled bias.<n>Our method achieves the order-optimal sample complexity of $tildemathcalO(epsilon-2)$ for robust policy evaluation and robust average reward estimation.
  arXiv  Detail & Related papers  (2025-02-24T03:55:09Z)
• Reducing the sampling complexity of energy estimation in quantum many-body systems using empirical variance information [45.18582668677648]
  We consider the problem of estimating the energy of a quantum state preparation for a given Hamiltonian in Pauli decomposition.<n>We construct an adaptive estimator using the state's actual variance.
  arXiv  Detail & Related papers  (2025-02-03T19:00:01Z)
• Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods [59.779795063072655]
  Chain-of-Thought (CoT) prompting and its variants have gained popularity as effective methods for solving multi-step reasoning problems. We analyze CoT prompting from a statistical estimation perspective, providing a comprehensive characterization of its sample complexity.
  arXiv  Detail & Related papers  (2024-08-25T04:07:18Z)
• Expectation value estimation with parametrized quantum circuits [5.705564993120308]
  Estimating properties of quantum states, such as fidelities, molecular energies, and correlation functions, is a fundamental task in quantum information science.<n>Due to the limitation of practical quantum devices, including limited circuit depth and connectivity, estimating even linear properties encounters high sample complexity.<n>We propose a framework that optimize sample complexity for estimating the expectation value of any observable using a shallow parameterized quantum circuit.
  arXiv  Detail & Related papers  (2024-07-28T14:04:33Z)
• Quantum metrology in the finite-sample regime [0.6299766708197883]
  In quantum metrology, the ultimate precision of estimating an unknown parameter is often stated in terms of the Cram'er-Rao bound. We propose to quantify the quality of a protocol by the probability of obtaining an estimate with a given accuracy.
  arXiv  Detail & Related papers  (2023-07-12T18:00:04Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Tight Exponential Analysis for Smoothing the Max-Relative Entropy and for Quantum Privacy Amplification [56.61325554836984]
  The max-relative entropy together with its smoothed version is a basic tool in quantum information theory. We derive the exact exponent for the decay of the small modification of the quantum state in smoothing the max-relative entropy based on purified distance.
  arXiv  Detail & Related papers  (2021-11-01T16:35:41Z)
• Sampling Overhead Analysis of Quantum Error Mitigation: Uncoded vs. Coded Systems [69.33243249411113]
  We show that Pauli errors incur the lowest sampling overhead among a large class of realistic quantum channels. We conceive a scheme amalgamating QEM with quantum channel coding, and analyse its sampling overhead reduction compared to pure QEM.
  arXiv  Detail & Related papers  (2020-12-15T15:51:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.