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.
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.
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.
Given a classical query algorithm as a decision tree, when does there exist a quantum query algorithm with a speed-up over the classical one? We provide a general construction based on the structure of the underlying decision tree, and prove that this can give us an up-to-quadratic quantum speed-up. In particular, we obtain a bounded-error quantum query algorithm of cost O(s) to compute a Boolean function (more generally, a relation) that can be computed by a classical (even randomized) decision tree of size s. Lin and Lin [ToC'16] and Beigi and Taghavi [Quantum'20] showed results of a similar flavor, and gave upper bounds in terms of a quantity which we call the "guessing complexity" of a decision tree. We identify that the guessing complexity of a decision tree equals its rank, a notion introduced by Ehrenfeucht and Haussler [Inf. Comp.'89] in the context of learning theory. This answers a question posed by Lin and Lin, who asked whether the guessing complexity of a decision tree is related to any complexity-theoretic measure. We also show a polynomial separation between rank and randomized rank for the complete binary AND-OR tree. Beigi and Taghavi constructed span programs and dual adversary solutions for Boolean functions given classical decision trees computing them and an assignment of non-negative weights to its edges. We explore the effect of changing these weights on the resulting span program complexity and objective value of the dual adversary bound, and capture the best possible weighting scheme by an optimization program. We exhibit a solution to this program and argue its optimality from first principles. We also exhibit decision trees for which our bounds are asymptotically stronger than those of Lin and Lin, and Beigi and Taghavi. This answers a question of Beigi and Taghavi, who asked whether different weighting schemes could yield better upper bounds.
Given a classical query algorithm as a decision tree, when does there exist a quantum query algorithm with a speed-up over the classical one? We provide a general construction based on the structure of the underlying decision tree, and prove that this can give us an up-to-quadratic quantum speed-up. In particular, we obtain a bounded-error quantum query algorithm of cost O(s) to compute a Boolean function (more generally, a relation) that can be computed by a classical (even randomized) decision tree of size s .Lin and Lin [ToC'16] and Beigi and Taghavi [Quantum'20] showed results of a similar flavor, and gave upper bounds in terms of a quantity which we call the "guessing complexity" of a decision tree. We identify that the guessing complexity of a decision tree equals its rank, a notion introduced by Ehrenfeucht and Haussler [Inf. Comp.'89] in the context of learning theory. This answers a question posed by Lin and Lin, who asked whether the guessing complexity of a decision tree is related to any complexity-theoretic measure. We also show a polynomial separation between rank and randomized rank for the complete binary AND-OR tree.Beigi and Taghavi constructed span programs and dual adversary solutions for Boolean functions given classical decision trees computing them and an assignment of non-negative weights to its edges. We explore the effect of changing these weights on the resulting span program complexity and objective value of the dual adversary bound, and capture the best possible weighting scheme by an optimization program. We exhibit a solution to this program and argue its optimality from first principles. We also exhibit decision trees for which our bounds are asymptotically stronger than those of Lin and Lin, and Beigi and Taghavi. This answers a question of Beigi and Taghavi, who asked whether different weighting schemes could yield better upper bounds.
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.
We consider the following question in query complexity: Given a classical query algorithm in the form of a decision tree, when does there exist a quantum query algorithm with a speed-up (i.e., that makes fewer queries) over the classical one? We provide a general construction based on the structure of the underlying decision tree, and prove that this can give us an up-to-quadratic quantum speed-up in the number of queries. In particular, our results give a bounded-error quantum query algorithm of cost O(√s) to compute a Boolean function (more generally, a relation) that can be computed by a classical (even randomized) decision tree of size s. This recovers an O(√n) algorithm for the Search problem, for example. Lin and Lin [Theory of Computing'16] and Beigi and Taghavi [Quantum'20] showed results of a similar flavor. Their upper bounds are in terms of a quantity which we call the “guessing complexity” of a decision tree. We identify that the guessing complexity of a decision tree equals its rank, a notion introduced by Ehrenfeucht and Haussler [Information and Computation'89] in the context of learning theory. This answers a question posed by Lin and Lin, who asked whether the guessing complexity of a decision tree is related to any measure studied in classical complexity theory. We also show a polynomial separation between rank and its natural randomized analog for the complete binary AND-OR tree. Beigi and Taghavi constructed span programs and dual adversary solutions for Boolean functions given classical decision trees computing them and an assignment of non-negative weights to edges of the tree. We explore the effect of changing these weights on the resulting span program complexity and objective value of the dual adversary bound, and capture the best possible weighting scheme by an optimization program. We exhibit a solution to this program and argue its optimality from first principles. We also exhibit decision trees for which our bounds are strictly stronger than those of Lin and Lin, and Beigi and Taghavi. This answers a question of Beigi and Taghavi, who asked whether different weighting schemes in their construction could yield better upper bounds.
In the thesis, we use a recently developed tight characterisation of quantum query complexity, the adversary bound, to develop new quantum algorithms and lower bounds. Our results are as follows: * We develop a new technique for the construction of quantum algorithms: learning graphs. * We use learning graphs to improve quantum query complexity of the triangle detection and the k-distinctness problems. * We prove tight lower bounds for the k-sum and the triangle sum problems. * We construct quantum algorithms for some subgraph-finding problems that are optimal in terms of query, time and space complexities. * We develop a generalisation of quantum walks that connects electrical properties of a graph and its quantum hitting time. We use it to construct a time-efficient quantum algorithm for 3-distinctness.