In previous papers about searches on star graphs several patterns have been made apparent; the speed up only occurs when graphs are ''tuned'' so that their time step operators have degenerate eigenvalues, and only certain initial states are effective. More than that, the searches are never faster than order square root of N time. In this thesis the problem is defined rigorously, the causes for all of these patterns are identified, sufficient and necessary conditions for quadratic-speed searches for any connected subgraph are demonstrated, the tolerance of these conditions is investigated, and it is shown that (unfortunately) we can do no better than order square root of N time. Along the way, a useful formalism is established that may be useful in future work involving highly symmetric graphs. The tools and techniques so derived are then used to demonstrate that tree graphs can be used for the computation of Boolean functions. The philosophy of Farhi's work on the continuous-time NAND tree is applied to a discrete-time walk with any (AND, OR, NAND, or NOR) gate at each vertex. Tentative results show that the vast majority of possible Boolean functions on N bits can be calculated in order square root of N time.
In previous papers about searches on star graphs several patterns have been made apparent; the speed up only occurs when graphs are ''tuned'' so that their time step operators have degenerate eigenvalues, and only certain initial states are effective. More than that, the searches are never faster than order square root of N time. In this thesis the problem is defined rigorously, the causes for all of these patterns are identified, sufficient and necessary conditions for quadratic-speed searches for any connected subgraph are demonstrated, the tolerance of these conditions is investigated, and it is shown that (unfortunately) we can do no better than order square root of N time. Along the way, a useful formalism is established that may be useful in future work involving highly symmetric graphs. The tools and techniques so derived are then used to demonstrate that tree graphs can be used for the computation of Boolean functions. The philosophy of Farhi's work on the continuous-time NAND tree is applied to a discrete-time walk with any (AND, OR, NAND, or NOR) gate at each vertex. Tentative results show that the vast majority of possible Boolean functions on N bits can be calculated in order square root of N time.
In previous papers about searches on star graphs several patterns have been made apparent; the speed up only occurs when graphs are 'tuned' so that their time step operators have degenerate eigenvalues, and only certain initial states are effective. More than that, the searches are never faster than time. In this paper the problem is defined rigorously, the causes for all of these patterns are identified, sufficient and necessary conditions for quadratic-speed searches for any connected subgraph are demonstrated, the tolerance of these conditions is investigated, and it is shown that (unfortunately) we can do no better than time. Along the way, a useful formalism is established that may be useful in future work involving highly symmetric graphs.
This thesis is on quantum algorithms. It has three main themes: \n(1) quantum walk based search algorithms, \n(2) quantum rejection sampling, and \n(3) the Boolean function hidden shift problem. \nThe first two parts deal with generic techniques for constructing quantum algorithms, and the last part is on quantum algorithms for a specific algebraic problem. \n \nIn the first part of this thesis we show how certain types of random walk search algorithms can be transformed into quantum algorithms that search quadratically faster. More formally, given a random walk on a graph with an unknown set of marked vertices, we construct a quantum walk that finds a marked vertex in a number of steps that is quadratically smaller than the hitting time of the random walk. The main idea of our approach is to interpolate the random walk from one that does not stop when a marked vertex is found to one that stops. The quantum equivalent of this procedure drives the initial superposition over all vertices to a superposition over marked vertices. We present an adiabatic as well as a circuit version of our algorithm, and apply it to the spatial search problem on the 2D grid. \n \nIn the second part we study a quantum version of the problem of resampling one probability distribution to another. More formally, given query access to a black box that produces a coherent superposition of unknown quantum states with given amplitudes, the problem is to prepare a coherent superposition of the same states with different specified amplitudes. Our main result is a tight characterization of the number of queries needed for this transformation. By utilizing the symmetries of the problem, we prove a lower bound using a hybrid argument and semidefinite programming. For the matching upper bound we construct a quantum algorithm that generalizes the rejection sampling method first formalized by von~Neumann in~1951. We describe quantum algorithms for the linear equations problem and quantum Metropolis sampling as applications of quantum rejection sampling. \n \nIn the third part we consider a hidden shift problem for Boolean functions: given oracle access to f(x+s), where f(x) is a known Boolean function, determine the hidden shift s. We construct quantum algorithms for this problem using the "pretty good measurement" and quantum rejection sampling. Both algorithms use the Fourier transform and their complexity can be expressed in terms of the Fourier spectrum of f (in particular, in the second case it relates to "water-filling" of the spectrum). We also construct algorithms for variations of this problem where the task is to verify a given shift or extract only a single bit of information about it.
We analyze the potential for different types of searches using the formalism of scattering random walks on quantum computers. Given a particular type of graph consisting of nodes and connections, a ``tree maze,'' we would like to find a selected final node as quickly as possible, faster than any classical search algorithm. We show that this can be done using a quantum random walk, both through numerical calculations as well as by using the eigenvectors and eigenvalues of the quantum system.
Quantum computation is a new computational paradigm which can provide fundamentally faster computation than in the classical regime. This is dependent on finding efficient quantum algorithms for problems of practical interest. One of the most successful tools in developing new quantum algorithms is the quantum walk. In this thesis, we explore two applications of the discrete time quantum walk. In addition, we introduce an experimental scheme for generating cluster states, a universal resource for quantum computation. We give an explicit construction which provides a link between the circuit model of quantum computation, and a graph structure on which the discrete time quantum walk traverses, performing the same computation. We implement a universal gate set, proving the discrete time quantum walk is universal for quantum computation, thus confirming any quantum algorithm can be recast as a quantum walk algorithm. In addition, we study factors affecting the efficiency of the quantum walk search algorithm. Although there is a strong dependence on the spatial dimension of the structure being searched, we find secondary dependencies on other factors including the connectivity and disorder (symmetry). Fairly intuitively, as the connectivity increases, the efficiency of the algorithm increases, as the walker can coalesce on the marked state with higher probability in a quicker time. In addition, we find as disorder in the system increases, the algorithm can maintain the quantum speed up for a certain level of disorder before gradually reverting to the classical run time. Finally, we give an abstract scheme for generating cluster states. We see a linear scaling, better than many schemes, as doubling the size of the generating grid in our scheme produces a cluster state which is double the depth. Our scheme is able to create other interesting topologies of entangled states, including the unit cell for topological error correcting schemes.
In this dissertation we demonstrate that the continuous-time quantum walk models remain powerful for nontrivial graph structures. We consider two aspects of this problem. First, it is known that the standard Continuous-Time Quantum Walk (CTQW), proposed by Childs and Goldstone, can propagate quickly on the infinite path graph. However, the Schrödinger equation requires the Hamiltonian to be symmetric, and thus only undirected graphs can be implemented. In this thesis, we address the question, whether it is possible to construct a continuous-time quantum walk on general directed graphs, preserving its propagation properties. Secondly, the quantum spatial search defined through CTQW has been proven to work well on various undirected graphs. However, most of these graphs have very simple structures. The most advanced results concerned the Erdős-Rényi model of random graphs, which is the most popular but not realistic random graph model, and Barabási-Albert random graphs, for which full quadratic speed-up was not confirmed. In the scope of this aspect we analyze, whether quantum speed-up is observed for complicated graph structures as well.
We study quantum walks on general graphs from the point of view of scattering theory. For a general finite graph we choose two vertices and attach one half line to each. We are interested in walks that proceed from one half line, through the graph, to the other. The particle propagates freely on the half lines but is scattered at each vertex in the original graph. The probability of starting on one line and reaching the other after n steps can be expressed in terms of the transmission amplitude for the graph. An example is presented. Classical random walks on graphs can be used to construct algorithms that solve 2-SAT, graph connectivity problems, and for finding satsifying assignments for Boolean functions. A hope is that recently defined quantum walks will prove similarly useful in the development of quantum algorithms. In fact, it has recently been shown that it is possible to use a quantum walk to perform a search on the hypercube faster than can be done classically [1]. In this problem