Quantum Speedup for Sampling Random Spanning Trees

Apers, Simon; Gao, Minbo; Ji, Zhengfeng; Liu, Chenghua

doi:10.4230/LIPIcs.ICALP.2025.13

Quantum Speedup for Sampling Random Spanning Trees

Simon Apers Université Paris Cité, CNRS, IRIF, Paris, France Minbo Gao Key Laboratory of System Software (Chinese Academy of Sciences) and State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
University of Chinese Academy of Sciences, Beijing, China Zhengfeng Ji Department of Computer Science and Technology, Tsinghua University, Beijing, China Chenghua Liu Key Laboratory of System Software (Chinese Academy of Sciences) and State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
University of Chinese Academy of Sciences, Beijing, China

Abstract

We present a quantum algorithm for sampling random spanning trees from a weighted graph in $\widetilde{O}(\sqrt{mn})$ time, where $n$ and $m$ denote the number of vertices and edges, respectively. Our algorithm has sublinear runtime for dense graphs and achieves a quantum speedup over the best-known classical algorithm, which runs in $\widetilde{O}(m)$ time. The approach carefully combines, on one hand, a classical method based on “large-step” random walks for reduced mixing time and, on the other hand, quantum algorithmic techniques, including quantum graph sparsification and a sampling-without-replacement variant of Hamoudi’s multiple-state preparation. We also establish a matching lower bound, proving the optimality of our algorithm up to polylogarithmic factors. These results highlight the potential of quantum computing in accelerating fundamental graph sampling problems.

Keywords and phrases:

Quantum Computing, Quantum Algorithms, Random Spanning Trees

Category:

Track A: Algorithms, Complexity and Games

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Design and analysis of algorithms ; Theory of computation

\rightarrow

Quantum computation theory

Acknowledgements:

We would like to thank Yang P. Liu for explaining the details of their work. Minbo Gao and Chenghua Liu would like to thank Sebastian Zur for helpful discussions on quantum random walks and quantum sampling algorithms. Minbo Gao would like to thank Jingqin Yang for discussions of link-cut trees used in previous spanning tree sampling algorithms.

Funding:

The work is supported by National Key Research and Development Program of China (Grant No. 2023YFA1009403), National Natural Science Foundation of China (Grant No. 12347104), and Beijing Natural Science Foundation (Grant No. Z220002). SA was supported in part by the European QuantERA project QOPT (ERA-NET Cofund 2022-25), the French PEPR integrated projects EPiQ (ANR-22-PETQ-0007) and HQI (ANR-22-PNCQ-0002), and the French ANR project QUOPS (ANR-22-CE47-0003-01).

DOI:

10.4230/LIPIcs.ICALP.2025.13

Event:

52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Editors:

Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Random spanning trees are among the oldest and most extensively studied probabilistic structures in graph theory, with their origins tracing back to Kirchhoff’s matrix-tree theorem from the 1840s [40]. This foundational result established a profound connection between spanning tree distributions and matrix determinants. Beyond graph theory, random spanning trees are deeply intertwined with probability theory [48] and exemplify strongly Rayleigh distributions [15]. Intriguingly, sampling random spanning trees has revealed unexpected and remarkable connections to various areas of theoretical computer science. Notably, they have been instrumental in breakthroughs that overcame long-standing approximation barriers for both the symmetric [31] and asymmetric versions of the Traveling Salesman Problem [12]. Goyal, Rademacher and Vempala [32] demonstrated their utility in constructing cut sparsifiers. Beyond their significance in theoretical computer science, random spanning trees also play a crucial role in machine learning and statistics. They have been applied to a wide range of tasks, including graph prediction [17], network activation detection [58], spatial clustering [60], online recommendation systems [37], and causal structure learning [26, 53].

Given its significant theoretical importance and broad applications, the problem of sampling random spanning trees has attracted substantial research interest, leading to a series of advancements in performance and algorithmic techniques [34, 16, 3, 44, 61, 19, 39, 49, 36, 27, 28, 57, 9]. These contributions can be broadly categorized into three main approaches:

$\blacksquare$

Determinant calculation approaches [34, 44, 19]: These methods build on Kirchhoff’s matrix-tree theorem, which states that the total number of spanning trees in a weighted graph is equal to any cofactor of its graph Laplacian. Leveraging this theorem, one can calculate determinants to randomly select an integer between 1 and the total number of spanning trees and efficiently map this integer to a unique tree. This approach was first employed by Guenoche [34] and Kulkarni [44] to develop an $O(mn^{3})$ time algorithm, where $m$ and $n$ denote the number of edges and vertices in the graph, respectively. Later, Colbourn, Myrvold, and Neufeld [19] improved it to an $O(n^{\omega})$ time algorithm, where $\omega\approx 2.37$ is the matrix multiplication exponent.
$\blacksquare$

Approaches based on effective resistances [36, 27, 28]: The core insights behind there approaches is that the marginal probability of an edge being in a random spanning tree is exactly equal to the product of the weight and the effective resistance of the edge. Harvey and Xu [36] proposed a deterministic $O(n^{\omega})$ time algorithm that uses conditional effective resistances to decide whether each edge belongs to the tree, iteratively contracting included edges and deleting excluded ones. Building on this, Durfee, Kyng, Peebles, Rao and Sachdeva [27] leveraged “Schur complements” to efficiently compute conditional effective resistances, resulting in a faster algorithm with a runtime of $\widetilde{O}(n^{4/3}m^{1/2}+n^{2})$ . In a separate work, Durfee, Peebles, Peng and Rao [28] introduced determinant-preserving sparsification, which enables the sampling of random spanning trees in $\widetilde{O}(n^{2}\epsilon^{-2})$ time, from a distribution with a total variation distance of $\epsilon$ from the true uniform distribution.
$\blacksquare$

Random walk based approaches [16, 3, 61, 39, 49, 57, 9]: First introduced independently by Broder [16] and Aldous [3], it was shown that a random spanning tree can be sampled by performing a simple random walk on the graph until all nodes are visited, while retaining only the first incoming edge for each vertex. For unweighted graphs, this results in an $O(mn)$ algorithm. The subsequent works [61, 39, 49] focused on accelerating these walks using various techniques involving fast Laplacian solving, electrical flows and Schur complements. This line of research culminated in Schild’s work [57], which achieved an almost-linear time algorithm with a runtime of $m^{1+o(1)}$ . The current state-of-the-art algorithm employs a simple yet elegant approach based on “down-up random walks” with a near-optimal runtime $O(m\log^{2}m)$ , and its mixing time analysis is technically intricate [56, 20, 9].

1.1 Main Result

In this work, we propose a quantum algorithm for approximately sampling random spanning trees, leading to the theorem below. We let $\mathcal{W}_{G}$ denote the distribution over spanning trees of $G$ , where each tree is sampled with probability proportional to the product of its edge weights.

Theorem 1 (Quantum algorithm for sampling a random spanning tree).

There exists a quantum algorithm $\mathsf{QRST}(\mathcal{O}_{G},\varepsilon)$ that, given query access $\mathcal{O}_{G}$ to the adjacency list of a connected graph $G=(V,E,w)$ (with $\left\lvert V\right\rvert=n$ , $\left\lvert E\right\rvert=m$ , $w\in\mathbb{R}^{E}_{\geq 0}$ ), and accuracy parameter $\varepsilon$ , with high probability, outputs a spanning tree $T$ of $G$ drawn from a distribution which is $\varepsilon$ -close to $\mathcal{W}_{G}$ in total variation distance. The algorithm makes $\widetilde{O}(\sqrt{mn}\log(1/\varepsilon))$ queries to $\mathcal{O}_{G}$ , and runs in $\widetilde{O}(\sqrt{mn}\log(1/\varepsilon))$ time.

We also prove a matching lower bound, showing that the runtime of our quantum algorithm is optimal up to polylog-factors.

Theorem 2 (Quantum lower bound for sampling a random spanning tree).

Let $\varepsilon<1/2$ be a constant. For any graph $G=(V,E,w)$ with $\left\lvert V\right\rvert=n$ , $\left\lvert E\right\rvert=m$ , $w\in\mathbb{R}^{E}_{\geq 0}$ , consider the problem of sampling a random spanning tree from a distribution $\varepsilon$ -close to $\mathcal{W}_{G}$ , given adjacency-list access to $G$ . The quantum query complexity of this problem is $\Omega(\sqrt{mn})$ .

1.2 Techniques

Our algorithm is based on the “down-up random walk” approach from [9]. Their core idea (already present in earlier work [55]) is to consider a random walk over spanning trees. In each step of the random walk, they randomly remove an edge to split it into two components, and then add a new edge sampled from the edges across the two components proportional to the edge weights. Their crucial contribution is to show that this random walk has a mixing time $\widetilde{O}(n)$ , which is sublinear with respect to the number of edges $m$ . Since each step of the down-up random walk can be costly ( $\widetilde{O}(m)$ , naively), their final algorithm actually considers an “up-down random walk”, where first an edge is added and then another edge is removed. While this walk has a larger mixing time $\widetilde{O}(m)$ , each step can now be implemented in amortized time $\widetilde{O}(1)$ using link-cut trees.

1.2.1 Idea (and Barrier) for Quantum Speedups

To achieve a sublinear-time quantum algorithm, we could follow [9] and attempt to quantumly accelerate the mixing time of the up-down walk. However, apart from some special cases [2, 50, 52], no general quantum speedups for the mixing time of classical random walks are known. As a result, any algorithm with a mixing time of $\widetilde{O}(m)$ does not yield a quantum advantage.

A natural alternative is to revisit the down-up random walk, which has a sublinear mixing time of $\widetilde{O}(n)$ , and leverage quantum techniques to speed up the implementation of each step. Specifically, after removing an edge, we can sample an edge between the two resulting components in $\widetilde{O}(\sqrt{m})$ time using Grover search [33], compared to the classical $\widetilde{O}(m)$ time. Unfortunately, this still results in an overall complexity of $\widetilde{O}(\sqrt{m}n)\in\widetilde{\Omega}(m)$ , offering no speedup over classical algorithms.

1.2.2 Our Approach

To overcome the above barriers, we use an amortization idea of implementing a “large-step” down-up walk instead of a single-step approach. In a standard down-up walk, a single edge in the spanning tree is changed after each step. In contrast, the large-step down-up walk modifies several edges – approximately $\Theta(n)$ – in each step, resulting in a significantly faster mixing time of $\widetilde{O}(1)$ . These $\Theta(n)$ edges are sampled from a batch of $\widetilde{O}(n)$ edges, which we select among the $m$ edges in time $\widetilde{O}(\sqrt{mn})$ using quantum search. While the framework appears simple at first glance, implementing each step requires a careful integration of various quantum algorithms. Additionally, analyzing the mixing time relies on deep results from [10]. Below, we outline the main techniques utilized in our approach:

Domain Sparsification Under Isotropy

Domain sparsification [6, 7, 10] is a framework which aims to reduce the task of sampling from a distribution on $\binom{\left[m\right]}{k}$ with $k\ll m$ to sampling from some related distribution on $\binom{\left[t\right]}{k}$ for $t\ll m$ . For so-called “strongly Rayleigh distributions” [15], the domain size can be reduced to be nearly linear in the input size with $t=\widetilde{O}(k)$ [10]. For random spanning trees, which are a canonical example of a strongly Rayleigh distribution, this reduces the sampling problem from domain $\binom{\left[m\right]}{n}$ to $\binom{\left[t\right]}{n}$ with $t\in\widetilde{O}(n)$ . This provides an opportunity for quantum acceleration, provided that it is easier to sample this subdomain of $\widetilde{O}(n)$ edges.

A key technique enabling efficient sampling of such a subdomain is the “isotropic transformation”, which can be interpreted as a discrete analogue of the isotropic position of a continuous distribution [54, 45]. Originally developed in the context of designing algorithms for sampling from logconcave distributions, the isotropic position uses a linear map to convert a distribution into a standard form, enabling faster and more efficient sampling. In [10], Anari Liu and Vuong describe a discrete isotropic transformation for distributions over $\binom{\left[m\right]}{k}$ based on the marginals of individual elements of $\left[m\right]$ . After this isotropic transformation, domain sparsification reduces to sampling a subdomain uniformly at random from the domain.

For the particular case of sampling random spanning trees, the marginal probability of an edge is given by its effective resistance, and domain sparsification amounts to sampling edges uniformly at random in the isotropic-transformed multigraph (see Lemma 18), whose construction is based on the effective resistances of the edges in the original graph.

In our algorithm, rather than explicitly computing this isotropic transformation (whose description size is $\widetilde{O}(m)$ which we cannot tolerate), we utilize a quantum data structure, $\mathsf{QResistance}$ , which provides quantum query access to effective resistances, to “implicitly” construct and maintain the isotropic-transformed multigraph. More specifically, with $\mathsf{QResistance}$ in place, we can efficiently implement the up step of the walk, which involves sampling a subdomain of $O(n)$ edges uniformly from the implicit isotropic-transformed multigraph, as well as the down step, which requires sampling a random spanning tree from the resulting $\widetilde{O}(n)$ -edge subdomain.

Quantum Graph Algorithms and Quantum Multi-Sampling

To achieve the near-optimal quantum speedup, our algorithm incorporates a suite of quantum algorithms as subroutines. During the initialization stage, it utilizes the quantum minimum spanning tree algorithm proposed in [29] to identify a starting spanning tree, reducing the complexity from $\widetilde{O}(m)$ to $\widetilde{O}(\sqrt{mn})$ . For approximating the effective resistance, we adopt the approach in [11] that combines the quantum graph sparsification algorithm with the Spielman-Srivastava toolbox [59] to construct an efficient $\mathsf{QResistance}$ data structure in $\widetilde{O}(\sqrt{mn})$ time. This data structure provides query access to approximate effective resistances with a cost of $\widetilde{O}(1)$ per query. For the up operation, we develop a variant of quantum search, $\mathsf{QIsotropicSample}$ , for sampling multiple edges in the isotropic-transformed graph with up to a quadratic speedup. The key idea behind this algorithm is to leverage a variant of the “preparing many copies of quantum states” technique proposed in [35], utilizing the query access provided by our $\mathsf{QResistance}$ . This variant of the Hamoudi’s technique can be thought of as a sampling without replacement method, ensuring that the samples are all different. Notably, $\mathsf{QIsotropicSample}$ efficiently samples a set of $\widetilde{O}(n)$ edges in $\widetilde{O}(\sqrt{mn})$ time. Leveraging these algorithms, our approach ultimately achieves random spanning tree sampling in $\widetilde{O}(\sqrt{mn})$ time.

1.2.3 Lower Bound

The lower bound follows from a reduction of the problem of finding $n$ marked elements among $m$ elements, whose quantum query complexity is $\Theta(\sqrt{mn})$ , to the problem of sampling a uniform spanning tree in a weighted graph. The reduction encodes the search problem into the weights of a fixed graph, in such a way that a uniformly random spanning tree in that graph reveals the marked elements. The argument is similar to the $\Omega(\sqrt{mn})$ lower bound from [29] on the quantum query complexity of finding a minimum spanning tree.

1.3 Open Questions

Our work raises several interesting questions and future directions, including the following:

$\blacksquare$

The runtime of our quantum algorithm is tight, up to polylogarithmic factors, for sampling random spanning trees in weighted graphs. Can we potentially improve the runtime for unweighted graphs, for instance, to $\widetilde{O}(n)$ ? This is the case for constructing spanning trees, as was shown in the earlier work [29]. Note that our $\Omega(\sqrt{mn})$ lower bound applies only to the weighted graph case. We were unable to prove a $\omega(n)$ lower bound for the unweighted case, based on which we conjecture that there exist more efficient algorithms for the unweighted case.
$\blacksquare$

This work represents the first application of the down-up walk in quantum algorithm design. As demonstrated by a series of breakthroughs in sampling and counting problems for spin systems [4, 8, 18, 38, 5, 47, 13, 1], the down-up walk has proven highly effective in designing classical algorithms for a variety of graph problems. Notable examples include independent set sampling [4, 8], $q$ -colorings sampling [18, 38, 13], edge-list-colorings sampling [1], planar matching counting and sampling [5], and vertex-list-colorings sampling [47]. Given these successes, it would be intriguing to explore whether quantum speedups can be achieved for these problems.
$\blacksquare$

Additionally, exploring quantum speedups for determinantal point processes (DPPs) is a natural and meaningful direction. Like random spanning trees, DPPs are strongly Rayleigh distributions, enabling efficient domain sparsification [6, 7, 10]. They also play a crucial role in applications such as machine learning [42, 43, 23], optimization [21, 23, 51], and randomized linear algebra [24, 22, 25]. Developing quantum algorithms for DPPs could lead to quantum computational advantages in these areas.

2 Preliminaries

For simplicity, we use $\left[n\right]$ to represent the set $\{1,2,\ldots,n\}$ and $\left[n\right]_{0}$ to represent the set $\{0,1,\ldots,n-1\}$ . We consider an undirected weighted graph $G=(V,E,w)$ , where $V$ is the vertex set, $E$ is the edge set, and $w:E\mapsto\mathbb{R}_{\geq 0}$ represents the weight function. We use $n, m$ to denote the size of $V$ and $E$ , respectively. We use $\delta_{i}$ to denote the vector whose elements are 0 except for the $i$ -th element, which is 1.

For a distribution defined over all subsets $\mu:2^{\left[m\right]}\to\mathbb{R}_{\geq 0}$ and $S\subseteq\left[m\right]$ , let $\mu_{S}$ be the restricted distribution of $P\sim\mu$ conditioned on the event $P\subseteq S$ .

2.1 Quantum Computational Model

We assume the same quantum computational model as in for instance [29, 11]. This entails a classical control system that (i) can run quantum circuits on $O(\log n)$ qubits, (ii) can make quantum queries to the adjacency list oracle $\mathcal{O}_{G}$ , and (iii) has access to a quantum-read/classical-write RAM of $\widetilde{O}(\sqrt{mn})$ bits. The quantum query complexity measures the number of quantum queries that an algorithm makes. The quantum time complexity measures the number of elementary operations (classical and quantum gates), quantum queries, and single-bit QRAM operations (classical-write or quantum-read). If we only care about the quantum query complexity, then we can drop the QRAM assumption at the expense of a polynomial increase in the time complexity.

2.2 Markov Chains and Mixing time

Let $\mu,\nu$ be two discrete probability distributions over a finite set $\Omega$ . The total variation distance (or $\operatorname{TV}$ -distance) between $\mu$ and $\nu$ is defined as

\left\lVert\mu-\nu\right\rVert_{\operatorname{TV}}:=\frac{1}{2}\sum_{x\in% \Omega}\left\lvert\mu(x)-\nu(x)\right\rvert.

The Kullback-Leibler (KL) divergence, also known as relative entropy, between $\mu$ and $\nu$ is defined as

\mathcal{D}_{\operatorname{KL}}(\mu\parallel\nu):=\sum_{x\in\Omega}\mu(x)\log% \left(\frac{\mu(x)}{\nu(x)}\right).

A well-known result, often summarized as “relative entropy never increases”, is stated in the following theorem:

Theorem 3 (Data Processing Inequality).

For any transition probability matrix $P\in\mathbb{R}^{\Omega\times\Omega^{\prime}}$ and pair of distributions $\mu,\nu:\Omega\to\mathbb{R}_{\geq 0}$ , it holds that

\mathcal{D}_{\operatorname{KL}}(\nu P\parallel\mu P)\leq\mathcal{D}_{% \operatorname{KL}}(\nu\parallel\mu).

A Markov chain on a finite state space $\Omega$ is specified by its transition probability matrix $P\in\mathbb{R}^{\Omega\times\Omega}$ . For a comprehensive introduction to the analysis of Markov chains, we refer the reader to [46]. A distribution $\mu$ is said to be stationary with respect to $P$ if $\mu P=\mu$ . In this case, $\mu$ is also called the stationary distribution of the Markov chain. When $P$ is ergodic, the Markov chain has a unique stationary distribution $\mu$ , and for any initial probability distribution $\nu$ on $\Omega$ , $\lVert\nu P^{t}-\mu\rVert_{\operatorname{TV}}$ converges to $0$ as $t\to\infty$ . To precisely characterize how quickly an ergodic Markov chain converges, one can define the mixing time as below.

Definition 4 (Mixing time).

Let $P$ be an ergodic Markov chain on a finite state space $\Omega$ and let $\mu$ denote its stationary distribution. For any probability distribution $\nu$ on $\Omega$ and $\varepsilon\in\mathopen{(}0,1\mathclose{)}$ , we define

t_{\operatorname{mix}}(P,\nu,\varepsilon):=\min\left\{t\geq 0\mid\lVert\nu P^{% t}-\mu\rVert_{\operatorname{TV}}\leq\varepsilon\right\}.

The following well-known theorem demonstrates the relationship between the modified log-Sobolev constant and mixing times, which bounds the mixing time via modified log-Sobolev inequalities.

Theorem 5 ([14], see also corollary 8 in [20]).

Let $P$ denote the transition matrix of an ergodic, reversible Markov chain on a finite state space $\Omega$ with the stationary distribution $\mu$ . Suppose there exists some $\alpha\in\mathopen{(}0,1\mathclose{]}$ such that for any probability distribution $\nu$ on $\Omega$ , we have

\mathcal{D}_{\operatorname{KL}}(\nu P\parallel\mu P)\leq(1-\alpha)\mathcal{D}_% {\operatorname{KL}}(\nu\parallel\mu).

Then, for any $\varepsilon\in\mathopen{(}0,1\mathclose{)}$ ,

t_{\operatorname{mix}}(P,1_{x},\varepsilon)\leq\left\lceil\frac{1}{\alpha}% \cdot\left(\log\log\left(\frac{1}{\mu\left(x\right)}\right)+\log\left(\frac{1}% {2\varepsilon^{2}}\right)\right)\right\rceil,

where $1_{x}$ is the point mass distribution supported on $x$ .

2.3 Laplacian and Graph Sparsification

For an undirected weighted graph $G=(V,E,w)$ , the weighted degree of a vertex $v$ is defined as $\deg(v)=\sum_{e\in E:v\in e}w_{e}$ , where the sum is taken over all edges $e$ incident to $v$ , and $w_{e}$ denotes the weight of edge $e$ .

Definition 6 (Laplacian).

The Laplacian of a weighted graph $G=(V,E,w)$ is defined as the matrix $L_{G}\in\mathbb{R}^{V\times V}$ such that

(L_{G})_{ij}=\begin{cases}\deg(i)&\textup{if }i=j,\\ -w_{ij}&\textup{if }\{i,j\}\in E,\\ 0&\textup{otherwise}.\end{cases}

Equivalently, the Laplacian of graph $G$ is given by $L_{G}=D_{G}-A_{G}$ , with $A_{G}$ the weighted adjacency matrix $\left(A_{G}\right)_{ij}=w_{ij}$ and $D$ the diagonal weighted degree matrix $D_{G}=\operatorname{diag}\left(\deg\left(i\right):i\in V\right)$ . $L_{G}$ is a positive semidefinite matrix since the weight function $w$ is nonnegative, and $L_{G}$ induces the quadratic form

x^{\top}L_{G}x=\sum_{\left\{i,j\right\}\in E}w_{ij}\cdot(x_{i}-x_{j})^{2}

for arbitrary vector $x\in\mathbb{R}^{V}$ . Graph sparsification produces a reweighted graph with fewer edges, known as a graph spectral sparsifier. A graph spectral sparsifier of $G$ is a re-weighted subgraph that closely approximates the quadratic form of the Laplacian for any vector $x\in\mathbb{R}^{V}$ .

In the groundbreaking work [59], the authors demonstrated that graphs can be efficiently sparsified by sampling $\widetilde{O}(n)$ edges with weights roughly proportional to their effective resistance. Now, we introduce the concept of effective resistance.

Definition 7 (Effective Resistance).

Given a graph $G=(V,E,w)$ , the effective resistance $R_{ij}$ of a pair of $i,j\in V$ is defined as

R_{ij}=(\delta_{i}-\delta_{j})^{\top}L_{G}^{+}(\delta_{i}-\delta_{j})=\lVert(L% _{G}^{+})^{1/2}(\delta_{i}-\delta_{j})\rVert^{2}.

Here, $\delta_{i}$ is a vector with all elements equal to 0 except for the $i$ -th is 1, and $L^{+}_{G}$ is the Moore-Penrose inverse of the Laplacian matrix $L_{G}$ .

Definition 8 (Leverage Score and Leverage Score Overestimates).

Given a graph $G=(V,E,w)$ , the leverage score $\ell_{e}$ of an edge $e\in E$ is defined as the product of its weight and its effective resistance:

\ell_{e}=w_{e}R_{ij},\quad\text{for }e=\{i,j\}.

An $\lambda$ -leverage score overestimates $\widetilde{\ell}$ for $G$ is a vector in $\mathbb{R}^{E}_{\geq 0}$ satisfying $\lVert\widetilde{\ell}\rVert_{1}\leq\lambda$ , and $\widetilde{\ell}_{e}\geq\ell_{e}=w_{e}R_{e}$ for all $e\in E$ .

Lemma 9 (Foster’s theorem [30]).

For a weighted graph $G=(V,E,w)$ , let $\ell_{e}$ denote the leverage score of an edge $e\in E$ . Then, it holds that $\sum_{e\in E}\ell_{e}\leq n-1$ .

Proof.

For a edge $\{i,j\}$ , recall that $R_{ij}=\left(\delta_{i}-\delta_{j}\right)^{\top}L_{G}^{+}\left(\delta_{i}-% \delta_{j}\right)$ , then

\sum_{e\in E}\ell_{e}=\sum_{\{i,j\}\in E}w_{ij}R_{ij}=\sum_{\{{i,j}\}\in E}% \operatorname{Tr}\left(w_{ij}\left(\delta_{i}-\delta_{j}\right)\left(\delta_{i% }-\delta_{j}\right)^{\top}L_{G}^{+}\right)=\operatorname{Tr}\left(L_{G}L_{G}^{% +}\right)\leq n-1,

since the rank of $L_{G}$ is at most $n-1$ . $\hfill\blacktriangleleft$

2.4 Strongly Rayleigh Distributions and Random Spanning Tree

Before defining strongly Rayleigh distributions, we first introduce the stability of generating polynomials, a fundamental property in both mathematics and physics. For a probability distribution $\mu:\binom{\left[m\right]}{k}\to\mathbb{R}_{\geq 0}$ , we define the generating polynomial $f_{\mu}$ of $\mu$ as

f_{\mu}(z_{1},\ldots,z_{m})=\sum_{S\in\binom{\left[m\right]}{k}}\mu(S)\cdot% \prod_{i\in S}z_{i}.

A nonzero polynomial $f\in\mathbb{C}\left[z_{1},\ldots,z_{m}\right]$ is called stable if, $\forall i\in\left[m\right]$ , the fact that $\operatorname{Im}(z_{i})>0$ implies that $f\left(z_{1},\ldots,z_{m}\right)\neq 0$ . A stable polynomial with real coefficients is called real stable.

We say $\mu$ is a strongly Rayleigh distribution if and only if $f_{\mu}$ is a real stable polynomial. We say $\mu$ is $k$ -homogeneous if $f_{\mu}$ is $k$ -homogeneous. A useful fact is that if $\mu$ is strongly Rayleigh, then its restricted distribution $\mu_{S}$ for arbitrary $S\subseteq\left[m\right]$ is also strongly Rayleigh. For more details, we refer the reader to [15].

For any connected undirected weighted graph $G=(V,E,w)$ , let $\mathcal{T}_{G}\subseteq\binom{\left[m\right]}{n-1}$ denote the set of all spanning trees of $G$ . We provide the formal definition of random spanning tree below.

Definition 10 ( $w$ -uniform distribution on trees).

For any connected weighted undirected graph $G=(V,E,w)$ , the distribution $\mathcal{W}_{G}$ on $\mathcal{T}_{G}$ is $w$ -uniform if $\mathop{\mathbb{P}}\displaylimits_{X\sim\mathcal{W}_{G}}\left[X=T\right]% \propto\prod_{e\in T}w_{e}$ .

We refer to $\mathcal{W}_{G}$ as the $w$ -uniform distribution on $\mathcal{T}_{G}$ . A random spanning tree drawn from the distribution $\mathcal{W}_{G}$ is called $w$ -uniform.

Proposition 11 (Spanning Tree Marginals).

Given a graph $G=(V,E,w)$ , the probability that an edge $e=\{i,j\}\in E$ appears in a tree sampled $w$ -uniformly randomly from $\mathcal{T}_{G}$ is given by its leverage score $\ell_{e}=w_{e}R_{ij}$ . Namely, $\mathop{\mathbb{P}}\displaylimits_{T\sim\mathcal{W}_{G}}\left[e\in T\right]=% \ell_{e}$ .

Proposition 12 (Spanning Trees are Strongly Rayleigh [15, Theorem 3.6]).

For any connected weighted undirected graph $G=(V,E,w)$ , the $w$ -uniform distribution $\mathcal{W}_{G}$ is $(n-1)$ -homogenous strongly Rayleigh.

Theorem 13 (Random Tree Sampling [9, Theorem 2]).

There is an algorithm $\mathsf{RST}(G,\varepsilon)$ that, given a connected weighted graph $G=(V,E,w)$ and $\varepsilon>0$ , outputs a random spanning tree in $O(m\log m\log(m/\varepsilon))$ time. The distribution of output is guaranteed to be $\varepsilon$ -close to $\mathcal{W}_{G}$ in total variation distance.

2.5 Down-up and Up-down Walks

For a distribution $\mu$ on $\binom{\left[m\right]}{k}$ , we define the complement distribution $\overline{\mu}$ on $\binom{\left[m\right]}{m-k}$ by setting $\overline{\mu}(S)\stackrel{{\scriptstyle\smash{\text{\tiny\rm def}}}}{{=}}\mu(% \left[m\right]\smallsetminus S)$ for every $S\in\binom{\left[m\right]}{m-k}$ .

Definition 14 (Down operator).

For $\ell\leq k$ define the row-stochastic matrix $D_{k\to\ell}\in\mathbb{R}_{\geq 0}^{\binom{\left[m\right]}{k}\times\binom{% \left[m\right]}{\ell}}$ by

D_{k\to\ell}(S,T)=\begin{cases}0&\text{ if }T\nsubseteq S,\\ \frac{1}{\binom{k}{\ell}}&\text{ otherwise. }\end{cases}

For a distribution $\mu$ on sets of size of $k$ , $\mu D_{k\to\ell}$ will be a distribution on sets of size of $\ell$ . In particular, $\mu D_{k\to 1}$ will be the marginal distribution of $\mu$ : $\mathop{\mathbb{P}}\displaylimits_{S\sim\mu}(i\in S)/k$ , $i\in\left[m\right]$ .

Definition 15 (Up operator).

For $\ell\leq k$ define the row-stochastic matrix $U_{\ell\to k}\in\mathbb{R}_{\geq 0}^{\binom{\left[m\right]}{\ell}\times\binom{% \left[m\right]}{k}}$ by

U_{\ell\to k}(T,S)=\begin{cases}0&\text{ if }T\nsubseteq S,\\ \frac{\mu(S)}{\sum_{S^{\prime}:T\subseteq S^{\prime}}\mu(S^{\prime})}&\text{ % otherwise. }\end{cases}

We consider the following Markov chain $M_{\mu}^{t}$ defined for any positive integer $t\geq k+1$ , with the state space $\operatorname{supp}(\mu)$ . Starting from $S_{0}\in\operatorname{supp}(\mu)$ , one step of the chain $M_{\mu}^{t}$ is:

1.

Sample $T\in\binom{\left[m\right]\smallsetminus S_{0}}{t-k}$ uniformly randomly.
2.

Sample $S_{1}\sim\mu_{S_{0}\cup T}$ and update $S_{0}$ to be $S_{1}$ .

In [7, 10], it was demonstrated that the above constructed Markov chain can be used for sampling, as it possesses several desirable properties.

Proposition 16 (Proposition 25 in [7], see also Proposition 15 and 16 in [10]).

The complement of $S_{1}$ is distributed according to $\overline{\mu}_{0}D_{(m-k)\to(m-t)}U_{(m-t)\to(m-k)}$ if we start with $S_{0}\sim\mu_{0}$ . Moreover, for any distribution $\mu:\binom{\left[m\right]}{k}\rightarrow\mathbb{R}_{\geq 0}$ that is strongly Rayleigh, the chain $M_{\mu}^{t}$ for $t\geq k+1$ is irreducible, aperiodic and has stationary distribution $\mu$ .

3 Main Algorithm

Our main quantum algorithm implements a “large-step” up-down walk over the spanning trees of $G$ . Starting from a spanning tree $T$ , the up-step samples $k=2n$ edges $S$ uniformly at random from $E\setminus T$ , and then the down-step samples a uniform spanning tree from the subgraph on $T\cup S$ . We can show that, if the graph is nearly-isotropic, meaning that its edges have approximately uniform leverage scores, this walk achieves a mixing time of $\widetilde{O}(1)$ (see Proposition 20).

In practice, most input graphs are not naturally isotropic. Isotropy here refers to a balanced structure where every edge contributes roughly equally to the connectivity of the graph. This balanced contribution is captured by the concept of leverage scores, which, in our setting, are given by the product of the effective resistances of the edges and their corresponding weights. The effective resistance of an edge serves as a measure of its “importance” in maintaining connectivity: edges with high effective resistance (or high leverage scores) have an outsized influence on the spanning tree distribution. If these values vary significantly across edges, the uniform sampling in the up-step may become biased, adversely affecting the mixing time of the chain. To address this, we introduce a preprocessing step that “isotropizes” $G$ by approximately normalizing the effective resistances. Specifically, we construct a quantum data structure $\mathsf{QResistance}$ that enables efficient quantum queries to constant-factor approximations of the effective resistances of the edges in $G$ . This builds upon the quantum graph sparsification algorithm from [11], which efficiently estimates effective resistances. This preprocessing step, which we detail in Proposition 25, takes $\widetilde{O}(\sqrt{mn})$ time. Once initialized, it allows us to simulate quantum query access to an isotropic-transformed version of $G$ , denoted as $G^{\prime}$ . With quantum query access to $G^{\prime}$ , we can then implement the up-step efficiently by uniformly sampling $k$ edges, thereby preserving the desired rapid mixing properties of the Markov chain.

As initial state of the random walk, the algorithm obtains a maximum weight-product spanning tree $T$ by running the quantum algorithm $\mathsf{QMaxProductTree}$ , a slightly modified version of the algorithm from [29] (see Theorem 27 for details). We label the tree with all its edges having $1$ as a label, i.e., $e\to(e,1)$ (the label is used for identification in the isotropic-transformed graph) and store it in QRAM. Subsequently, the algorithm executes $\widetilde{O}(1)$ rounds of the up-down walk. To implement the up-step, we develop a quantum algorithm $\mathsf{QIsotropicSample}$ for uniformly sampling $k$ edges $S$ in the isotropic-transformed graph. The key idea is to combine a routine for “preparing many copies of quantum states” with the leverage score oracle access given by our $\mathsf{QResistance}$ algorithm. We detail this algorithm in Theorem 24. Notably, the algorithm $\mathsf{QIsotropicSample}$ returns a sparsified domain of $k=2n$ edges in $\widetilde{O}(\sqrt{mn})$ time.

Using oracles to $G$ and $\mathcal{R}$ , we then build the subgraph with edges $T\cup S$ using the $\mathsf{SubgraphConstruct}$ procedure. This subgraph has $O(n)$ edges, and so we can apply the classical spanning tree sampling algorithm $\mathsf{RST}$ (Theorem 13) to obtain a random spanning tree in the subgraph in $\widetilde{O}(n)$ time. This effectively implements the down-operator.

We present our algorithm in Algorithm 1.

Algorithm 1 Quantum Algorithm for Random Spanning Tree Sampling,

\mathsf{QRST}(\mathcal{O}_{G},\varepsilon)

.

More details of the subroutines employed in the algorithm are given below:

$\blacksquare$

The procedure $\mathsf{Label}(T_{0})$ means that we add a specific label $1$ to all the edges of $T_{0}$ .
$\blacksquare$

The procedure $\mathsf{QStoreTree}(T)$ stores the tree $T$ into a QRAM allowing for coherent quantum queries, given its classical description as the input.
$\blacksquare$

The procedure $\mathsf{SubgraphConstruct}(\mathcal{O}_{G},\mathcal{R},T_{t-1}^{\prime},S_{t}^% {\prime})$ constructs the subgraph after the up-step. More precisely, given query access $\mathcal{O}_{G}$ to $G=(V,E,w)$ , query access $\mathcal{R}$ to approximate resistance $\widetilde{R}$ , a classical description of a tree $T_{t-1}^{\prime}$ in $G$ , and a set $S_{t}^{\prime}$ of labeled edges, we define the multigraph $G^{\prime}=(V,E^{\prime},w^{\prime})$ , where $E^{\prime}=\left\{(e,j)\mid e\in E,j\in\left[q_{e}\right]\right\}$ with $q_{e}=\left\lceil\frac{mw_{e}\widetilde{R}_{e}}{n}\right\rceil$ and $w^{\prime}_{(e,j)}=w_{e}/q_{e}$ . We treat $T_{t-1}^{\prime}$ and $S_{t}^{\prime}$ as subsets of edges in $G^{\prime}$ . The procedure $\mathsf{SubgraphConstruct}$ just outputs a classical description of the graph $H_{t}^{\prime}=(V,E_{t}^{\prime},w_{t}^{\prime})$ , where $E_{t}^{\prime}=T_{t-1}^{\prime}\bigcup S_{t}^{\prime}$ , and $w_{t}^{\prime}(f)=w^{\prime}(f)$ for $f\in E_{t-1}^{\prime}$ .

3.1 Isotropic Transformation

Inspired by [6, 7, 10], we consider a process that transforms a graph into a multigraph, ensuring that the resulting random spanning tree distribution is nearly-isotropic.

Definition 17 (Isotropic Transformation of a Graph).

Consider a connected weighted graph $G=(V,E,w)$ , with $\lambda$ -leverage score overestimates $\widetilde{\ell}\in\mathbb{R}^{E}_{\geq 0}$ for $G$ . The isotropic transformed multigraph $G^{\prime}$ of $G$ (with respect to $\widetilde{\ell}$ ) is defined as $G^{\prime}=(V,E^{\prime},w^{\prime})$ : Here $E^{\prime}=\left\{(e,j)\mid e\in E,j\in\left[q_{e}\right]\right\}$ , where $(e,j)$ connects the same vertices as $e$ , and $q_{e}=\left\lceil\frac{m\widetilde{\ell}_{e}}{\lambda}\right\rceil$ ; $w^{\prime}_{(e,j)}=w_{e}/q_{e}$ for all $e\in E$ and $j\in\left[q_{e}\right]$ .

Lemma 18 (Isotropic Bound).

For a graph $G=(V,E,w)$ with $\left\lvert V\right\rvert=n$ and $\left\lvert E\right\rvert=m$ , let $\widetilde{\ell}\in\mathbb{R}^{E}_{\geq 0}$ be its $\lambda$ -leverage score overestimates. Let $G^{\prime}=(V,E^{\prime},w^{\prime})$ denotes the isotropic-transformed graph of $G$ with respect to $\widetilde{\ell}$ . Then, it holds that $\left\lvert E^{\prime}\right\rvert\leq 2\left\lvert E\right\rvert$ . Furthermore, for all $(e,j)\in E^{\prime}$ , we have

\mathop{\mathbb{P}}\displaylimits_{S\sim\mathcal{W}_{G^{\prime}}}\left[(e,j)% \in S\right]\leq\frac{\lambda}{m}.

Proof.

One has

\left\lvert E^{\prime}\right\rvert=\sum_{e\in E}q_{e}\leq\sum_{e\in E}\left(1+% \frac{m\widetilde{\ell}_{e}}{\lambda}\right)\leq m+\frac{m\lVert\widetilde{% \ell}\rVert_{1}}{\lambda}\leq 2m.

For any $e=\{a,b\}\in E$ and $j\in\left[q_{e}\right]$ , the marginal

\mathop{\mathbb{P}}\displaylimits_{S\sim\mathcal{W}_{G^{\prime}}}\left[(e,j)% \in S\right]=w^{\prime}_{\left(e,j\right)}R^{\prime}_{ab}=w^{\prime}_{\left(e,% j\right)}R_{ab}=\frac{w_{e}R_{ab}}{q_{e}}\leq\frac{\lambda}{m},

where the first equality follows from Proposition 11, and the second equality follows from the fact that $R^{\prime}_{ab}=R_{ab}$ . $\hfill\blacktriangleleft$

The following theorem demonstrates that the down operator satisfies a significantly stronger entropy contraction inequality when applied to strongly Rayleigh distributions with nearly uniform marginals.

Theorem 19 ([10, Theorem 28]).

Let $\mu:\binom{\left[m\right]}{k}\to\mathbb{R}_{\geq 0}$ be a strongly Rayleigh distribution with marginals $p\in\mathbb{R}^{m}$ defined by $p_{i}\stackrel{{\scriptstyle\smash{\text{\tiny\rm def}}}}{{=}}\mathop{\mathbb{% P}}\displaylimits_{S\sim\mu}\left[i\in S\right]$ . Suppose $\mu$ satisfies

p_{\max}\stackrel{{\scriptstyle\smash{\text{\tiny\rm def}}}}{{=}}\max\left\{p_% {i}:i\in\left[m\right]\right\}\leq 1/500.

Then for any distribution $\overline{\nu}:\binom{\left[m\right]}{m-k}\to\mathbb{R}_{\geq 0}$ and $t\geq k+1$ , we have

\mathcal{D}_{\operatorname{KL}}(\overline{\nu}D_{(m-k)\to(m-t)}\parallel% \overline{\mu}D_{(m-k)\to(m-t)})\leq(1-\kappa)\mathcal{D}_{\operatorname{KL}}(% \overline{\nu}\parallel\overline{\mu})

with $\kappa=\Theta\left(\frac{t-k}{(mp_{\max}+t)\log^{2}m}\right)$ .

Proposition 20.

Let $G=(V,E,w)$ be a weighted graph with $\left\lvert V\right\rvert=n$ , $\left\lvert E\right\rvert=m$ , and $w\in\mathbb{R}^{E}_{\geq 0}$ . Suppose $G$ has $\lambda$ -leverage score overestimates given by $\widetilde{\ell}\in\mathbb{R}_{\geq 0}^{E}$ , and assume $m\geq 1000n$ and $\lambda\leq 2n$ . Consider the isotropic transformed multigraph $G^{\prime}=(V,E^{\prime},w^{\prime})$ of $G$ with respect to $\widetilde{\ell}$ , as defined in Definition 17. Let $t\geq n$ be an integer, $m^{\prime}=\left\lvert E^{\prime}\right\rvert$ , and define the transition matrix $P=D_{(m^{\prime}-n+1)\to(m^{\prime}-t)}U_{(m^{\prime}-t)\to(m^{\prime}-n+1)}$ . Then, the mixing time satisfies

t_{\operatorname{mix}}(P,T_{\max}^{\prime},\varepsilon)=O(\log^{3}(n)\log(1/% \varepsilon)).

(1)

Here, $T_{\max}^{\prime}=\{(e,1)\mid e\in T_{\max}\}\subseteq E^{\prime}$ , where $T_{\max}$ is the maximum weight-product spanning tree of $G$ .

Proof.

For the isotropic-transformed graph $G^{\prime}$ , by Lemma 18, we have $m^{\prime}\leq 2m$ , and

\mathop{\mathbb{P}}\displaylimits_{S\sim\mathcal{W}_{G^{\prime}}}\left[(e,j)% \in S\right]\leq\frac{\lambda}{m}\leq\frac{2n}{m}\leq\frac{1}{500}.

Let $\mathcal{T}_{G^{\prime}}$ denote the set of all spanning trees of $G^{\prime}$ , and let $\mu^{\prime}:\binom{\left[m^{\prime}\right]}{n-1}\to\mathbb{R}_{\geq 0}$ be the $w^{\prime}$ -uniform distribution on $\mathcal{T}_{G^{\prime}}$ . Applying Theorem 19 with $t=2n$ and $k=n-1$ , we obtain that, for any distribution $\overline{\nu^{\prime}}:\binom{\left[m^{\prime}\right]}{m^{\prime}-k}\to% \mathbb{R}_{\geq 0}$ ,

\mathcal{D}_{\operatorname{KL}}(\overline{\nu^{\prime}}D_{(m^{\prime}-n+1)\to(% m^{\prime}-t)}\parallel\overline{\mu^{\prime}}D_{(m^{\prime}-n+1)\to(m^{\prime% }-t)})\leq(1-\kappa)\mathcal{D}_{\operatorname{KL}}(\overline{\nu^{\prime}}% \parallel\overline{\mu^{\prime}}),

where $\kappa^{-1}=O(\log^{2}m^{\prime})=O(\log^{2}n)$ . Thus, by the data processing inequality (Theorem 3), we have

\mathcal{D}_{\operatorname{KL}}(\overline{\nu^{\prime}}P\parallel\overline{\mu% ^{\prime}}P)\leq(1-\kappa)\mathcal{D}_{\operatorname{KL}}(\overline{\nu^{% \prime}}\parallel\overline{\mu^{\prime}}).

Combining the above result with the modified log-Sobolev inequality (Theorem 5), we conclude that

t_{\operatorname{mix}}(P,T^{\prime}_{\max},\varepsilon)\leq\left\lceil\frac{1}% {\kappa}\cdot\left(\log\log\left(\frac{1}{\mu^{\prime}(T^{\prime}_{\max})}% \right)+\log\left(\frac{1}{2\varepsilon^{2}}\right)\right)\right\rceil

(2)

Now, observe that by the pigeonhole principle we have $\mu(T_{\max})\geq 1/\binom{m}{n-1}=\Omega(1/m^{n})$ . Consequently, $\mu^{\prime}(T^{\prime}_{\max})\geq\mu(T_{\max})/(m^{\prime})^{n-1}=\Omega(1/(% 2m)^{n})$ . Thus, the claim follows as desired. $\hfill\blacktriangleleft$

As a side remark, we note that by applying Proposition 16, we can prove a bound of the mixing time for the complement (up-down walk) in a similar way.

3.2 QIsotropicSample Routine

In this subsection, we provide further details about the $\mathsf{QIsotropicSample}$ routine, which is designed for implementing the up-step. The goal of $\mathsf{QIsotropicSample}$ is to sample a set of $k$ distinct edges from the isotropic-transformed multigraph uniformly at random. Throughout the discussion, we refer to this type of task as uniformly random $k$ -subset sampling (of a set $[m]$ ), which means sampling a uniformly random $k$ -size subset of the set $[m]$ .

A crucial distinction between uniformly sampling a $k$ -size subset of the set $[m]$ and uniformly and independently sampling $k$ times from $[m]$ lies in the sampling method. The former requires sampling without replacement, while the latter involves sampling with replacement. Notably, the latter can be addressed directly using the “preparing many copies of a quantum state” algorithm (see Theorem 26 for more details). Building on this, we propose a reduction from sampling with replacement to sampling without replacement in the following, leading to an efficient quantum implementation for uniformly random $k$ -subset sampling (Theorem 23) and the $\mathsf{QIsotropicSample}$ routine (Theorem 24).

We begin with the following combinatorial proposition, which shows that we can first perform the sampling with replacement, and then discard any repeated elements to accomplish uniformly random $k$ -subset sampling.

Proposition 21.

Let $m\in\mathbb{N}$ . Suppose $j_{1},j_{2},\dots,j_{k}\in[m]$ are integers which are uniformly and independently sampled from $[m]$ . Then, conditioning on the distinctness of these integers, the distribution of $\{j_{1},j_{2},\dots,j_{k}\}$ is the same as the distribution of a uniformly random $k$ -subset of $[m]$ .

Proof.

Consider any fixed set $S=\{s_{1},s_{2},\dots,s_{k}\}$ . For the uniformly random $k$ -subset sampling, the probability that $S$ occurs is exactly $\frac{1}{\binom{m}{k}}$ .

For $j_{1},\dots,j_{k}$ which are uniformly and independently sampled from $[m]$ , the probability that they form a permutation of $\{s_{1},\dots,s_{k}\}$ is $k!/m^{k}$ . The probability that they are pairwise distinct is $m!/(m^{k}(m-k)!)$ . Therefore, conditioning on the pairwise distinctness, the probability that $\{j_{1},j_{2},\dots,j_{k}\}=S$ is just

\frac{k!/m^{k}}{m!/\left((m-k)!m^{k}\right)}=\frac{1}{\binom{m}{k}}.\

$\hfill\blacktriangleleft$

We then consider how many samples are sufficient for $k$ distinct results, which is formalized in the following modified balls-into-bins lemma.

Lemma 22.

Let $X$ be a uniformly random variable taking values in $[m]$ . For $k\in[m]$ , let $R$ be the set of different results from sampling $X$ for $\widetilde{\Theta}\lparen k\rparen$ times. Then, with high probability, we have $\lvert R\rvert\geq k$ .

Proof.

Let $Y_{i}$ denote the number of samples needed for $\lvert R\rvert=i-1$ to become $\lvert R\rvert=i$ . Let $Y=\sum_{i=1}^{k}Y_{i}$ . When $\lvert R\rvert=i-1$ , the probability that a sample falls in $[m]-R$ is $p_{i}=\left\lparen m-i+1\right\rparen/m$ . By definition, $Y_{i}$ obeys the geometric distribution, meaning that

\Pr\left[Y_{i}=k\right]={(1-p_{i})}^{k-1}p_{i}.

Therefore, $\mathbf{E}[Y_{i}]=1/p_{i}=m/\lparen m-i+1\rparen$ . By the linearity of expectations, we have

\mathbf{E}\left[Y\right]=\sum_{i=1}^{k}\mathbf{E}\left[Y_{i}\right]=\sum_{i=1}% ^{k}\frac{m}{\left\lparen m-i+1\right\rparen}\leq\sum_{i=1}^{k}\frac{k}{\left% \lparen k-i+1\right\rparen}\leq k\log(k).

Thus, by Markov’s inequality, with probability at least $2/3$ , $Y\leq 3k\log(k)$ , and the claim follows by amplifying the successful probability using Hoeffding’s inequality. $\hfill\blacktriangleleft$

By combining the above propositions and Theorem 26, we obtain a quantum algorithm for uniformly random $k$ -subset sampling from a set, which is described in the following corollary.

Theorem 23 (Quantum uniform random $k$ -subset sampling).

There exists a quantum algorithm $\mathsf{MultiSample}(\mathcal{O}_{w},k)$ that, given query access $O_{w}$ to a vector $w\in\mathbb{N}^{n}$ (where $\lVert w\rVert_{1}=O(\textup{poly}(n))$ ), and $k\in[n]$ , with high probability, returns a uniformly random $k$ -size subset $S$ of $S_{w}=\{(j,\ell)|j\in[n],\ell\in[w_{j}]\}$ . The algorithm uses $\widetilde{O}(\sqrt{nk})$ queries to $\mathcal{O}_{w}$ and runs in $\widetilde{O}(\sqrt{nk})$ time.

Proof.

In the following, we denote $k^{\prime}=ck\log k$ where $c$ is a sufficiently large constant.

From Theorem 26, we know with high probability, the algorithm $\mathsf{MultiPrepare}(\mathcal{O}_{w},k^{\prime})$ will return $k^{\prime}$ copies of the state

\lvert\mspace{0.5mu}w\mspace{0.5mu}\rangle=\frac{1}{\sqrt{W}}\sum_{j=1}^{n}% \sqrt{w_{j}}\lvert\mspace{0.5mu}j\mspace{0.5mu}\rangle,

where $W=\sum_{j=1}^{n}w_{j}$ , using $\widetilde{O}(\sqrt{nk})$ queries to $\mathcal{O}_{w}$ and in $\widetilde{O}(\sqrt{nk})$ time. We then measure the $k^{\prime}$ states on the computational basis, obtaining $k^{\prime}$ samples $j_{1},j_{2},\dots j_{k^{\prime}}$ .

Then, for each sample $j_{i}$ , we query the oracle $\mathcal{O}_{w}$ with the state $\lvert\mspace{0.5mu}j_{i}\mspace{0.5mu}\rangle\lvert\mspace{0.5mu}0\mspace{0.5% mu}\rangle$ , and measure the state $\mathcal{O}_{w}\lvert\mspace{0.5mu}j_{i}\mspace{0.5mu}\rangle\lvert\mspace{0.5% mu}0\mspace{0.5mu}\rangle$ in the computational basis to get the value of $w_{j_{i}}$ . We then uniformly sample a integer $\ell_{i}\in[w_{j_{i}}]$ , producing a uniformly random sample $(j_{i},\ell_{i})$ from $S_{w}$ . For each sample $j_{i}$ , these operations take $\widetilde{O}(1)$ time. After the above procedure, we get a sequence $(j_{1},\ell_{1}),(j_{2},\ell_{2}),\ldots,(j_{k^{\prime}},\ell_{k^{\prime}})$ .

We then output the first $k$ distinct elements of the above sequence (if there are no such $k$ elements, the algorithm simply outputs fail; by Lemma 22, the probability of this situation occurring is small.). By Proposition 21, these elements constitute a set of size $k$ which is uniformly randomly drawn from $S_{w}$ . It is clear that the above algorithm uses $\widetilde{O}(\sqrt{nk})$ queries to $\mathcal{O}_{w}$ in total and runs in $\widetilde{O}(\sqrt{nk})$ time. $\hfill\blacktriangleleft$

As a direct result of Theorem 23, given adjacency list access to a graph and query access to its approximate resistance, we can sample $k$ different edges in the isotropic-transformed graph in $\widetilde{O}(\sqrt{mk})$ time, yielding an efficient quantum implementation of the up-step.

Theorem 24 (Quantum Multi-Sampling in the Isotropic-Transformed Graph).

There exists a quantum algorithm $\mathsf{QIsotropicSample}(\mathcal{O}_{G},\mathcal{T},\mathcal{R},k)$ , that, given query access $\mathcal{O}_{G}$ to a graph $G=(V,E,W)$ (where $\left\lvert V\right\rvert=n$ and $\left\lvert E\right\rvert=m$ ), access $\mathcal{T}$ to a labeled tree $T^{\prime}$ of the multigraph $G^{\prime}=(V,E^{\prime},w^{\prime})$ , access $\mathcal{R}$ to an instance of $\mathsf{QResistance}$ that allows quantum query to the approximate effective resistance $\widetilde{R}_{e}$ for edge $e$ , and integer $k\leq m$ , with high probability, outputs a uniformly random $k$ -size subset $S$ of $E^{\prime}\setminus T^{\prime}$ , where $E^{\prime}=\left\{(e,j)\mid e\in E,j\in\left[q_{e}\right]\right\}$ , with $q_{e}=\left\lceil\frac{mw_{e}\widetilde{R}_{e}}{n}\right\rceil$ . The algorithm uses $\widetilde{O}(\sqrt{mk})$ queries to $\mathcal{O}_{G}$ and $\mathcal{R}$ , and runs in $\widetilde{O}(\sqrt{mk})$ time.

Proof.

By definition, we have

\mathcal{O}_{G}\lvert\mspace{0.5mu}e\mspace{0.5mu}\rangle\lvert\mspace{0.5mu}0% \mspace{0.5mu}\rangle=\lvert\mspace{0.5mu}e\mspace{0.5mu}\rangle\lvert\mspace{% 0.5mu}w_{e}\mspace{0.5mu}\rangle,\text{ and }\mathcal{R}\lvert\mspace{0.5mu}e% \mspace{0.5mu}\rangle\lvert\mspace{0.5mu}0\mspace{0.5mu}\rangle=\lvert\mspace{% 0.5mu}e\mspace{0.5mu}\rangle\lvert\mspace{0.5mu}\widetilde{R}_{e}\mspace{0.5mu% }\rangle.

Thus, together with access $\mathcal{T}$ to a labeled tree $T^{\prime}$ , we could implement a unitary $U_{q}$ satisfying

U_{q}\lvert\mspace{0.5mu}e\mspace{0.5mu}\rangle\lvert\mspace{0.5mu}0\mspace{0.% 5mu}\rangle=\lvert\mspace{0.5mu}e\mspace{0.5mu}\rangle\lvert\mspace{0.5mu}q_{e% }\mspace{0.5mu}\rangle

with $q_{e}=\left\lceil\frac{mw_{e}\widetilde{R}_{e}}{n}\right\rceil$ if $e\in E^{\prime}\setminus E_{T}^{\prime}$ , and $q_{e}=0$ if $e\in E_{T}^{\prime}$ , using $\widetilde{O}(1)$ queries and in $\widetilde{O}(1)$ time. This is because we can coherently evaluate $q_{e}$ given $\mathcal{O}_{G}$ , $\mathcal{R}$ and $\mathcal{T}$ .

Then, using Theorem 23, with high probability, the algorithm $\mathsf{MultiSample}(U_{q},k)$ will return a set $S$ of size $k$ which is uniformly drawn from $E^{\prime}=\left\{(e,j)\mid e\in E,j\in\left[q_{e}\right]\right\}$ , using $\widetilde{O}(\sqrt{mk})$ queries to $\mathcal{O}_{G}$ , and in $\widetilde{O}(\sqrt{mk})$ time. $\hfill\blacktriangleleft$

3.3 Proof of Main Theorem

We can now prove our main theorem.

Proof.

Without loss of generality, we assume $n/m=o(1)$ . At the initial step, the algorithm executes the subroutine $\mathsf{QResistance}$ to obtain query access to $\frac{1}{10}$ -overestimates effective resistances of $G$ in $\widetilde{O}(\sqrt{mn})$ time (by Proposition 25). It then applies $\mathsf{QMaxProductTree}$ (see Theorem 27) to find a spanning tree $T_{0}$ as the start in $\widetilde{O}(\sqrt{mn})$ time. Each edge $e\in T_{0}$ is then assigned a label $e^{(1)}$ , and the labeled tree is stored in $\widetilde{O}(n)$ time in the procedure $\mathsf{Label}$ and $\mathsf{QStoreTree}$ .

Subsequently, in each iteration $t\in\left[M\right]$ , the algorithm first uses the sampling subroutine $\mathsf{QIsotropicSample}$ to sample a uniformly random set $S^{\prime}_{t}$ of size $k$ from $E^{\prime}\setminus T^{\prime}_{t-1}$ in $\widetilde{O}(\sqrt{mk})$ time, where $k=\Theta(n)$ . Next, using Theorem 13, it samples a labeled random spanning tree in the subgraph $H^{\prime}_{t}$ in $\widetilde{O}(n)$ time, since the edge-set of subgraph $T^{\prime}_{t-1}\bigcup S^{\prime}_{t}$ has size at most $n-1+k=O(n)$ . Overall, the algorithm’s time complexity is $\widetilde{O}(\sqrt{mn})$ . It remains to prove the correctness of algorithm.

We first observe that $\widetilde{R}_{e}$ is a $\frac{1}{10}$ -overestimate of $R_{e}$ , i.e., $R_{e}\leq\widetilde{R}_{e}\leq\frac{11}{10}R_{e}$ for all $e\in E$ . Thus, $\widetilde{\ell}_{e}=w_{e}\widetilde{R}_{e}$ provides an $\frac{11}{10}n$ -leverage score overestimates, as shown below:

\sum_{e\in E}w_{e}\widetilde{R}_{e}\leq\sum_{e\in E}\frac{11}{10}w_{e}R_{e}% \leq\frac{11}{10}n,

where the final inequality follows from Foster’s theorem (Lemma 9).

If the sampling error for the random spanning tree in each iteration (line 8 of Algorithm 1) is zero, then each iteration can be viewed as one step of the chain $M_{\mu^{\prime}}^{k}$ , where $\mu^{\prime}:\binom{\left[m^{\prime}\right]}{k}\to\mathbb{R}_{\geq 0}$ corresponds exactly to the random spanning tree distribution $\mathcal{W}_{G^{\prime}}$ . Here, $m^{\prime}$ represents the number of edges of the isotropic multigraph $G^{\prime}$ satisfying $m^{\prime}\leq 2m$ . By Proposition 20, the (ideal) up-down walk has mixing time $O(\log^{3}(n)\log(1/\varepsilon))$ (Equation 1). We can hence pick $M\in O(\log^{3}(n)\log(1/\varepsilon))$ so as to ensure that the (ideal) up-down walk returns a tree $T^{\prime}_{M}$ that is distributed $\varepsilon/2$ -close to $\mathcal{W}_{G^{\prime}}$ . Since $G^{\prime}$ is obtained by equally dividing the weight of each edge in $G$ among the multiedges, mapping the multigraph $G^{\prime}$ back to $G$ ensures that distribution of the unlabeled tree $T_{M}$ remains $\varepsilon/2$ -close to $\mathcal{W}_{G}$ .

Taking into account the sampling error, note that we chose the error of $\mathsf{RST}(H^{\prime}_{t},\varepsilon/(2M))$ to be $\varepsilon/(2M)$ , ensuring that in each iteration, the TV-distance between the actual and ideal case is at most $\varepsilon/(2M)$ . After $M$ iterations, the cumulative TV-distance is bounded by $\varepsilon/2$ . Since the ideal case returns $T_{M}$ that is $\frac{\varepsilon}{2}$ -close to $\mathcal{W}_{G}$ , actual distribution of $T_{M}$ will be $\varepsilon$ -close to $\mathcal{W}_{G}$ . $\hfill\blacktriangleleft$

4 Lower Bound

Here we prove our lower bound, showing that the algorithm’s time and query complexity are optimal, up to polylogarithmic factors.

See 2

Proof.

The argument is similar to the $\Omega(\sqrt{mn})$ lower bound from [29] on the quantum query complexity of finding a minimum spanning tree, and follows from a lower bound on quantum search. Let $m=k(n+1)$ for some integer $k$ . Consider a binary matrix $M\in{\{0,1\}}^{n\times k}$ , with the promise that every row of $M$ contains a single 1-entry. The task of finding all $n$ 1-entries corresponds to solving $n$ parallel $\mathrm{OR}_{k}$ instances. By the direct product theorem on the quantum query complexity of the $\mathrm{OR}_{k}$ -function [41], the quantum query complexity of this problem is $\Theta(n\sqrt{k})=\Theta(\sqrt{mn})$ .

Now we construct a weighted graph $G_{M}$ from $M$ , in such a way that solving the aforementioned search problem on $M$ reduces to sampling a random spanning tree from $G_{M}$ . The vertices of $G_{M}$ are $\{s,\ell_{1},\dots,\ell_{k},r_{1},\dots,r_{n}\}$ . Its edges are all $(s,\ell_{i})$ with edge weight 1, and all $(\ell_{i},r_{j})$ with edge weight $M_{ij}$ . Notably, there are $n+k+1$ vertices and $n+k$ weight-1 edges. The union of these edges forms the unique spanning tree $T$ with nonzero weight $\Pi_{e\in T}w_{e}=1$ . As a consequence, sampling a random spanning tree in $G_{M}$ always returns $T$ . Since $T$ identifies all weight-1 edges in $G_{M}$ (and hence all 1-entries in $M$ ), the quantum query complexity is $\Omega(\sqrt{mn})$ ¹¹1A more refined argument shows that the lower bound even holds when all the edge weights are nonzero. The argument works by replacing $w_{ij}\in\{0,1\}$ by $w_{ij}\in\{1/n^{4},1\}$ , and noting that a random spanning tree still returns $T$ with constant probability.. $\hfill\blacktriangleleft$

References

[1] Dorna Abdolazimi, Kuikui Liu, and Shayan Oveis Gharan. A matrix trickle-down theorem on simplicial complexes and applications to sampling colorings. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 161–172. IEEE, 2022.
[2] Dorit Aharonov, Andris Ambainis, Julia Kempe, and Umesh Vazirani. Quantum walks on graphs. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 50–59, 2001. doi:10.1145/380752.380758.
[3] David J Aldous. The random walk construction of uniform spanning trees and uniform labelled trees. SIAM Journal on Discrete Mathematics, 3(4):450–465, 1990. doi:10.1137/0403039.
[4] Vedat Levi Alev and Lap Chi Lau. Improved analysis of higher order random walks and applications. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 1198–1211, 2020. doi:10.1145/3357713.3384317.
[5] Yeganeh Alimohammadi, Nima Anari, Kirankumar Shiragur, and Thuy-Duong Vuong. Fractionally log-concave and sector-stable polynomials: counting planar matchings and more. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 433–446, 2021. doi:10.1145/3406325.3451123.
[6] Nima Anari and Michał Dereziński. Isotropy and log-concave polynomials: Accelerated sampling and high-precision counting of matroid bases. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1331–1344. IEEE, 2020.
[7] Nima Anari, Michał Dereziński, Thuy-Duong Vuong, and Elizabeth Yang. Domain Sparsification of Discrete Distributions Using Entropic Independence. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:23, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2022.5.
[8] Nima Anari, Kuikui Liu, and Shayan Oveis Gharan. Spectral independence in high-dimensional expanders and applications to the hardcore model. SIAM Journal on Computing, 53(6):FOCS20–1–FOCS20–37, 2024. doi:10.1137/20M1367696.
[9] Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant, and Thuy-Duong Vuong. Log-concave polynomials iv: approximate exchange, tight mixing times, and near-optimal sampling of forests. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 408–420, 2021. doi:10.1145/3406325.3451091.
[10] Nima Anari, Yang P. Liu, and Thuy-Duong Vuong. Optimal sublinear sampling of spanning trees and determinantal point processes via average-case entropic independence. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 123–134, 2022. doi:10.1109/FOCS54457.2022.00019.
[11] Simon Apers and Ronald de Wolf. Quantum speedup for graph sparsification, cut approximation, and laplacian solving. SIAM Journal on Computing, 51(6):1703–1742, 2022. doi:10.1137/21M1391018.
[12] Arash Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan, and Amin Saberi. An ${O}(\log n\log\log n)$ -approximation algorithm for the asymmetric traveling salesman problem. In Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 379–389, 2010. doi:10.1137/1.9781611973075.32.
[13] Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel Štefankovič, and Eric Vigoda. On mixing of markov chains: Coupling, spectral independence, and entropy factorization. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3670–3692, 2022. doi:10.1137/1.9781611977073.145.
[14] Sergey G Bobkov and Prasad Tetali. Modified logarithmic Sobolev inequalities in discrete settings. Journal of Theoretical Probability, 19:289–336, 2006.
[15] Julius Borcea, Petter Brändén, and Thomas Liggett. Negative dependence and the geometry of polynomials. Journal of the American Mathematical Society, 22(2):521–567, 2009.
[16] Andrei Z Broder. Generating random spanning trees. In FOCS, volume 89, pages 442–447, 1989. doi:10.1109/SFCS.1989.63516.
[17] Nicolo Cesa-Bianchi, Claudio Gentile, Fabio Vitale, Giovanni Zappella, et al. Random spanning trees and the prediction of weighted graphs. Journal of Machine Learning Research, 14(1):1251–1284, 2013. doi:10.5555/2567709.2502620.
[18] Zongchen Chen, Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Rapid mixing for colorings via spectral independence. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1548–1557. SIAM, 2021.
[19] Charles J Colbourn, Wendy J Myrvold, and Eugene Neufeld. Two algorithms for unranking arborescences. Journal of Algorithms, 20(2):268–281, 1996. doi:10.1006/JAGM.1996.0014.
[20] Mary Cryan, Heng Guo, and Giorgos Mousa. Modified log-Sobolev inequalities for strongly log-concave distributions. The Annals of Probability, 49(1):506–525, 2021. doi:10.1214/20-AOP1453.
[21] Michal Derezinski, Burak Bartan, Mert Pilanci, and Michael W Mahoney. Debiasing distributed second order optimization with surrogate sketching and scaled regularization. Advances in Neural Information Processing Systems, 33:6684–6695, 2020.
[22] Michał Dereziński, Kenneth L Clarkson, Michael W Mahoney, and Manfred K Warmuth. Minimax experimental design: Bridging the gap between statistical and worst-case approaches to least squares regression. In Conference on Learning Theory, pages 1050–1069. PMLR, 2019.
[23] Michal Derezinski, Rajiv Khanna, and Michael W Mahoney. Improved guarantees and a multiple-descent curve for column subset selection and the nystrom method. Advances in Neural Information Processing Systems, 33:4953–4964, 2020.
[24] Michal Derezinski and Manfred KK Warmuth. Unbiased estimates for linear regression via volume sampling. Advances in Neural Information Processing Systems, 30, 2017.
[25] Michał Dereziński and Jiaming Yang. Solving dense linear systems faster than via preconditioning. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1118–1129, 2024.
[26] Leo L Duan, Zeyu Yuwen, George Michailidis, and Zhengwu Zhang. Low tree-rank bayesian vector autoregression models. Journal of Machine Learning Research, 24(286):1–35, 2023. URL: http://jmlr.org/papers/v24/22-0360.html.
[27] David Durfee, Rasmus Kyng, John Peebles, Anup B Rao, and Sushant Sachdeva. Sampling random spanning trees faster than matrix multiplication. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 730–742, 2017. doi:10.1145/3055399.3055499.
[28] David Durfee, John Peebles, Richard Peng, and Anup B Rao. Determinant-preserving sparsification of SDDM matrices with applications to counting and sampling spanning trees. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 926–937. IEEE, 2017. doi:10.1109/FOCS.2017.90.
[29] Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing, 35(6):1310–1328, 2006. doi:10.1137/050644719.
[30] Ronald M Foster. The average impedance of an electrical network. Contributions to Applied Mechanics (Reissner Anniversary Volume), 333, 1949.
[31] Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. A randomized rounding approach to the traveling salesman problem. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 550–559. IEEE, 2011. doi:10.1109/FOCS.2011.80.
[32] Navin Goyal, Luis Rademacher, and Santosh Vempala. Expanders via random spanning trees. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 576–585. SIAM, 2009. doi:10.1137/1.9781611973068.64.
[33] Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996. doi:10.1145/237814.237866.
[34] Alain Guenoche. Random spanning tree. Journal of Algorithms, 4(3):214–220, 1983. doi:10.1016/0196-6774(83)90022-6.
[35] Yassine Hamoudi. Preparing many copies of a quantum state in the black-box model. Physical Review A, 105:062440, June 2022. doi:10.1103/PhysRevA.105.062440.
[36] Nicholas JA Harvey and Keyulu Xu. Generating random spanning trees via fast matrix multiplication. In LATIN 2016: Theoretical Informatics: 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings 12, pages 522–535. Springer, 2016. doi:10.1007/978-3-662-49529-2_39.
[37] Mark Herbster, Stephen Pasteris, Fabio Vitale, and Massimiliano Pontil. A gang of adversarial bandits. Advances in Neural Information Processing Systems, 34:2265–2279, 2021. URL: https://proceedings.neurips.cc/paper/2021/hash/124461dcd3571e6674ec4e0e140cc298-Abstract.html.
[38] Vishesh Jain, Huy Tuan Pham, and Thuy Duong Vuong. Spectral independence, coupling with the stationary distribution, and the spectral gap of the glauber dynamics. arXiv preprint arXiv:2105.01201, 2021. arXiv:2105.01201.
[39] Jonathan A Kelner and Aleksander Madry. Faster generation of random spanning trees. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 13–21. IEEE, 2009. doi:10.1109/FOCS.2009.75.
[40] Gustav Kirchhoff. Ueber die auflösung der gleichungen, auf welche man bei der untersuchung der linearen vertheilung galvanischer ströme geführt wird. Annalen der Physik, 148(12):497–508, 1847.
[41] Hartmut Klauck, Robert Špalek, and Ronald De Wolf. Quantum and classical strong direct product theorems and optimal time-space tradeoffs. SIAM Journal on Computing, 36(5):1472–1493, 2007. doi:10.1137/05063235X.
[42] Alex Kulesza and Ben Taskar. k-dpps: Fixed-size determinantal point processes. In Proceedings of the 28th International Conference on Machine Learning (ICML-11), pages 1193–1200, 2011. URL: https://icml.cc/2011/papers/611_icmlpaper.pdf.
[43] Alex Kulesza, Ben Taskar, et al. Determinantal point processes for machine learning. Foundations and Trends® in Machine Learning, 5(2–3):123–286, 2012. doi:10.1561/2200000044.
[44] Vidyadhar G. Kulkarni. Generating random combinatorial objects. Journal of Algorithms, 11(2):185–207, 1990. doi:10.1016/0196-6774(90)90002-V.
[45] Yin Tat Lee and Santosh S Vempala. Eldan’s stochastic localization and the KLS conjecture: Isoperimetry, concentration and mixing. Annals of Mathematics, 199(3):1043–1092, 2024.
[46] David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
[47] Kuikui Liu. From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up Walk. In Mary Wootters and Laura Sanità, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), volume 207 of Leibniz International Proceedings in Informatics (LIPIcs), pages 32:1–32:21, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.APPROX/RANDOM.2021.32.
[48] Russell Lyons and Yuval Peres. Probability on trees and networks, volume 42. Cambridge University Press, 2017.
[49] Aleksander Madry, Damian Straszak, and Jakub Tarnawski. Fast generation of random spanning trees and the effective resistance metric. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 2019–2036. SIAM, 2014.
[50] Cristopher Moore and Alexander Russell. Quantum walks on the hypercube. In Randomization and Approximation Techniques in Computer Science: 6th International Workshop, RANDOM 2002 Cambridge, MA, USA, September 13–15, 2002 Proceedings 5, pages 164–178. Springer, 2002. doi:10.1007/3-540-45726-7_14.
[51] Aleksandar Nikolov, Mohit Singh, and Uthaipon Tantipongpipat. Proportional volume sampling and approximation algorithms for a-optimal design. Mathematics of Operations Research, 47(2):847–877, 2022. doi:10.1287/MOOR.2021.1129.
[52] Peter C Richter. Quantum speedup of classical mixing processes. Physical Review A—Atomic, Molecular, and Optical Physics, 76(4):042306, 2007.
[53] Robin Richter, Shankar Bhamidi, and Sach Mukherjee. Improved baselines for causal structure learning on interventional data. Statistics and Computing, 33(5):93, 2023. doi:10.1007/S11222-023-10257-9.
[54] Mark Rudelson. Random vectors in the isotropic position. Journal of Functional Analysis, 164(1):60–72, 1999.
[55] Luís MS Russo, Andreia Sofia Teixeira, and Alexandre P Francisco. Linking and cutting spanning trees. Algorithms, 11(4):53, 2018. doi:10.3390/A11040053.
[56] Luís M. S. Russo, Andreia Sofia Teixeira, and Alexandre P. Francisco. Linking and cutting spanning trees. Algorithms, 11(4), 2018. doi:10.3390/a11040053.
[57] Aaron Schild. An almost-linear time algorithm for uniform random spanning tree generation. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 214–227, 2018. doi:10.1145/3188745.3188852.
[58] James Sharpnack, Aarti Singh, and Akshay Krishnamurthy. Detecting activations over graphs using spanning tree wavelet bases. In Artificial intelligence and statistics, pages 536–544. PMLR, 2013. URL: http://proceedings.mlr.press/v31/sharpnack13a.html.
[59] Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6):1913–1926, 2011. doi:10.1137/080734029.
[60] Leonardo V Teixeira, Renato M Assunção, and Rosangela H Loschi. Bayesian space-time partitioning by sampling and pruning spanning trees. Journal of Machine Learning Research, 20(85):1–35, 2019. URL: https://jmlr.org/papers/v20/16-615.html.
[61] David Bruce Wilson. Generating random spanning trees more quickly than the cover time. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 296–303, 1996. doi:10.1145/237814.237880.

Appendix A Useful Theorems

In this part, we revisit some useful quantum algorithms.

By first applying the quantum graph sparsification algorithm, and then computing the approximate effective resistance on the sparisified graph, we can obtain a quantum speedup for approximating effective resistance overestimates. This is characterized by the following theorem.

Proposition 25 (Quantum Algorithms for the Effective Resistance Overestimates, Adapted from [11, Claim 7.9]).

Assume quantum query acces $\mathcal{O}_{G}$ to $G=(V,E,w)$ . There is a quantum data structure $\mathsf{QResistance}$ , that takes in the accuracy parameter $\varepsilon\in\mathopen{(}0,1/3\mathclose{)}$ , and supports the following operations:

$\blacksquare$

Initialization $\mathsf{QResistanceInit}(G,\varepsilon)$ : outputs an instance $\mathcal{R}$ of $\mathsf{QResistance}$ . This operation uses $\widetilde{O}(\sqrt{mn}/\varepsilon)$ queries to $\mathcal{O}_{G}$ , and runs in $\widetilde{O}(\sqrt{mn}/\varepsilon+n/\varepsilon^{4})$ time.
$\blacksquare$

Query $\mathcal{R}.\mathsf{Query}$ : outputs a unitary satisfying

$\mathcal{R}.\mathsf{Query}\lvert\mspace{0.5mu}a\mspace{0.5mu}\rangle\lvert% \mspace{0.5mu}b\mspace{0.5mu}\rangle\lvert\mspace{0.5mu}0\mspace{0.5mu}\rangle% =\lvert\mspace{0.5mu}a\mspace{0.5mu}\rangle\lvert\mspace{0.5mu}b\mspace{0.5mu}% \rangle\lvert\mspace{0.5mu}\widetilde{R}_{ab}\mspace{0.5mu}\rangle$

with $R_{ab}\leq\widetilde{R}_{ab}\leq(1+\varepsilon)R_{ab}$ for every pair of vertices $a,b\in V$ , where $R_{ab}$ is the effective resistance between vertices $a$ and $b$ in graph $G$ . The operation runs in $\widetilde{O}(1/\varepsilon^{2})$ time.

Proof.

Originally the quantum algorithm in [11, Claim 7.9] provides query access to the estimate $R_{ab}^{\prime}$ of the effective resistance satisfying $(1-\varepsilon^{\prime})R_{ab}\leq R_{ab}^{\prime}\leq(1+\varepsilon^{\prime})% R_{ab}$ . Therefore, for our purpose, it suffices to take $\varepsilon^{\prime}=\varepsilon/3$ and $\widetilde{R}_{ab}=R_{ab}^{\prime}/(1-\varepsilon^{\prime})$ in their algorithm. $\hfill\blacktriangleleft$

The following theorem allows us to obtain a quantum speedup for the task of preparing multiple copies of a state.

Theorem 26 (Preparing many copies of a quantum state, [35, Theorem 1]).

There exists a quantum algorithm $\mathsf{MultiPrepare}(\mathcal{O}_{w},k)$ that, given oracle access $\mathcal{O}_{w}$ to a vector $w\in\mathbb{R}_{\geq 0}^{n}$ (0-indexed), and $k\in[n]$ , with high probability, outputs $k$ copies of the state $\lvert\mspace{0.5mu}w\mspace{0.5mu}\rangle$ , where $\lvert\mspace{0.5mu}w\mspace{0.5mu}\rangle=\frac{1}{\sqrt{W}}\sum_{i\in\left[n% \right]_{0}}\sqrt{w_{i}}\lvert\mspace{0.5mu}i\mspace{0.5mu}\rangle$ with $W={\sum_{i\in\left[n\right]_{0}}w_{i}}$ . The algorithm uses $\widetilde{O}(\sqrt{nk})$ queries to $\mathcal{O}_{w}$ , and runs in $\widetilde{O}(\sqrt{nk})$ time.

We further recall the quantum algorithm for finding a minimum spanning tree proposed in [29].

Theorem 27 (Quantum algorithm for finding a minimum spanning tree, Theorem 4.2 in [29]).

There exists a quantum algorithm $\mathsf{QMinTree}(\mathcal{O}_{G})$ that, given query access $\mathcal{O}_{G}$ to an undirected weighted graph $G=(V,E,w)$ with $\left\lvert V\right\rvert=n$ and $\left\lvert E\right\rvert$ = m, with high probability, outputs a minimum spanning tree of $G$ . The algorithm uses $O(\sqrt{mn})$ queries to $\mathcal{O}_{G}$ and runs in $\widetilde{O}(\sqrt{mn})$ time.

In our paper, we need to find a spanning tree with maximal weight product in an undirected weighted graph. This could be done by directly applying above algorithm to the same graph with slight modifications of weight. We give more details in the following.

Corollary 28 (Quantum algorithm for finding a maximum spanning tree, Adapted from Theorem 4.2 in [29]).

There exists a quantum algorithm $\mathsf{QMaxProductTree}(\mathcal{O}_{G})$ that, given adjacency query access $\mathcal{O}_{G}$ to an undirected weighted graph $G=(V,E,w)$ with $\left\lvert V\right\rvert=n$ and $\left\lvert E\right\rvert$ = m, and weight $w$ bounded by some constant $W$ , with high probability, outputs a maximum weight-product spanning tree of $G$ . The algorithm uses $O(\sqrt{mn})$ queries to $\mathcal{O}_{G}$ and runs in $\widetilde{O}(\sqrt{mn})$ time.

Proof.

Note that a maximum weight-product spanning tree of $G=(V,E,w)$ corresponds to a minimum spanning tree of the graph $G^{\prime}=(V,E,w^{\prime})$ , with $w^{\prime}_{e}=\log(W/w_{e})$ for all $e\in E$ . Given query access to $G$ , a query access to $G^{\prime}$ can be constructed in $\widetilde{O}(1)$ time. Therefore, by applying Theorem 27, we know $\mathsf{QMinTree}(\mathcal{O}_{G^{\prime}})$ is what we need. $\hfill\blacktriangleleft$

[bib.bib1] [1] Dorna Abdolazimi, Kuikui Liu, and Shayan Oveis Gharan. A matrix trickle-down theorem on simplicial complexes and applications to sampling colorings. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 161–172. IEEE, 2022.

[bib.bib2] [2] Dorit Aharonov, Andris Ambainis, Julia Kempe, and Umesh Vazirani. Quantum walks on graphs. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 50–59, 2001. doi:10.1145/380752.380758.

[bib.bib3] [3] David J Aldous. The random walk construction of uniform spanning trees and uniform labelled trees. SIAM Journal on Discrete Mathematics, 3(4):450–465, 1990. doi:10.1137/0403039.

[bib.bib4] [4] Vedat Levi Alev and Lap Chi Lau. Improved analysis of higher order random walks and applications. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 1198–1211, 2020. doi:10.1145/3357713.3384317.

[bib.bib5] [5] Yeganeh Alimohammadi, Nima Anari, Kirankumar Shiragur, and Thuy-Duong Vuong. Fractionally log-concave and sector-stable polynomials: counting planar matchings and more. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 433–446, 2021. doi:10.1145/3406325.3451123.

[bib.bib6] [6] Nima Anari and Michał Dereziński. Isotropy and log-concave polynomials: Accelerated sampling and high-precision counting of matroid bases. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1331–1344. IEEE, 2020.

[bib.bib7] [7] Nima Anari, Michał Dereziński, Thuy-Duong Vuong, and Elizabeth Yang. Domain Sparsification of Discrete Distributions Using Entropic Independence. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:23, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2022.5.

[bib.bib8] [8] Nima Anari, Kuikui Liu, and Shayan Oveis Gharan. Spectral independence in high-dimensional expanders and applications to the hardcore model. SIAM Journal on Computing, 53(6):FOCS20–1–FOCS20–37, 2024. doi:10.1137/20M1367696.

[bib.bib9] [9] Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant, and Thuy-Duong Vuong. Log-concave polynomials iv: approximate exchange, tight mixing times, and near-optimal sampling of forests. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 408–420, 2021. doi:10.1145/3406325.3451091.

[bib.bib10] [10] Nima Anari, Yang P. Liu, and Thuy-Duong Vuong. Optimal sublinear sampling of spanning trees and determinantal point processes via average-case entropic independence. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 123–134, 2022. doi:10.1109/FOCS54457.2022.00019.

[bib.bib11] [11] Simon Apers and Ronald de Wolf. Quantum speedup for graph sparsification, cut approximation, and laplacian solving. SIAM Journal on Computing, 51(6):1703–1742, 2022. doi:10.1137/21M1391018.

[bib.bib12] [12] Arash Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan, and Amin Saberi. An ${O}(\log n\log\log n)$ -approximation algorithm for the asymmetric traveling salesman problem. In Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 379–389, 2010. doi:10.1137/1.9781611973075.32.

[bib.bib13] [13] Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel Štefankovič, and Eric Vigoda. On mixing of markov chains: Coupling, spectral independence, and entropy factorization. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3670–3692, 2022. doi:10.1137/1.9781611977073.145.

[bib.bib14] [14] Sergey G Bobkov and Prasad Tetali. Modified logarithmic Sobolev inequalities in discrete settings. Journal of Theoretical Probability, 19:289–336, 2006.

[bib.bib15] [15] Julius Borcea, Petter Brändén, and Thomas Liggett. Negative dependence and the geometry of polynomials. Journal of the American Mathematical Society, 22(2):521–567, 2009.

[bib.bib16] [16] Andrei Z Broder. Generating random spanning trees. In FOCS, volume 89, pages 442–447, 1989. doi:10.1109/SFCS.1989.63516.

[bib.bib17] [17] Nicolo Cesa-Bianchi, Claudio Gentile, Fabio Vitale, Giovanni Zappella, et al. Random spanning trees and the prediction of weighted graphs. Journal of Machine Learning Research, 14(1):1251–1284, 2013. doi:10.5555/2567709.2502620.

[bib.bib18] [18] Zongchen Chen, Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Rapid mixing for colorings via spectral independence. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1548–1557. SIAM, 2021.

[bib.bib19] [19] Charles J Colbourn, Wendy J Myrvold, and Eugene Neufeld. Two algorithms for unranking arborescences. Journal of Algorithms, 20(2):268–281, 1996. doi:10.1006/JAGM.1996.0014.

[bib.bib20] [20] Mary Cryan, Heng Guo, and Giorgos Mousa. Modified log-Sobolev inequalities for strongly log-concave distributions. The Annals of Probability, 49(1):506–525, 2021. doi:10.1214/20-AOP1453.

[bib.bib21] [21] Michal Derezinski, Burak Bartan, Mert Pilanci, and Michael W Mahoney. Debiasing distributed second order optimization with surrogate sketching and scaled regularization. Advances in Neural Information Processing Systems, 33:6684–6695, 2020.

[bib.bib22] [22] Michał Dereziński, Kenneth L Clarkson, Michael W Mahoney, and Manfred K Warmuth. Minimax experimental design: Bridging the gap between statistical and worst-case approaches to least squares regression. In Conference on Learning Theory, pages 1050–1069. PMLR, 2019.

[bib.bib23] [23] Michal Derezinski, Rajiv Khanna, and Michael W Mahoney. Improved guarantees and a multiple-descent curve for column subset selection and the nystrom method. Advances in Neural Information Processing Systems, 33:4953–4964, 2020.

[bib.bib24] [24] Michal Derezinski and Manfred KK Warmuth. Unbiased estimates for linear regression via volume sampling. Advances in Neural Information Processing Systems, 30, 2017.

[bib.bib25] [25] Michał Dereziński and Jiaming Yang. Solving dense linear systems faster than via preconditioning. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1118–1129, 2024.

[bib.bib26] [26] Leo L Duan, Zeyu Yuwen, George Michailidis, and Zhengwu Zhang. Low tree-rank bayesian vector autoregression models. Journal of Machine Learning Research, 24(286):1–35, 2023. URL: http://jmlr.org/papers/v24/22-0360.html.

[bib.bib27] [27] David Durfee, Rasmus Kyng, John Peebles, Anup B Rao, and Sushant Sachdeva. Sampling random spanning trees faster than matrix multiplication. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 730–742, 2017. doi:10.1145/3055399.3055499.

[bib.bib28] [28] David Durfee, John Peebles, Richard Peng, and Anup B Rao. Determinant-preserving sparsification of SDDM matrices with applications to counting and sampling spanning trees. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 926–937. IEEE, 2017. doi:10.1109/FOCS.2017.90.

[bib.bib29] [29] Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing, 35(6):1310–1328, 2006. doi:10.1137/050644719.

[bib.bib30] [30] Ronald M Foster. The average impedance of an electrical network. Contributions to Applied Mechanics (Reissner Anniversary Volume), 333, 1949.

[bib.bib31] [31] Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. A randomized rounding approach to the traveling salesman problem. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 550–559. IEEE, 2011. doi:10.1109/FOCS.2011.80.

[bib.bib32] [32] Navin Goyal, Luis Rademacher, and Santosh Vempala. Expanders via random spanning trees. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 576–585. SIAM, 2009. doi:10.1137/1.9781611973068.64.

[bib.bib33] [33] Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996. doi:10.1145/237814.237866.

[bib.bib34] [34] Alain Guenoche. Random spanning tree. Journal of Algorithms, 4(3):214–220, 1983. doi:10.1016/0196-6774(83)90022-6.

[bib.bib35] [35] Yassine Hamoudi. Preparing many copies of a quantum state in the black-box model. Physical Review A, 105:062440, June 2022. doi:10.1103/PhysRevA.105.062440.

[bib.bib36] [36] Nicholas JA Harvey and Keyulu Xu. Generating random spanning trees via fast matrix multiplication. In LATIN 2016: Theoretical Informatics: 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings 12, pages 522–535. Springer, 2016. doi:10.1007/978-3-662-49529-2_39.

[bib.bib37] [37] Mark Herbster, Stephen Pasteris, Fabio Vitale, and Massimiliano Pontil. A gang of adversarial bandits. Advances in Neural Information Processing Systems, 34:2265–2279, 2021. URL: https://proceedings.neurips.cc/paper/2021/hash/124461dcd3571e6674ec4e0e140cc298-Abstract.html.

[bib.bib38] [38] Vishesh Jain, Huy Tuan Pham, and Thuy Duong Vuong. Spectral independence, coupling with the stationary distribution, and the spectral gap of the glauber dynamics. arXiv preprint arXiv:2105.01201, 2021. arXiv:2105.01201.

[bib.bib39] [39] Jonathan A Kelner and Aleksander Madry. Faster generation of random spanning trees. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 13–21. IEEE, 2009. doi:10.1109/FOCS.2009.75.

[bib.bib40] [40] Gustav Kirchhoff. Ueber die auflösung der gleichungen, auf welche man bei der untersuchung der linearen vertheilung galvanischer ströme geführt wird. Annalen der Physik, 148(12):497–508, 1847.

[bib.bib41] [41] Hartmut Klauck, Robert Špalek, and Ronald De Wolf. Quantum and classical strong direct product theorems and optimal time-space tradeoffs. SIAM Journal on Computing, 36(5):1472–1493, 2007. doi:10.1137/05063235X.

[bib.bib42] [42] Alex Kulesza and Ben Taskar. k-dpps: Fixed-size determinantal point processes. In Proceedings of the 28th International Conference on Machine Learning (ICML-11), pages 1193–1200, 2011. URL: https://icml.cc/2011/papers/611_icmlpaper.pdf.

[bib.bib43] [43] Alex Kulesza, Ben Taskar, et al. Determinantal point processes for machine learning. Foundations and Trends® in Machine Learning, 5(2–3):123–286, 2012. doi:10.1561/2200000044.

[bib.bib44] [44] Vidyadhar G. Kulkarni. Generating random combinatorial objects. Journal of Algorithms, 11(2):185–207, 1990. doi:10.1016/0196-6774(90)90002-V.

[bib.bib45] [45] Yin Tat Lee and Santosh S Vempala. Eldan’s stochastic localization and the KLS conjecture: Isoperimetry, concentration and mixing. Annals of Mathematics, 199(3):1043–1092, 2024.

[bib.bib46] [46] David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.

[bib.bib47] [47] Kuikui Liu. From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up Walk. In Mary Wootters and Laura Sanità, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), volume 207 of Leibniz International Proceedings in Informatics (LIPIcs), pages 32:1–32:21, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.APPROX/RANDOM.2021.32.

[bib.bib48] [48] Russell Lyons and Yuval Peres. Probability on trees and networks, volume 42. Cambridge University Press, 2017.

[bib.bib49] [49] Aleksander Madry, Damian Straszak, and Jakub Tarnawski. Fast generation of random spanning trees and the effective resistance metric. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 2019–2036. SIAM, 2014.

[bib.bib50] [50] Cristopher Moore and Alexander Russell. Quantum walks on the hypercube. In Randomization and Approximation Techniques in Computer Science: 6th International Workshop, RANDOM 2002 Cambridge, MA, USA, September 13–15, 2002 Proceedings 5, pages 164–178. Springer, 2002. doi:10.1007/3-540-45726-7_14.

[bib.bib51] [51] Aleksandar Nikolov, Mohit Singh, and Uthaipon Tantipongpipat. Proportional volume sampling and approximation algorithms for a-optimal design. Mathematics of Operations Research, 47(2):847–877, 2022. doi:10.1287/MOOR.2021.1129.

[bib.bib52] [52] Peter C Richter. Quantum speedup of classical mixing processes. Physical Review A—Atomic, Molecular, and Optical Physics, 76(4):042306, 2007.

[bib.bib53] [53] Robin Richter, Shankar Bhamidi, and Sach Mukherjee. Improved baselines for causal structure learning on interventional data. Statistics and Computing, 33(5):93, 2023. doi:10.1007/S11222-023-10257-9.

[bib.bib54] [54] Mark Rudelson. Random vectors in the isotropic position. Journal of Functional Analysis, 164(1):60–72, 1999.

[bib.bib55] [55] Luís MS Russo, Andreia Sofia Teixeira, and Alexandre P Francisco. Linking and cutting spanning trees. Algorithms, 11(4):53, 2018. doi:10.3390/A11040053.

[bib.bib56] [56] Luís M. S. Russo, Andreia Sofia Teixeira, and Alexandre P. Francisco. Linking and cutting spanning trees. Algorithms, 11(4), 2018. doi:10.3390/a11040053.

[bib.bib57] [57] Aaron Schild. An almost-linear time algorithm for uniform random spanning tree generation. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 214–227, 2018. doi:10.1145/3188745.3188852.

[bib.bib58] [58] James Sharpnack, Aarti Singh, and Akshay Krishnamurthy. Detecting activations over graphs using spanning tree wavelet bases. In Artificial intelligence and statistics, pages 536–544. PMLR, 2013. URL: http://proceedings.mlr.press/v31/sharpnack13a.html.

[bib.bib59] [59] Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6):1913–1926, 2011. doi:10.1137/080734029.

[bib.bib60] [60] Leonardo V Teixeira, Renato M Assunção, and Rosangela H Loschi. Bayesian space-time partitioning by sampling and pruning spanning trees. Journal of Machine Learning Research, 20(85):1–35, 2019. URL: https://jmlr.org/papers/v20/16-615.html.

[bib.bib61] [61] David Bruce Wilson. Generating random spanning trees more quickly than the cover time. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 296–303, 1996. doi:10.1145/237814.237880.

Quantum Speedup for Sampling Random Spanning Trees

Abstract

Keywords and phrases:

Category:

Copyright and License:

2012 ACM Subject Classification:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Main Result

Theorem 1 (Quantum algorithm for sampling a random spanning tree).

Theorem 2 (Quantum lower bound for sampling a random spanning tree).

1.2 Techniques

1.2.1 Idea (and Barrier) for Quantum Speedups

1.2.2 Our Approach

Domain Sparsification Under Isotropy

Quantum Graph Algorithms and Quantum Multi-Sampling

1.2.3 Lower Bound

1.3 Open Questions

2 Preliminaries

2.1 Quantum Computational Model

2.2 Markov Chains and Mixing time

Theorem 3 (Data Processing Inequality).

Definition 4 (Mixing time).

Theorem 5 ([14], see also corollary 8 in [20]).

2.3 Laplacian and Graph Sparsification

Definition 6 (Laplacian).

Definition 7 (Effective Resistance).

Definition 8 (Leverage Score and Leverage Score Overestimates).

Lemma 9 (Foster’s theorem [30]).

Proof.

2.4 Strongly Rayleigh Distributions and Random Spanning Tree

Definition 10 (w-uniform distribution on trees).

Proposition 11 (Spanning Tree Marginals).

Proposition 12 (Spanning Trees are Strongly Rayleigh [15, Theorem 3.6]).

Theorem 13 (Random Tree Sampling [9, Theorem 2]).

2.5 Down-up and Up-down Walks

Definition 14 (Down operator).

Definition 15 (Up operator).

Proposition 16 (Proposition 25 in [7], see also Proposition 15 and 16 in [10]).

3 Main Algorithm

3.1 Isotropic Transformation

Definition 17 (Isotropic Transformation of a Graph).

Lemma 18 (Isotropic Bound).

Proof.

Theorem 19 ([10, Theorem 28]).

Proposition 20.

Proof.

3.2 QIsotropicSample Routine

Proposition 21.

Proof.

Lemma 22.

Proof.

Theorem 23 (Quantum uniform random k-subset sampling).

Proof.

Theorem 24 (Quantum Multi-Sampling in the Isotropic-Transformed Graph).

Proof.

3.3 Proof of Main Theorem

Proof.

4 Lower Bound

Proof.

References

Appendix A Useful Theorems

Proposition 25 (Quantum Algorithms for the Effective Resistance Overestimates, Adapted from [11, Claim 7.9]).

Proof.

Theorem 26 (Preparing many copies of a quantum state, [35, Theorem 1]).

Theorem 27 (Quantum algorithm for finding a minimum spanning tree, Theorem 4.2 in [29]).

Corollary 28 (Quantum algorithm for finding a maximum spanning tree, Adapted from Theorem 4.2 in [29]).

Proof.

Definition 10 ( $w$ -uniform distribution on trees).

Theorem 23 (Quantum uniform random $k$ -subset sampling).