Sharp bounds for perfect quantum state classification beyond antidistinguishability

• URL: http://arxiv.org/abs/2609.17411v1
• Date: Tue, 15 Sep 2026 16:37:09 GMT
• Title: Sharp bounds for perfect quantum state classification beyond antidistinguishability
• Abstract summary: We prove two universal, and optimal, Gram-matrix criteria for k-learnability.<n>We apply them to derive explicit learnability and copy-complexity guarantees for several well-known sets of states.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A multiset of pure quantum states is said to be k-learnable if there is a measurement strategy that always narrows an unknown sample drawn from the list down to one of at most k candidates. The parameter k interpolates between distinguishability and antidistinguishability, and provides a unified framework for partial state identification. We prove two universal, and optimal, Gram-matrix criteria for k-learnability: a Frobenius-norm sufficient condition and an entrywise-$\ell_1$ necessary condition. We apply them to derive explicit learnability and copy-complexity guarantees for several well-known sets of states including SIC-POVMs, mutually unbiased bases, and stabilizer states. We further apply our results to zero-error mutation detection problems such as anomaly detection and changepoint detection.

Related papers

• Certifying Adversarial Robustness of Quantum Classifiers under Known-Readout Query Access [6.902322288643561]
  A quantum classifier assigns labels by evolving an input quantum state and measuring the output, so repeated executions reveal only a distribution over labels.<n>We give a measurement-only framework that returns two complementary guarantees for each input.<n>From 40 executions of two 8-qubit quantum neural networks, our method estimates both bounds, with the expected lower-upper ordering on every tested input.
  arXiv  Detail & Related papers  (2026-09-10T14:45:21Z)
• Uncertainty equality for SU(N) observables enabling the experimentally friendly detection of k-inseparability via purity measurements [0.0]
  We derive an exact uncertainty relation for arbitrary quantum states of finite-dimensional Hilbert spaces.<n>We then derive a correlation matrix-based necessary condition for $k$-separability of arbitrary finite-dimensional quantum states.<n>Our results shed some further light on the intimate and intricate relation between correlations, entropies, uncertainties, and the entanglement certification and detection problem.
  arXiv  Detail & Related papers  (2026-03-18T15:33:59Z)
• Polynomial-time certification of fidelity for many-body mixed states and mixed-state universality classes [23.9304612104967]
  We introduce a-time algorithm to compute certified lower and upper bounds for fidelity between matrix product density operators.<n>Our results offer an exponential improvement in precision over known moment-based bounds.
  arXiv  Detail & Related papers  (2026-01-19T19:13:28Z)
• Unsupervised Conformal Inference: Bootstrapping and Alignment to Control LLM Uncertainty [49.19257648205146]
  We propose an unsupervised conformal inference framework for generation.<n>Our gates achieve close-to-nominal coverage and provide tighter, more stable thresholds than split UCP.<n>The result is a label-free, API-compatible gate for test-time filtering.
  arXiv  Detail & Related papers  (2025-09-26T23:40:47Z)
• Realignment Criterion: A necessary and sufficient condition for two-qubit $X$-states [0.0]
  We advance the applicability of the realignment criterion by deriving a condition that is both necessary and sufficient for detecting entanglement in two-qubit.<n>$X$-states have proven highly useful in entanglement studies due to their sparse structure and the ease with which entanglement-related quantities can be computed.
  arXiv  Detail & Related papers  (2025-06-30T11:03:40Z)
• COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
  COIN is an uncertainty-guarding selection framework that calibrates statistically valid thresholds to filter a single generated answer per question.<n>COIN estimates the empirical error rate on a calibration set and applies confidence interval methods to establish a high-probability upper bound on the true error rate.<n>We demonstrate COIN's robustness in risk control, strong test-time power in retaining admissible answers, and predictive efficiency under limited calibration data.
  arXiv  Detail & Related papers  (2025-06-25T07:04:49Z)
• Approximate Conditional Coverage via Neural Model Approximations [0.030458514384586396]
  We analyze a data-driven procedure for obtaining empirically reliable approximate conditional coverage. We demonstrate the potential for substantial (and otherwise unknowable) under-coverage with split-conformal alternatives with marginal coverage guarantees.
  arXiv  Detail & Related papers  (2022-05-28T02:59:05Z)
• 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)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• Optimal Adaptive Strategies for Sequential Quantum Hypothesis Testing [87.17253904965372]
  We consider sequential hypothesis testing between two quantum states using adaptive and non-adaptive strategies. We show that these errors decrease exponentially with decay rates given by the measured relative entropies between the two states.
  arXiv  Detail & Related papers  (2021-04-30T00:52:48Z)
• DAGs with No Fears: A Closer Look at Continuous Optimization for Learning Bayesian Networks [45.3591788771536]
  We re-examine a continuous optimization framework dubbed NOTEARS for learning Bayesian networks. We show that the Karush-Kuhn-Tucker optimality conditions for the NOTEARS cannot be satisfied except in a trivial case. Some combinations with local search are both more accurate and more efficient than the original NOTEARS.
  arXiv  Detail & Related papers  (2020-10-18T22:59:37Z)

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.