{
  "abstract": "Linear threshold functions are $f_{w,θ}(x)=\\text{sign}(\\langle x,w \\rangle -θ)$, where the weight vector $w\\in\\mathbb{R}^n$ is a unit vector, $θ\\in\\mathbb R$ is a threshold, and typically $x\\in\\mathbb{R}^n$ or $x\\in\\{-1,1\\}^n$. When $θ=0$, the LTF is called homogeneous, and we write $f_w:=f_{w,0}$. Such functions are among the most important objects in machine learning, since they serve to linearly discriminate positive and negative examples. We give three positive results about learning LTFs: 1. Suppose we can make real-domain queries, meaning we can compute $f_{w,θ}(x)$ at any $x\\in\\mathbb{R}^n$ of our choice. We give a quantum algorithm that learns $f_{w,θ}$ up to Euclidean error $ε$ using $O(\\log(n/ε))$ membership queries and $\\widetilde{O}(n)$ other gates. Then we have also learned $f_{w,θ}$ up to error $O(ε)$ when $x$ is Gaussian. Classical algorithms need $Ω(n\\log(1/ε))$ queries. 2. A homogeneous LTF $f_w$ on domain $\\{-1,1\\}^n$ where $w$ has only $k$ nonzero entries of the same value, is the Majority function on the support of $w$. Belovs gave a bounded-error quantum algorithm that identifies the hidden support exactly (and hence learns $f_w$) using $O(k^{1/4})$ queries. We give an exponential improvement, using $O(\\log k)$ queries. 3. Suppose we have a unitary $U$ that can produce (discretized) quantum examples under Gaussian measure, corresponding to $\\int_x \\sqrt{γ_n(x)}|x\\rangle |f_w(x)\\rangle dx$. This is a weaker access model than membership queries. We give a quantum algorithm based on the efficient Hermite transform of Jain et al. to learn homogeneous LTFs $f_w$ with error $ε$ under the Gaussian distribution, using $O(n^{1/4}/\\sqrtε)$ applications of $U$ and $U^\\dagger$ and $\\widetilde{O}(n^2/ε^4)$ other gates.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.40331",
  "author_total": 3,
  "authors": [
    {
      "name": "Aleksandrs Krivcenko"
    },
    {
      "name": "Tuyen Nguyen"
    },
    {
      "name": "Ronald de Wolf"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/fzv3s86bwa9fm.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.40331",
  "fulltext_url": null,
  "id": "fzv3s86bwa9fm",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.40331",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "quant-ph"
    ],
    [
      "openalex",
      "1702|Quantum Computing Algorithms and Architecture"
    ]
  ],
  "openalex": "W7215120799",
  "pdf_url": "https://arxiv.org/pdf/2609.40331",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-05",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/fzv3s86bwa9fm.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:27:01Z",
      "native_id": "2609.40331",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.40331"
    }
  ],
  "subjects": [
    {
      "field": "physics",
      "origin": "arxiv:quant-ph",
      "subfield": "quantum"
    }
  ],
  "title": "Fast Quantum Algorithms for Learning Linear Threshold Functions",
  "title_text": "Fast Quantum Algorithms for Learning Linear Threshold Functions",
  "type": "preprint",
  "updated_at": "2026-11-06T18:21:01Z",
  "url": "https://research.draconitic.com/paper/fzv3s86bwa9fm",
  "venue": "arXiv",
  "versions": []
}