In this work, we generalize the recently-introduced graph composition framework to the non-boolean setting. A quantum algorithm in this framework is represented by a hypergraph, where each hyperedge is adjacent to multiple vertices. The input and output to the quantum algorithm is represented by a set of boundary vertices, and the hyperedges act like switches, connecting the input vertex to the output that the algorithm computes. Apart from generalizing the graph composition framework, our new proposed framework unifies the quantum divide and conquer framework, the decision-tree framework, and the unified quantum walk search framework. For the decision trees, we additionally construct a quantum algorithm from an improved weighting scheme in the non-boolean case. For quantum walk search, we show how our techniques naturally allow for amortization of the subroutines' costs. Previous work showed how one can speed up ``detection'' of marked vertices by amortizing the costs of the quantum walk. In this work, we extend these results to the setting of ``finding'' such marked vertices, albeit in some restricted settings. Along the way, we provide a novel analysis of irreducible, reversible Markov processes, by linear-algebraically connecting its effective resistance to the random walk operator. This significantly simplifies the algorithmic implementation of the quantum walk search algorithm, achieves an amortization speed-up for quantum walks over Johnson graphs, avoids the need for quantum fast-forwarding, and removes the log-factors from the query complexity statements.
In this work, we generalize the recently-introduced graph composition framework to the non-boolean setting. A quantum algorithm in this framework is represented by a hypergraph, where each hyperedge is adjacent to multiple vertices. The input and output to the quantum algorithm is represented by a set of boundary vertices, and the hyperedges act like switches, connecting the input vertex to the output that the algorithm computes. Apart from generalizing the graph composition framework, our new proposed framework unifies the quantum divide and conquer framework, the decision-tree framework, and the unified quantum walk search framework. For the decision trees, we additionally construct a quantum algorithm from an improved weighting scheme in the non-boolean case. For quantum walk search, we show how our techniques naturally allow for amortization of the subroutines' costs. Previous work showed how one can speed up detection'' of marked vertices by amortizing the costs of the quantum walk. In this work, we extend these results to the setting of finding'' such marked vertices, albeit in some restricted settings. Along the way, we provide a novel analysis of irreducible, reversible Markov processes, by linear-algebraically connecting its effective resistance to the random walk operator. This significantly simplifies the algorithmic implementation of the quantum walk search algorithm, achieves an amortization speed-up for quantum walks over Johnson graphs, avoids the need for quantum fast-forwarding, and removes the log-factors from the query complexity statements.
In this work, we unify several quantum algorithmic frameworks for boolean functions that are based on the quantum adversary bound. First, we show that the st-connectivity framework subsumes the (adaptive/extended) learning graph framework, and the weighted-decision-tree framework. Additionally, we show that every randomized algorithm can be turned into an st-connectivity problem as well, with the same complexity up to constants. This situates the st-connectivity framework in between randomized and quantum algorithms, indicating that it's an intermediate computational model between classical and quantum. We also introduce a generalization of the st-connectivity framework, the \textit{graph composition framework}, and show that it subsumes part of the quantum divide and conquer framework, and it is itself subsumed by the multidimensional quantum walk framework. Second, we investigate these frameworks' power by investigating the most efficient algorithms they can produce, in terms of the number of queries to the input. We show that the weighted-decision-tree framework's power is polynomially related to deterministic query complexity, showing that the quantum speed-ups that can be obtained with this framework are at most quadratic. Finally, we turn our attention to time-efficient implementations of the algorithms constructed through the st-connectivity and graph composition frameworks. To that end, we convert instances to the two-subspace phase estimation framework, and we show how we can implement these as transducers. This has the added benefit of removing the effective spectral gap lemma from the construction, significantly simplifying the analysis. We showcase the techniques developed in this work to give improved algorithms for various string search problems.
Due to the difficulty of constructing new quantum algorithms, frameworks that facilitate this construction are of great importance in quantum computing. These frameworks reduce the problem of coming up with a quantum algorithm to that of constructing some combinatorial object that is often much simpler to reason about. The implementation and analysis of an algorithm for the specified problem follow from the properties of this object. A number of such frameworks have been extremely successful in leading to the development of numerous quantum algorithms for a variety of problems. In this thesis, we build on two of these frameworks, the quantum walk search framework, and the span program framework, extending their algorithmic potential. \n \nThe quantum walk search framework gives a generic quantum analogue to a specific type of classical algorithm based on random walks. If one can construct a classical algorithm of this form, a corresponding quantum algorithm with better complexity immediately follows. In this framework, a generic algorithm is constructed from several subroutines for which implementations must be given for each application. One of these subroutines, a checking subroutine, is run many times throughout the algorithm. This subroutine may be implemented by any quantum algorithm that satisfies the required functionality, including another quantum walk algorithm. By making a slight modification to the quantum walk framework, we can show how to nest a quantum walk algorithm in the checking subroutine of another quantum walk algorithm in a way that gives better complexity than the naive nesting. This modification allows us to reproduce a number of upper bounds previously obtained in another framework, the learning graph framework, including upper bounds for triangle finding, and more generally, subgraph finding for constant-sized subgraphs. Porting these upper bounds over to the setting of quantum walks is desirable because the algorithms achieved in the quantum walk search framework are much more explicit than those of the learning graph framework, making them easier to work with, modify, and build on, as needed. Our efficient nested checking idea has already been used to come up with new quantum algorithms for finding sub-hypergraphs. \n \nAnother subroutine that is called repeatedly by the generic quantum walk search algorithm is the update subroutine. It was not clear how to use a quantum walk algorithm to perform this step, but by making another slight modification to the quantum walk search framework, we are able to show how to nest a quantum walk in the update step of another quantum walk in an efficient way. Our technique for doing this is a special case of a technique that allows the update to be implemented with garbage --- i.e., some unwanted data in an auxiliary register, entangled with the desired state. This technique may have other applications. \n \nUsing the nested update technique, we are able to improve the best known upper bounds on the time complexity of k-distinctness. Previously the best known upper bound on the time complexity was nk/(k+1), due to Ambainis. Belovs had recently improved the query complexity of k-distinctness to o(n3/4) for all k, but since this upper bound was obtained in a framework called span programs, which only gives upper bounds on quantum query complexity, there was no known time efficient implementation of his k-distinctness algorithm. We use ideas from his construction and our nested update technique to get a quantum time upper bound for 3-distinctness of n5/7, matching his quantum query upper bound. We can generalize our algorithm get a time upper bound of n(k−1)/k for any k>3, slightly improving on the best previous upper bound. \n \nAnother framework, the span program framework, is known to be equivalent to quantum query complexity, in the sense that for any Boolean decision problem, there exists a span program construction that yields a tight upper bound on its quantum query complexity. We explore several variations of this framework. First, we slightly modify the definition of a span program so that we can show that for \\emph{any} (not necessarily Boolean) decision problem, there is a span program construction that yields a tight upper bound on its quantum query complexity. Previously this was only known up to logarithmic factors. We also explore several approximate versions of span programs, and show them to be equivalent. Finally, we explore the structure of span program witnesses, and use this structure to present an algorithm for evaluating span programs that is straightforward and intuitive. We also show how to evaluate approximate span programs, opening the possibility for the construction of new upper bounds using approximate span programs.
Many quantum algorithms critically rely on quantum walk search, or the use of quantum walks to speed up search problems on graphs. However, the main results on quantum walk search are scattered over different, incomparable frameworks, such as the hitting time framework, the MNRS framework, and the electric network framework. As a consequence, a number of pieces are currently missing. For example, recent work by Ambainis et al. (STOC'20) shows how quantum walks starting from the stationary distribution can always find elements quadratically faster. In contrast, the electric network framework allows quantum walks to start from an arbitrary initial state, but it only detects marked elements. We present a new quantum walk search framework that unifies and strengthens these frameworks, leading to a number of new results. For example, the new framework effectively finds marked elements in the electric network setting. The new framework also allows to interpolate between the hitting time framework, minimizing the number of walk steps, and the MNRS framework, minimizing the number of times elements are checked for being marked. This allows for a more natural tradeoff between resources. In addition to quantum walks and phase estimation, our new algorithm makes use of quantum fast-forwarding, similar to the recent results by Ambainis et al. This perspective also enables us to derive more general complexity bounds on the quantum walk algorithms, e.g., based on Monte Carlo type bounds of the corresponding classical walk. As a final result, we show how in certain cases we can avoid the use of phase estimation and quantum fast-forwarding, answering an open question of Ambainis et al.
We show a simple generalization of the quantum walk algorithm for search in backtracking trees by Montanaro (ToC 2018) to the case where vertices can have different times of computation. If a vertex v in the tree of depth D is computed in tv steps from its parent, then we show that detection of a marked vertex requires O(TD) queries to the steps of the computing procedures, where T=∑vtv2. This framework provides an easy and convenient way to re-obtain a number of other quantum frameworks like variable time search, quantum divide & conquer and bomb query algorithms. The underlying algorithm is simple, explicitly constructed, and has low poly-logarithmic factors in the complexity.
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.
Quantum walks have been useful for designing quantum algorithms that outperform their classical versions for a variety of search problems. Most of the papers, however, consider a search space containing a single marked element. We show that if the search space contains more than one marked element, their placement may drastically affect the performance of the search. More specifically, we study search by quantum walks on general graphs and show a wide class of configurations of marked vertices, for which search by quantum walk needs Ω(N) steps, that is, it has no speed-up over the classical exhaustive search. The demonstrated configurations occur for certain placements of two or more adjacent marked vertices. The analysis is done for the two-dimensional grid and hypercube, and then is generalized for any graph. Additionally, we consider an algorithmic application of the found effect. We investigate a problem of detection of a perfect matching in a bipartite graph. We use the found effect as an algorithmic building block and construct quantum algorithm which, for a specific class of graphs, outperforms its classical analogs.