Electric flow sampling (elfs) is a new tool in the quantum walk toolbox and a useful primitive for solving search, sampling and optimization problems on graphs. We refine this tool by showing that there exists a zero-error transducer for implementing elfs. More broadly, we establish a zero-error transducer for reflecting about the intersection of two subspaces, yielding an errorfree transducer version of the effective gap lemma. Building on this result, we obtain improved quantum walk algorithms for estimating effective resistances and span program witness sizes with an optimal error scaling, and for sampling from the random walk arrival distribution, via the composition of many elfs. Using this last algorithm, we obtain an up-to-quadratic quantum speedup for semi-supervised learning on expander graphs.
Electric flow sampling (elfs) is a new tool in the quantum walk toolbox and a useful primitive for solving search, sampling and optimization problems on graphs. We refine this tool by showing that there exists a zero-error transducer for implementing elfs. More broadly, we establish a zero-error transducer for reflecting about the intersection of two subspaces, yielding an errorfree transducer version of the effective gap lemma. Building on this result, we obtain improved quantum walk algorithms for estimating effective resistances and span program witness sizes with an optimal error scaling, and for sampling from the random walk arrival distribution, via the composition of many elfs. Using this last algorithm, we obtain an up-to-quadratic quantum speedup for semi-supervised learning on expander graphs.
We study an elementary Markov process on graphs based on electric flow sampling (elfs). The elfs process repeatedly samples from an electric flow on a graph. While the sinks of the flow are fixed, the source is updated using the electric flow sample, and the process ends when it hits a sink vertex. We argue that this process naturally connects to many key quantities of interest. E.g., we describe a random walk coupling which implies that the elfs process has the same arrival distribution as a random walk. We also analyze the electric hitting time, which is the expected time before the process hits a sink vertex. As our main technical contribution, we show that the electric hitting time on trees is logarithmic in the graph size and weights. The initial motivation behind the elfs process is that quantum walks can sample from electric flows, and they can hence implement this process very naturally. This yields a quantum walk algorithm for sampling from the random walk arrival distribution, which has widespread applications. It complements the existing line of quantum walk search algorithms which only return an element from the sink, but yield no insight in the distribution of the returned element. By our bound on the electric hitting time on trees, the quantum walk algorithm on trees requires quadratically fewer steps than the random walk hitting time, up to polylog factors.
Over the last decade, a large number of quantum algorithms have been discovered that outperform their classical counterparts. However, depending on the main techniques used, most of them fall into only three categories. The first category uses quantum Fourier transform to achieve super-polynomial speedup in group-theoretical problems. The second category uses amplitude amplification to achieve polynomial speedup in search problems. The third category simulates quantum many-body systems. Finding a new class of quantum algorithms has proven a challenging task. This dissertation explores several new approaches to developing quantum algorithms. These approaches include span programs, electrical flows and nonsparse Hamiltonian simulation. We demonstrate their power by successfully applying them to some useful problems, including tree detection, effective resistance estimation and curve fitting. All of these algorithms are time-efficient, and some of them are proven to be (nearly) optimal.Span program is a linear-algebraic computation model originally proposed to prove circuit lower bounds. Recently, it is found to be closely related to quantum query complexity. We develop a span-program-based quantum algorithm for the following variant of the tree containment problem. Let T be a fixed tree. Given the ntimesn adjacency matrix of a graph G, we need to decide whether G contains T as a subgraph, or G does not contain T as a minor, under the promise that one of these cases holds. We call this problem is the subgraph/not-a-minor problem for T. We show that this problem can be solved by a quantum algorithm with O(n) query complexity and tildeO(n) time complexity. This query complexity is optimal, and this time complexity is tight up to poly-logarithmic factors. Electrical network theory has many applications to the design and analysis of classical algorithms. Its connection to quantum computation, however, remains mostly unclear. We give two quantum algorithms for approximating the effective resistance between two given vertices in an electrical network. Both of them have time complexity polynomial in logn, d, c, 1/phi and 1/epsilon, where n is the number of vertices, d is the maximum degree of the vertices, c is the ratio of the largest to the smallest edge resistance, phi is the conductance of the network, and epsilon is the relative error. Our algorithms have exponentially better dependence on n than classical algorithms. Furthermore, we prove that the polynomial dependence on the inverse conductance is necessary. As a consequence, our algorithms cannot be greatly improved. Finally, as a by-product, our second algorithm also produces a quantum state encoding the electrical flow between two given vertices in a network, which might be of independent interest. Our algorithms are developed by using quantum tools to analyze the algebraic properties of graph-related matrices. While the first one relies on inverting the Laplacian matrix, the second one relies on projecting onto the kernel of the weighted incidence matrix. It is hopeful that more quantum algorithms could be designed in similar way. Curve fitting is the process of constructing a (simple continuous) curve that has the best fit to a series of data points. It is a common practice in many fields of science and engineering, because it can help us to understand the relationships among two or more variables, and to infer the values of a function where no data are available. We propose efficient quantum algorithms for estimating the best-fit parameters and the quality of least-square curve fitting. The running times of our algorithms are polynomial in logn, d, kappa, nu, chi, 1/Phi and 1/epsilon, where n is the number of data points to be fitted, d is the dimension of the feature vectors, kappa is the condition number of the design matrix, nu and chi are some parameters reflecting the variances of the design matrix and response vector, Phi is the fit quality, and epsilon is the tolerable error. Our algorithms have exponentially better dependence on n than classical algorithms. They are designed by combining the techniques of phase estimation and density matrix exponentiation for nonsparse Hamiltonian simulation.
We present a quantum algorithm that generates a uniform superposition over the spanning trees of a graph -- also known as a q-sample -- using only a sub-linear number of queries to the graph. This goes beyond previous work that focuses on generating classical samples, including a recent quantum algorithm by Apers, Gao, Ji, and Liu [ICALP 2025]. For an n-vertex, m-edge graph, our algorithm admits a pre-processing step of O~(mn+m1−δ), after which each q-sample can be generated in O~(n1+2δ) for any δ. Alternatively, k independent q-samples can be generated at a total cost of O~(kmn). We also prove a matching lower bound up to logarithmic factors, showing that our algorithm is essentially optimal. Further tradeoffs are given in the paper. In comparison, the optimal classical algorithms (Anari, Liu and Vuong [FOCS 2022]) need an O~(m) pre-processing step, after which each sample costs O~(n) operations. These results yield faster quantum walk-based algorithms for counting spanning trees or finding a marked one.
Our result is obtained via quantum walk sampling over a sequence of slowly-changing Markov chains. Each chain is an isotropized up-down walk that mixes rapidly to the spanning tree distribution of the input graph. A key ingredient is an amortized data structure supporting fast implementation of the associated quantum walk operators throughout the sequence. This data structure maintains access to a spectral sparsifier and a leverage score sampler that evolve with the underlying graph.
We give a new quantum algorithm to sample from probability distributions over graph vertices quadratically faster than the optimal classical algorithm, which uses random walks with stopping rules. Efficient sampling is an important computational task used in simulations based on stochastic processes. This is the first quantum algorithm that achieves a quadratic speed-up for sampling from general probability distributions over graph vertices. Our algorithm generalizes the controlled quantum walk algorithm proposed by Dohotaru and Høyer in 2015. Our main technical innovation is to allow for multiple distinct controlled reflections. This allows us to generate the quantum state analogous to the target probability distribution over vertices. This quantum state, when measured, gives a corresponding classical sample from the target distribution. We also give a second classical algorithm for sampling from probability distributions over graph vertices. This algorithm adds different self-loops to each vertex of the random walk. We show how to construct the quantum analogue of this algorithm. Finally, we show that we can embed this quantum analogue into our controlled quantum walk.
This work describes a new algorithm for creating a superposition over the edge set of a graph, encoding a quantum sample of the random walk stationary distribution. The algorithm requires a number of quantum walk steps scaling as O(m1/3δ−1/3), with m the number of edges and δ the random walk spectral gap. This improves on existing strategies by initially growing a classical seed set in the graph, from which a quantum walk is then run. The algorithm leads to a number of improvements: (i) it provides a new bound on the setup cost of quantum walk search algorithms, (ii) it yields a new algorithm for st-connectivity, and (iii) it allows to create a superposition over the isomorphisms of an n-node graph in time O(2n/3), surpassing the Ω(2n/2) barrier set by index erasure.
Given an undirected, weighted graph, with n vertices and m edges, and two special vertices s and t, the problem is to find the shortest path between them. We give two bounded-error quantum algorithms with improved runtime in the adjacency list model that solve the problem on special classes of graphs defined via pathfinding probabilities of classical random walks and the electrical network framework. Firstly, we give a simple quantum algorithm based on sampling edges from a graph via the quantum flow state and running a classical algorithm on the sampled edges. It runs in O~(l2m) expected time and uses O(logn) space on graphs where the shortest s-t path is also a minimum resistance s-t subgraph. Our main algorithm can be thought of as a divide and conquer version of this approach and works on a special class of graphs where classical loop-erased random walk has a probability q>0.537 of finding the shortest s-t path. In such cases the quantum algorithm outputs the shortest s-t path with high probability in O(ℓm) expected time and O(logn) space, where l is the length (or total weight, in case of weighted graphs) of the shortest s-t path. This algorithm can be parallelised to O~(lm) circuit depth when using O(llogn) space. With the latter we partially resolve with an affirmative answer the open problem of whether a path between two vertices can be found in the number of steps required to detect it.