{
  "abstract": "We present a quantum algorithm that generates a uniform superposition over the spanning trees of a graph -also known as a q-sample -using only a sublinear number of queries to the graph. This goes beyond previous work that focuses on generating classical samples, including a recent quantum algorithm by Apers, Gao, Ji, and Liu [AGJL25]. For an nvertex, m-edge graph, our algorithm admits a pre-processing step of ˜︁ O( √ mn + m 1-δ ), after which each q-sample can be generated in ˜︁ O(n 1+2δ ) for any δ. Alternatively, k independent q-samples can be generated at a total cost of ˜︁ O( √ kmn). We also prove a matching lower bound up to logarithmic factors, showing that our algorithm is essentially optimal. Further tradeoffs are given in the paper. In comparison, the optimal classical algorithms [ALV22] need an ˜︁ O(m) pre-processing step, after which each sample costs ˜︁ O(n) operations. These results yield faster quantum walk-based algorithms for counting spanning trees or finding a marked one. Our result is obtained via quantum walk sampling over a sequence of slowly-changing Markov chains. Each chain is an isotropized up-down walk that mixes rapidly to the spanning tree distribution of the input graph. A key ingredient is an amortized data structure supporting fast implementation of the associated quantum walk operators throughout the sequence. This data structure maintains access to a spectral sparsifier and a leverage score sampler that evolve with the underlying graph.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.40314",
  "author_total": 3,
  "authors": [
    {
      "name": "Yassine Hamoudi"
    },
    {
      "name": "Adrian Tanasa"
    },
    {
      "name": "Shrinidhi Teganahally Sridhara"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/9vc5kxv9ch3wp.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.40314",
  "fulltext_url": null,
  "id": "9vc5kxv9ch3wp",
  "issns": [],
  "landing_url": "https://hal.science/hal-05800605v1",
  "language": "en",
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "https://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "quant-ph"
    ],
    [
      "hal",
      "0.info"
    ],
    [
      "hal",
      "0.phys"
    ],
    [
      "hal",
      "1.info.info-ds"
    ],
    [
      "hal",
      "1.phys.qphy"
    ],
    [
      "openalex",
      "1702|Quantum Computing Algorithms and Architecture"
    ]
  ],
  "openalex": "W7215124440",
  "pdf_url": "https://hal.science/hal-05800605/document",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-30",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/9vc5kxv9ch3wp.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:17:57Z",
      "native_id": "hal-05800605",
      "source": "hal",
      "url": "https://hal.science/hal-05800605v1"
    },
    {
      "first_seen": "2026-10-30T12:25:49Z",
      "native_id": "2609.40314",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.40314"
    }
  ],
  "subjects": [
    {
      "field": "physics",
      "origin": "arxiv:quant-ph",
      "subfield": "quantum"
    }
  ],
  "title": "Quantum Sampling of Random Spanning Trees via Amortized Data Structures",
  "title_text": "Quantum Sampling of Random Spanning Trees via Amortized Data Structures",
  "type": "preprint",
  "updated_at": "2026-10-30T12:25:49Z",
  "url": "https://research.draconitic.com/paper/9vc5kxv9ch3wp",
  "venue": "HAL",
  "versions": []
}