Pith. sign in

REVIEW 4 major objections 8 minor 24 references

Analysis of the sample complexity for PAC-learning functions defined over quantum states

T0 review · 4 major / 8 minor · reviewed 2026-07-09 · glm-5.2

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read VC-dimension fails to govern quantum-state PAC learning

desk verdict VC-dimension is shown insufficient for quantum PAC learning with labeled quantum states; lower and upper bounds are derived but the gap remains open. read the letter →

arxiv 2607.07572 v1 pith:MJYRK4PJ submitted 2026-07-08 quant-ph

Jordi Pérez-Guijarro This is my paper
classification quant-ph PACS 03.67.Lx
keywords quantumboundmodelpac-learningstatesvc-dimensionclassicalcomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies a PAC-learning variant where training examples are pairs consisting of a quantum state and a label for that state, rather than the classical pair of a bit-string and a label. The central result is that the VC-dimension—the quantity that completely determines sample complexity in classical PAC-learning—no longer suffices in this quantum setting. The author proves this by constructing a concrete concept class over the four BB84 states {|0⟩, |1⟩, |+⟩, |−⟩} that has finite VC-dimension and finite pairwise overlap F, yet is not learnable at all: two distinct concepts induce identical density matrices under the uniform distribution, making them information-theoretically indistinguishable to any algorithm. Beyond the counterexample, the paper develops a general lower bound on sample complexity involving a new function Λ_C built from the quantum Chernoff distance between concept-induced density matrices, and proves an upper bound that recovers a classical-looking form when the domain states are linearly independent, scaling as O((d + ln(1/δ))/(ε·λ_min(G))) where λ_min(G) is the smallest eigenvalue of the Gram matrix of inner products between states. The paper also shows that even granting the learner multiple copies of each quantum state per example does not restore VC-dimension as a sufficient statistic for learnability in general.

What carries the argument

The induced density matrix σ_c^D = E_{|ψ⟩~D}[|ψ⟩⟨ψ| ⊗ |c(|ψ⟩)⟩⟨c(|ψ⟩)|] encodes what an algorithm can statistically extract from quantum examples. Two concepts producing the same σ_c^D are indistinguishable. The lower bound uses the quantum Chernoff distance C_Q(σ, ρ) between such density matrices, aggregated via the function Λ_C(α), which measures the minimum distinguishability of concept-distribution pairs that are far apart in error. The upper bound for linearly independent states uses unambiguous state discrimination (where the Gram matrix eigenvalue λ_min(G) sets the inconclusive probability) to convert quantum examples into classical ones, then applies the standard PAC bound.

What would settle it

If one could exhibit a concept class over linearly dependent quantum states (finite domain, finite VC-dimension, finite F) that is PAC-learnable with a sample complexity matching the classical Θ((d + ln(1/δ))/ε) scaling, the claim that VC-dimension is insufficient would need qualification: the insufficiency would be specific to certain domain geometries rather than a general feature of the quantum-state PAC model. Conversely, if every finite-VC concept class over any finite set of quantum states turned out to require a new parameter beyond (d, F, Λ_C) for characterization, the paper's open-pro

Watch

Extended reading notes

Core claim

The VC-dimension does not characterize sample complexity when PAC-learning examples are labeled quantum states. The failure is not merely quantitative (a worse constant) but qualitative: there exist concept classes with finite VC-dimension that are unlearnable, because distinct concepts can produce identical quantum statistical signatures (density matrices) under some distributions. The paper introduces Λ_C, a function of the quantum Chernoff distance between concept-induced density matrices, as a new quantity that the lower bound requires and that captures this indistinguishability phenomenon. When Λ_C(α) = 0 for relevant α, the concept class is provably unlearnable regardless of how many (

Load-bearing premise

The upper bound (Theorem 2) applies only when the quantum states in the domain are linearly independent, which excludes many physically natural settings—including the BB84 states used in the unlearnability counterexample, which span only a 2-dimensional space. The lower bound applies generally, so there remains a gap between what is known for linearly independent states and what holds for arbitrary domains.

Editorial extensions

If this is right

  • The classical PAC sample complexity formula Θ((d + ln(1/δ))/ε) is not the right benchmark for quantum-state learning; any correct characterization must incorporate information-geometric properties of how concepts map to density matrices, not just combinatorial shattering structure.
  • Concept classes over non-orthogonal quantum states that span a space of dimension smaller than the number of states—physically natural settings like BB84—can be fundamentally unlearnable, establishing a structural barrier distinct from computational hardness.
  • The function Λ_C(α) provides a diagnostic tool: computing or bounding it for a given concept class and domain immediately tells a practitioner whether learning is possible and at what rate.
  • The result that multiple copies per example do not resolve the general unlearnability (Proposition 9) means that the gap between quantum-state learning and classical learning is not a matter of insufficient copies but of adversarial distributional support near indistinguishable state pairs.
  • The upper bound for linearly independent states, scaling with 1/λ_min(G), quantifies how state overlap inflates sample complexity: as states become more similar (λ_min(G) → 0), the required number of examples grows, diverging in the limit where linearly independent states become nearly linearly dependent.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

4 major / 8 minor

Summary. This paper studies a quantum generalization of PAC learning in which examples are pairs (|φ⟩, c(|φ⟩)) consisting of a quantum state and a classical label. The author shows that the VC-dimension alone does not characterize sample complexity in this model. The central counterexample (Proposition 3) uses the BB84-type states {|0⟩, |1⟩, |+⟩, |−⟩}: two distinct concepts induce identical density matrices under the uniform distribution, making them information-theoretically indistinguishable. A lower bound (Theorem 1) is developed via reduction to quantum state discrimination using the quantum Chernoff distance, and an upper bound (Theorem 2) is established for linearly independent states using unambiguous discrimination. The paper also studies a multi-copy variant (|φ⟩^{⊗k}, c(|φ⟩)) and shows that unlearnability persists for infinite domains with F=1.

Significance. The paper addresses a natural and well-motivated question at the interface of learning theory and quantum information. The main conceptual contribution — that VC-dimension is insufficient when examples are quantum states rather than classical labels — is cleanly demonstrated. Proposition 3's counterexample is elegant and correct: the density-matrix indistinguishability argument is airtight. The lower bound (Theorem 1) via the quantum Chernoff distance and the upper bound (Theorem 2) via unambiguous discrimination are technically sound and well-executed. The author provides reproducible code for the numerical plots (Figure 1), which is a strength. The multi-copy extension (Propositions 8–9) adds depth by showing that the VC-dimension's insufficiency persists even with multiple copies for infinite domains. The gap between the lower bound (general) and upper bound (linearly independent states only) is acknowledged honestly.

major comments (4)
  1. §5, Theorem 2 and Appendix E: The upper bound requires linearly independent states, which excludes the BB84-type states used in the central counterexample (Proposition 3). This means the paper does not achieve a tight characterization of sample complexity in general. The author acknowledges this gap, but it is worth noting that the gap is substantial: the lower bound applies to all concept classes while the upper bound applies only to a restricted subclass. The paper would benefit from a brief discussion of whether any intermediate condition (weaker than full linear independence) could bridge this gap, or whether the gap is fundamental.
  2. §3, Proposition 3: The counterexample showing that (d, F) is insufficient is clean, but the broader claim that 'VC-dimension fails to characterize sample complexity' should be framed more carefully. The unlearnability arises because the model provides only a single copy of |φ⟩ per example, and no single measurement can distinguish all four BB84 states. This is a genuine quantum mechanical limitation, but the insufficiency of VC-dimension is a direct consequence of the single-copy restriction. The paper could strengthen its contribution by explicitly stating that the VC-dimension's insufficiency is tied to this model feature, and by noting that Proposition 8 shows learnability is restored with k = O(ln|X| / (−ln max|⟨ψi|ψj⟩|)) copies for finite domains.
  3. §4, Theorem 1, Eq. (13): The definition of Λ_C(α) involves an infimum over distributions D, D' and concepts c, c' satisfying dist_{D,D'}(c, c') > α and d_TV(D, D') ≤ α/6. The constraint d_TV(D, D') ≤ α/6 appears in the definition but the role of this constraint in the proof (Appendix B) is not immediately transparent. In the proof, the condition used is d_TV(D, D') ≤ ε/2 (Eq. 47–50), which with α = 3ε gives d_TV ≤ α/6. This connection should be made explicit in the main text, not only derivable from the appendix, as it is load-bearing for understanding why the constraint takes this specific form.
  4. §6, Proposition 9: The proof constructs a concept class with F=1 over an infinite domain and argues that for any finite k(ε, δ), the sample complexity can be made arbitrarily large. The argument relies on the existence of a sequence of opposite pairs with overlaps approaching 1. While this is correct, the concept class C = {c1, c2} with c1 = S(H)∖c2 is defined implicitly and its VC-dimension is stated to be 1 without explicit verification. A brief justification of the VC-dimension claim would strengthen the proof.
minor comments (8)
  1. §2: The notation t_{Q,C}(ε, δ) is introduced but the subscript formatting is inconsistent throughout the paper (sometimes t_Q,C, sometimes t_{Q,C}). Standardize.
  2. §3, Definition 1: The term 'opposite pair' is defined with respect to a concept class C, but the definition could be confused with the generalized notion in Definition 2. A brief remark distinguishing the two notions would help.
  3. §4, Proposition 5, Eq. (18): The second inequality C_Q(σ, ρ) ≤ ||σ − ρ||_1 is stated and proved, but the proof uses Eq. (20) from [20] and a logarithmic inequality from [21]. The chain of inequalities is correct but could be streamlined for readability.
  4. §5, Eq. (27): The inequality chain λ_min(G) ≤ 1 − max|⟨ψi|ψj⟩| ≤ −ln max|⟨ψi|ψj⟩| ≤ −(1/2)ln F is stated without proof in the main text (proof deferred to Appendix F). A one-line intuition in the main text would help the reader.
  5. Appendix D, Eq. (87): The final inequality −ln(1 − α²/2) ≤ α² uses ln(1+x) ≥ x/(1+x). This is correct but the step from −ln(1 − α²/2) to α² should show the intermediate algebra explicitly, as the bound is not immediately obvious.
  6. Figure 1: The plot shows Λ_C for three concept classes, but the caption does not specify what the x-axis (α) represents in the context of the learning problem. A brief clarification would improve accessibility.
  7. §6, Proposition 8, Eq. (32): The Gershgorin circle theorem is applied to G^(k), but the matrix G^(k)_{i,j} = ⟨ψi|ψj⟩^k is not necessarily Hermitian for odd k if the overlaps are complex. This should be addressed or the claim restricted to real overlaps.
  8. References: The arXiv reference [22] is dated July 8, 2026, which appears to be a future date. This may be a typographical error.

Simulated Author's Rebuttal

4 responses · 0 unresolved

We thank the referee for a careful and constructive report. All four major comments are addressed below; three require revisions (two partial, one full) and one we respectfully decline to revise while explaining why. We agree the paper is fundamentally sound and the referee's suggestions will improve clarity.

read point-by-point responses

  1. Referee: §5, Theorem 2 and Appendix E: The upper bound requires linearly independent states, which excludes the BB84-type states used in the central counterexample (Proposition 3). The gap between the lower bound (general) and upper bound (linearly independent only) is substantial. The paper would benefit from a brief discussion of whether any intermediate condition could bridge this gap, or whether the gap is fundamental.

    Authors: We agree that the gap between the general lower bound and the restricted upper bound deserves more discussion. We will add a paragraph to Section 5 addressing this point. Specifically, we will note that the gap is not merely a technical limitation of the proof technique: the BB84 counterexample of Proposition 3 shows that for linearly dependent states, the quantum Chernoff distance between the induced density matrices can be zero, making the concept class information-theoretically unlearnable regardless of sample size. This means no upper bound of the same form can hold without additional structure. Regarding intermediate conditions: a natural weakening would be to require that the Gram matrix has bounded condition number (i.e., the states are 'approximately' linearly independent in the sense that lambda_min(G) is bounded away from zero). The proof of Theorem 2 extends to this case with the same 1/lambda_min(G) factor, since unambiguous discrimination succeeds with probability proportional to lambda_min(G). However, this does not cover the BB84 setting, where lambda_min(G) = 0. We are not aware of a condition weaker than approximate linear independence that suffices for a general upper bound, and we believe the gap is to a significant extent fundamental, as the lower bound via Lambda_C can be zero for linearly dependent states. We will state this explicitly. revision: partial

  2. Referee: §3, Proposition 3: The broader claim that 'VC-dimension fails to characterize sample complexity' should be framed more carefully. The unlearnability arises because the model provides only a single copy of |φ⟩ per example, and the insufficiency of VC-dimension is a direct consequence of the single-copy restriction. The paper could strengthen its contribution by explicitly stating that the VC-dimension's insufficiency is tied to this model feature, and by noting that Proposition 8 shows learnability is restored with k = O(ln|X| / (−ln max|⟨ψi|ψj⟩|)) copies for finite domains.

    Authors: We agree that the connection between the VC-dimension's insufficiency and the single-copy restriction should be made more explicit. We will add a clarifying remark after Proposition 3 stating that the unlearnability demonstrated there is a consequence of the single-copy model: with only one copy per example, no measurement can simultaneously distinguish all four BB84 states, leading to identical induced density matrices for distinct concepts. We will also add a forward reference to Proposition 8, noting that for finite domains, learnability is restored when k = O(ln|X| / (−ln max_{i≠j} |⟨ψi|ψj⟩|)) copies are provided, and that this is consistent with the single-copy limitation being the source of the insufficiency. However, we will also note (as Proposition 9 shows) that for infinite domains, the insufficiency persists even when k is allowed to depend on epsilon and delta, so the single-copy restriction is not the whole story. revision: yes

  3. Referee: §4, Theorem 1, Eq. (13): The constraint d_TV(D, D') ≤ α/6 appears in the definition of Λ_C(α) but its role in the proof (Appendix B) is not immediately transparent. In the proof, the condition used is d_TV(D, D') ≤ ε/2 (Eq. 47–50), which with α = 3ε gives d_TV ≤ α/6. This connection should be made explicit in the main text, not only derivable from the appendix.

    Authors: We agree. The substitution alpha = 3*epsilon, which converts the proof's condition d_TV(D, D') <= epsilon/2 into the definition's d_TV(D, D') <= alpha/6, is load-bearing for understanding the theorem statement and should be stated in the main text. We will add an explicit sentence after the definition of Lambda_C(alpha) in Theorem 1 explaining this connection: 'The constraint d_TV(D, D') <= alpha/6 arises from setting alpha = 3*epsilon in the proof (Appendix B), where the condition d_TV(D, D') <= epsilon/2 is used to ensure that the learning algorithm's hypothesis distinguishes between the two concepts (Eqs. 47–50).' revision: yes

  4. Referee: §6, Proposition 9: The concept class C = {c1, c2} with c1 = S(H)∖c2 is defined implicitly and its VC-dimension is stated to be 1 without explicit verification. A brief justification of the VC-dimension claim would strengthen the proof.

    Authors: We will add a brief justification. The concept class C = {c1, c2} with c1 = S(H) ∖ c2 and c2 a proper subset of S(H) has VC-dimension 1 because: (i) any single state |ψ⟩ can be shattered, since if |ψ⟩ ∈ c2 then c1(|ψ⟩) = 0 and c2(|ψ⟩) = 1, and if |ψ⟩ ∉ c2 then c1(|ψ⟩) = 1 and c2(|ψ⟩) = 0, so both labelings of {|ψ⟩} are realized; and (ii) no pair of states {|ψ1⟩, |ψ2⟩} can be shattered, since c2 is a single fixed subset and c1 is its complement, yielding only two possible labelings of any pair (either (c2(|ψ1⟩), c2(|ψ2⟩)) or (1−c2(|ψ1⟩), 1−c2(|ψ2⟩))), which cannot cover all four labelings. We will include this argument in the proof of Proposition 9. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found. The derivation chain is self-contained against external benchmarks.

full rationale

The paper's main results are derived from standard information-theoretic arguments using externally sourced tools: the quantum Chernoff bound from Audenaert et al. [20] and unambiguous state discrimination from Chefles [23]. The lower bounds (Proposition 1, Theorem 1) follow from the requirement that any learner must distinguish between density matrices σ_c^D and σ_c'^D', with the quantum Chernoff bound providing the information-theoretic limit — this is a genuine lower bound, not a fit renamed as prediction. The upper bound (Theorem 2) constructs an explicit algorithm that converts quantum examples to classical ones via unambiguous discrimination, then applies classical PAC bounds — a genuine construction. Proposition 3's counterexample is a direct computation (σ_c1 = σ_c2 = τ⊗2) showing information-theoretic indistinguishability. The quantities Λ_C, F, and B_C are defined in terms of problem structure (concept classes, distributions, state overlaps) and are not fitted to data. The only self-citation is [22], which points to the author's GitHub repository for code generating Figure 1; this is not load-bearing for any theoretical claim. No step in the derivation chain reduces to its own inputs by construction.

Assumptions & free parameters 2 free parameters · 4 assumptions · 3 invented entities

The paper is a theory paper in quantum learning theory. The central claims are well-supported by detailed proofs in the appendices. The main results — VC-dimension insufficiency, the Λ_C lower bound, and the linearly-independent upper bound — are new and technically sound. The paper is honest about the gap between lower and upper bounds and does not overclaim. No critical red flags are present.

free parameters (2)
  • c_L, c_U = unspecified constants
    Constants in the lower and upper bounds that are independent of the concept class but not numerically specified, following standard PAC-learning convention.
  • α (in Theorem 2 proof) = chosen in (0,1) depending on C
    A free parameter in the unambiguous discrimination algorithm that trades off between the number of quantum examples and the probability of obtaining enough classical samples. The proof shows a suitable value exists but does not specify it.
assumptions (4)
  • standard math The quantum Chernoff bound (equation (6) from [20]) provides the optimal asymptotic error exponent for distinguishing two quantum states.
    Used in the proof of Theorem 1 (Appendix B, equation (53)) to relate the PAC learning condition to state distinguishability. This is a well-established result in quantum information theory.
  • standard math Linearly independent quantum states can be unambiguously discriminated (Lemma 1 from [23]).
    Used in the proof of Theorem 2 (Appendix E) to convert quantum examples to classical ones. This is a standard result in quantum state discrimination.
  • standard math The classical PAC sample complexity is characterized by VC-dimension (equation (3)).
    Used as the baseline for both lower bounds (via reduction) and upper bounds (via conversion to classical problem). This is the foundational result of classical learning theory.
  • domain assumption The quantum PAC-learning model with examples (|ϕ⟩, c(|ϕ⟩)) is a meaningful generalization of classical PAC learning.
    The entire paper is built on this model, introduced in [13,14]. The model assumes that the learner receives quantum states as examples but must output a hypothesis that generalizes over the distribution of quantum states.
invented entities (3)
  • Λ_C(α) — quantum Chernoff-based distinguishability function independent evidence
    purpose: Captures the information-theoretic hardness of distinguishing concepts in the quantum PAC model, replacing the role of VC-dimension alone.
    Defined via the quantum Chernoff distance between induced density matrices (equation (13)), which is a well-established quantity. The function makes falsifiable predictions about sample complexity that can be checked against specific concept classes (as done in Propositions 4, 5, 7).
  • F — supremum of squared overlap of opposite pairs independent evidence
    purpose: A simpler scalar quantity that partially captures quantum hardness, analogous to but weaker than Λ_C.
    Defined in terms of inner products between quantum states (Definition 1), which are physical quantities. Proposition 1 shows it provides a valid lower bound, and Proposition 3 shows it is insufficient alone.
  • B_C — generalized opposite-pair Chernoff constant independent evidence
    purpose: A constant upper-bounding Λ_C(α), intended as a simpler summary of the function's behavior.
    Defined via the quantum Chernoff distance between opposite-pair density matrices (equation (24)). Proposition 7 shows it is insufficient to characterize sample complexity, as the rate of change of Λ_C matters.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Analysis of the sample complexity for PAC-learning functions defined over quantum states." pith.science (2026). https://pith.science/paper/MJYRK4PJ

@misc{pith2026260707572,
  author       = {Pith},
  title        = {Pith review of: Analysis of the sample complexity for PAC-learning functions defined over quantum states},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MJYRK4PJ}},
  note         = {Machine review of arXiv:2607.07572}
}
read the original abstract

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.

Figures

Figures reproduced from arXiv: 2607.07572 by the authors.

Figure 1
Figure 1. Plot of the function ΛC for the concept classes C1 = 2{|0⟩,|+⟩} , C2 = 2{|0⟩,|+⟩,|+y⟩} , and C3 = 2{|0⟩,|1⟩,|+⟩,|+y⟩}, along with the upper bound min{− ln F, 2α}. The code used to generate this figure is available at [22]. Therefore, ΛC(α) is always bounded by the constant − ln F. This can be seen clearly in [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    A theory of the learnable,

    L. G. Valiant, “A theory of the learnable,”Communications of the ACM, vol. 27, no. 11, pp. 1134–1142, 1984

    work page 1984

  2. [2]

    Learnability and the vapnik-chervonenkis dimension,

    A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth, “Learnability and the vapnik-chervonenkis dimension,”Journal of the ACM (JACM), vol. 36, no. 4, pp. 929–965, 1989

    work page 1989

  3. [3]

    Learning from noisy examples,

    D. Angluin and P. Laird, “Learning from noisy examples,”Machine learning, vol. 2, no. 4, pp. 343–370, 1988

    work page 1988

  4. [4]

    Guest column: A survey of quantum learning theory,

    S. Arunachalam and R. De Wolf, “Guest column: A survey of quantum learning theory,”ACM Sigact News, vol. 48, no. 2, pp. 41–67, 2017

    work page 2017

  5. [5]

    Learning dnf over the uniform distribution using a quantum example oracle,

    N. H. Bshouty and J. C. Jackson, “Learning dnf over the uniform distribution using a quantum example oracle,” inProceedings of the eighth annual conference on Computational learning theory, pp. 118–127, 1995

    work page 1995

  6. [6]

    A general lower bound on the number of examples needed for learning,

    A. Ehrenfeucht, D. Haussler, M. Kearns, and L. Valiant, “A general lower bound on the number of examples needed for learning,”Information and Computation, vol. 82, no. 3, pp. 247–261, 1989

    work page 1989

  7. [7]

    Vapnik,Estimation of dependences based on empirical data

    V. Vapnik,Estimation of dependences based on empirical data. Springer Science & Business Media, 2006

    work page 2006

  8. [8]

    An almost optimal pac algorithm,

    H. U. Simon, “An almost optimal pac algorithm,” inConference on Learning Theory, pp. 1552–1563, PMLR, 2015

    work page 2015

Show all 24 references
  1. [9]

    The optimal sample complexity of pac learning,

    S. Hanneke, “The optimal sample complexity of pac learning,”Journal of Ma- chine Learning Research, vol. 17, no. 38, pp. 1–15, 2016. 11

    2016

  2. [10]

    Optimal quantum sample complexity of learn- ing algorithms,

    S. Arunachalam and R. De Wolf, “Optimal quantum sample complexity of learn- ing algorithms,”The Journal of Machine Learning Research, vol. 19, no. 1, pp. 2879–2878, 2018

    2018

  3. [11]

    Equivalences and separations between quantum and classical learnability,

    R. A. Servedio and S. J. Gortler, “Equivalences and separations between quantum and classical learnability,”SIAM Journal on Computing, vol. 33, no. 5, pp. 1067– 1092, 2004

    2004

  4. [12]

    Provable advantage in quantum pac learning,

    W. Salmon, S. Strelchuk, and T. Gur, “Provable advantage in quantum pac learning,”arXiv preprint arXiv:2309.10887, 2023

    2023 arXiv

  5. [13]

    Machine learning in a quantum world,

    E. A¨ ımeur, G. Brassard, and S. Gambs, “Machine learning in a quantum world,” inConference of the Canadian society for computational studies of intelligence, pp. 431–442, Springer, 2006

    2006

  6. [14]

    Quantum classification,

    S. Gambs, “Quantum classification,”arXiv preprint arXiv:0809.0444, 2008

    2008 arXiv

  7. [15]

    Quantum learning: asymptotically optimal clas- sification of qubit states,

    M. Gut ¸˘ a and W. Kot lowski, “Quantum learning: asymptotically optimal clas- sification of qubit states,”New Journal of Physics, vol. 12, no. 12, p. 123032, 2010

    2010

  8. [16]

    Quantum learning without quantum memory,

    G. Sent´ ıs, J. Calsamiglia, R. Munoz-Tapia, and E. Bagan, “Quantum learning without quantum memory,”Scientific reports, vol. 2, no. 1, p. 708, 2012

    2012

  9. [17]

    A theoretical framework for learning from quantum data,

    M. Heidari, A. Padakandla, and W. Szpankowski, “A theoretical framework for learning from quantum data,” in2021 IEEE international symposium on infor- mation theory (ISIT), pp. 1469–1474, IEEE, 2021

    2021

  10. [18]

    New bounds on quantum sample complexity of measurement classes,

    M. Heidari and W. Szpankowski, “New bounds on quantum sample complexity of measurement classes,” in2024 IEEE International Symposium on Information Theory (ISIT), pp. 1515–1520, IEEE, 2024

    2024

  11. [19]

    Learning k-qubit quantum operators via pauli decomposition,

    M. Heidari and W. Szpankowski, “Learning k-qubit quantum operators via pauli decomposition,” inInternational Conference on Artificial Intelligence and Statis- tics, pp. 490–504, PMLR, 2023

    2023

  12. [20]

    Discriminating states: The quantum chernoff bound,

    K. M. Audenaert, J. Calsamiglia, R. Munoz-Tapia, E. Bagan, L. Masanes, A. Acin, and F. Verstraete, “Discriminating states: The quantum chernoff bound,”Physical review letters, vol. 98, no. 16, p. 160501, 2007

    2007

  13. [21]

    Some bounds for the logarithmic function,

    F. Topsøe, “Some bounds for the logarithmic function,”Inequality theory and applications, vol. 4, no. 01, 2007

    2007

  14. [22]

    Code and data: Analysis of the sam- ple complexity for pac-learning functions defined over quan- tum states

    J. P´ erez-Guijarro, “Code and data: Analysis of the sam- ple complexity for pac-learning functions defined over quan- tum states.”https://github.com/Jordi-Perez-Guijarro/ code-sample-complexity-for-PAC-learning-over-quantum-states. July 8, 2026

    2026

  15. [23]

    Unambiguous discrimination between linearly independent quantum states,

    A. Chefles, “Unambiguous discrimination between linearly independent quantum states,”Physics Letters A, vol. 239, no. 6, pp. 339–347, 1998

    1998

  16. [24]

    Mitzenmacher and E

    M. Mitzenmacher and E. Upfal,Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017. Appendices A Proof of Proposition 1 In this appendix, we provide the proof of Proposition 1, restated here for ...

    2017

Pith tools

Reviewed July 9, 2026 · model on record in the stance chip above.