Certified Lower Bounds and Efficient Estimation of Minimum Accuracy in Quantum Kernel Methods

• URL: http://arxiv.org/abs/2512.20588v1
• Date: Tue, 23 Dec 2025 18:34:58 GMT
• Title: Certified Lower Bounds and Efficient Estimation of Minimum Accuracy in Quantum Kernel Methods
• Authors: Demerson N. Gonçalves, Tharso D. Fernandes, Andrias M. M. Cordeiro, Pedro H. G. Lugao, João T. Dias,
• Abstract summary: The minimum accuracy evaluates quantum feature maps without requiring full quantum support vector machine (QSVM) training.<n>This work generalizes the metric to arbitrary binary datasets and formally proves it constitutes a certified lower bound on the optimal empirical accuracy of any linear classifier in the same feature space.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The minimum accuracy heuristic evaluates quantum feature maps without requiring full quantum support vector machine (QSVM) training. However, the original formulation is computationally expensive, restricted to balanced datasets, and lacks theoretical backing. This work generalizes the metric to arbitrary binary datasets and formally proves it constitutes a certified lower bound on the optimal empirical accuracy of any linear classifier in the same feature space. Furthermore, we introduce Monte Carlo strategies to efficiently estimate this bound using a random subset of Pauli directions, accompanied by rigorous probabilistic guarantees. These contributions establish minimum accuracy as a scalable, theoretically sound tool for pre-screening feature maps on near-term quantum devices.

Related papers

• Kernel-based optimization of measurement operators for quantum reservoir computers [5.486630950557179]
  We formulate the training of both stateless (quantum extreme learning machines, QELMs) and stateful (memory dependent) QRCs in the framework of kernel ridge regression.<n>This approach renders an optimal measurement operator that minimizes prediction error for a given reservoir and training dataset.
  arXiv  Detail & Related papers  (2026-02-16T12:04:42Z)
• A Posteriori Certification Framework for Generalized Quantum Arimoto-Blahut Algorithms [41.15017547767954]
  We introduce an a posteriori certification viewpoint for the generalized quantum Arimoto-Blahut (QAB) algorithm.<n>We prove a global convergence theorem showing that, under convexity and a substantially weaker numerically verifiable condition, the QAB iteration converges to the global minimizer.<n>As an application, we develop a certified iterative scheme for computing the quantum relative entropy of channels.
  arXiv  Detail & Related papers  (2026-01-14T09:10:41Z)
• Machine learning-aided direct estimation of coherence and entanglement for unknown states [11.587753857811506]
  We present a machine learning approach that directly estimates the coherence measures and the geometric measure of quantum entanglement.<n>The proposed technique provides a practical and scalable tool for characterizing quantum resources across computation, communication, and metrology applications.
  arXiv  Detail & Related papers  (2026-01-08T14:26:50Z)
• 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)
• Saturation of the Multiparameter Quantum Cramér-Rao Bound at the Single-Copy Level with Projective Measurements [0.0]
  It was not known when the quantum Cram'er-Rao bound can be saturated (achieved) when only a single copy of the quantum state is available.<n>In this paper, key structural properties of optimal measurements that saturate the quantum Cram'er-Rao bound are illuminated.
  arXiv  Detail & Related papers  (2024-05-02T17:04:13Z)
• Non-degenerate Marginal-Likelihood Calibration with Application to Quantum Characterization [0.0]
  We propose a novel marginalized likelihood strategy within the Kennedy-O'Hagan (KOH) Bayesian framework.<n>Our method defines an exact likelihood -- distinct from the original but preserving all relevant information.<n>It is applied to the characterization of a superconducting quantum device at Lawrence Livermore National Laboratory.
  arXiv  Detail & Related papers  (2023-08-24T04:39:18Z)
• Robust and efficient verification of graph states in blind measurement-based quantum computation [52.70359447203418]
  Blind quantum computation (BQC) is a secure quantum computation method that protects the privacy of clients. It is crucial to verify whether the resource graph states are accurately prepared in the adversarial scenario. Here, we propose a robust and efficient protocol for verifying arbitrary graph states with any prime local dimension.
  arXiv  Detail & Related papers  (2023-05-18T06:24:45Z)
• Shot-frugal and Robust quantum kernel classifiers [12.146571029233435]
  Quantum kernel methods are a candidate for quantum speed-ups in machine learning. We show that for classification tasks, the aim is reliable classification and not precise kernel evaluation. We motivate a new metric that characterizes the reliability of classification.
  arXiv  Detail & Related papers  (2022-10-13T12:48:23Z)
• Tight Cram\'{e}r-Rao type bounds for multiparameter quantum metrology through conic programming [61.98670278625053]
  It is paramount to have practical measurement strategies that can estimate incompatible parameters with best precisions possible. Here, we give a concrete way to find uncorrelated measurement strategies with optimal precisions. We show numerically that there is a strict gap between the previous efficiently computable bounds and the ultimate precision bound.
  arXiv  Detail & Related papers  (2022-09-12T13:06:48Z)
• 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)
• Bosonic field digitization for quantum computers [62.997667081978825]
  We address the representation of lattice bosonic fields in a discretized field amplitude basis. We develop methods to predict error scaling and present efficient qubit implementation strategies.
  arXiv  Detail & Related papers  (2021-08-24T15:30:04Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  We propose the amortized conditional normalized maximum likelihood (ACNML) method as a scalable general-purpose approach for uncertainty estimation. Our algorithm builds on the conditional normalized maximum likelihood (CNML) coding scheme, which has minimax optimal properties according to the minimum description length principle. We demonstrate that ACNML compares favorably to a number of prior techniques for uncertainty estimation in terms of calibration on out-of-distribution inputs.
  arXiv  Detail & Related papers  (2020-11-05T08:04:34Z)

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.