Sample Complexity of Composite Quantum Hypothesis Testing

• URL: http://arxiv.org/abs/2601.08588v2
• Date: Thu, 15 Jan 2026 16:07:59 GMT
• Title: Sample Complexity of Composite Quantum Hypothesis Testing
• Authors: Jacob Paul Simpson, Efstratios Palias, Sharu Theresa Jose,
• Abstract summary: We characterize the sample complexity of symmetric composite binary quantum hypothesis testing.<n>Specifically, we derive lower bounds that generalize the sample complexity of simple QHT.<n>We extend our analysis to the differentially private setting, establishing the sample complexity for privacy-preserving composite QHT.
• Score: 1.376408511310322
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper investigates symmetric composite binary quantum hypothesis testing (QHT), where the goal is to determine which of two uncertainty sets contains an unknown quantum state. While asymptotic error exponents for this problem are well-studied, the finite-sample regime remains poorly understood. We bridge this gap by characterizing the sample complexity -- the minimum number of state copies required to achieve a target error level. Specifically, we derive lower bounds that generalize the sample complexity of simple QHT and introduce new upper bounds for various uncertainty sets, including of both finite and infinite cardinalities. Notably, our upper and lower bounds match up to universal constants, providing a tight characterization of the sample complexity. Finally, we extend our analysis to the differentially private setting, establishing the sample complexity for privacy-preserving composite QHT.

Related papers

• Phase-space complexity of discrete-variable quantum states and operations [0.0]
  We introduce a quantifier of phase-space complexity for discrete-variable quantum systems.<n>The complexity is normalized such that coherent states have unit complexity, while the completely mixed state has zero complexity.<n>We extend the framework to quantum channels, defining measures for both the generation and breaking of complexity.
  arXiv  Detail & Related papers  (2026-03-03T19:00:02Z)
• Quantum Sequential Universal Hypothesis Testing [62.751483592497806]
  Quantum hypothesis testing (QHT) concerns the statistical inference of unknown quantum states.<n>We introduce the quantum sequential universal test (QSUT), a novel framework for sequential QHT in the general case of composite hypotheses.<n> QSUT builds on universal inference, and it alternates between adaptive local measurements aimed at exploring the hypothesis space and joint measurements optimized for maximal discrimination.
  arXiv  Detail & Related papers  (2025-08-29T12:50:04Z)
• Quantum Chaos Diagnostics for Open Quantum Systems from Bi-Lanczos Krylov Dynamics [2.0603431589684518]
  In Hermitian systems, Krylov complexity has emerged as a powerful diagnostic of quantum dynamics.<n>Here, we demonstrate that Krylov complexity, computed via the bi-Lanczos algorithm, effectively identifies chaotic and integrable phases in open quantum systems.
  arXiv  Detail & Related papers  (2025-08-19T15:49:09Z)
• On The Sample Complexity Bounds In Bilevel Reinforcement Learning [49.19950489963245]
  Bilevel reinforcement learning (BRL) has emerged as a powerful framework for aligning generative models.<n>We present the first sample of $mathcalO(epsilon)$ in continuous state-action complexity.<n>Our analysis also extends complexity improving upon existing bounds of $mathcalO(epsilon)$.
  arXiv  Detail & Related papers  (2025-03-22T04:22:04Z)
• Sample Complexity of Locally Differentially Private Quantum Hypothesis Testing [10.14555083237668]
  We provide achievability and converse bounds for different settings. This includes symmetric state discrimination in various regimes and the asymmetric case. An important tool in this endeavor are new entropy inequalities that we believe to be of independent interest.
  arXiv  Detail & Related papers  (2024-06-26T18:00:19Z)
• An invitation to the sample complexity of quantum hypothesis testing [15.499012185410662]
  We study the sample complexity of quantum hypothesis testing (QHT)<n>We characterize the sample complexity of binary QHT in the symmetric and asymmetric settings.<n>We provide bounds on the sample complexity of multiple QHT.
  arXiv  Detail & Related papers  (2024-03-26T16:57:01Z)
• Taming Quantum Time Complexity [45.867051459785976]
  We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
  arXiv  Detail & Related papers  (2023-11-27T14:45:19Z)
• The Complexity of Being Entangled [0.0]
  Nielsen's approach to quantum state complexity relates the minimal number of quantum gates required to prepare a state to the length of geodesics computed with a certain norm on the manifold of unitary transformations. For a bipartite system, we investigate binding complexity, which corresponds to norms in which gates acting on a single subsystem are free of cost.
  arXiv  Detail & Related papers  (2023-11-07T19:00:02Z)
• An Analysis of On-the-fly Determinization of Finite-state Automata [65.268245109828]
  We establish an abstraction of on-the-fly determinization of finite-state automata and demonstrate how it can be applied to bound the automatons. A special case of our findings is that automata with many non-deterministic transitions almost always admit a determinization of complexity.
  arXiv  Detail & Related papers  (2023-08-27T11:51:27Z)
• 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)
• A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability [57.502573663108535]
  We study the problem of learning an adversarially robust predictor to test time attacks in the semi-supervised PAC model. We show that there is a significant benefit in semi-supervised robust learning even in the worst-case distribution-free model.
  arXiv  Detail & Related papers  (2022-02-11T03:01:45Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  We propose a novel technique for analyzing adaptive sampling called the em Simulator. We prove the first instance-based lower bounds the top-k problem which incorporate the appropriate log-factors. Our new analysis inspires a simple and near-optimal for the best-arm and top-k identification, the first em practical of its kind for the latter problem.
  arXiv  Detail & Related papers  (2017-02-16T23:42:02Z)

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.