In this work, we mostly concentrate on the hidden shift problem for non-injective functions. It is worthwhile to know that the query complexity of the non-injective hidden shift problem is exponential in the worst case by the well known bounds on the unstructured search problem. Hence, we can make this problem more tractable by imposing additional constraints on the problem. Perhaps the first constraint that comes to mind is to address the average case problem. In this work, we show that the average case non-injective hidden shift problem can be reduced to the injective hidden shift problem by giving one such reduction. The reduction is based on a tool we developed called injectivization. The result is strong in the sense that the underlying group can be any finite group and that the non-injective functions for which we have defined the hidden shift problem can have range in an arbitrary finite set. Using this tool, we simplify the main result of a recent paper by about the hidden shift problem for Boolean-valued functions by reducing that problem to Simon's problem. They also posed an open question which is subject to personal interpretation. We answer the seemingly most general interpretation of the question. However, we use our own techniques in doing so (the authors ask if their techniques can be used for addressing that problem). Another constraint that one can consider is to have a promise on the structure of the functions. In this work we consider the hidden shift problem for c-almost generalized bent functions. A class of functions which we defined that includes the generalized bent functions. Then we turn our attention toward the generalized hidden shift problem which is easier than injective hidden shift problem and hence more tractable. We state some of our observations about this problem. Finally we show that the average classical query complexity of the non-injective hidden shift problem over groups of form (Z/mZ)^n when m is a constant is exponential, which also immediately implies that the classical average query complexity of the non-injective hidden shift problem is exponential. We also show that the worst-case classical query complexity of the generalized injective hidden shift problem over the same group is high, which implies that the classical query complexity of the hidden shift problem is high.

In this work, we mostly concentrate on the hidden shift problem for non-injective functions. It is worthwhile to know that the query complexity of the non-injective hidden shift problem is exponential in the worst case by the well known bounds on the unstructured search problem. Hence, we can make this problem more tractable by imposing additional constraints on the problem. Perhaps the first constraint that comes to mind is to address the average case problem. In this work, we show that the average case non-injective hidden shift problem can be reduced to the injective hidden shift problem by giving one such reduction. The reduction is based on a tool we developed called injectivization. The result is strong in the sense that the underlying group can be any finite group and that the non-injective functions for which we have defined the hidden shift problem can have range in an arbitrary finite set. Using this tool, we simplify the main result of a recent paper by about the hidden shift problem for Boolean-valued functions by reducing that problem to Simon's problem. They also posed an open question which is subject to personal interpretation. We answer the seemingly most general interpretation of the question. However, we use our own techniques in doing so (the authors ask if their techniques can be used for addressing that problem). Another constraint that one can consider is to have a promise on the structure of the functions. In this work we consider the hidden shift problem for c-almost generalized bent functions. A class of functions which we defined that includes the generalized bent functions. Then we turn our attention toward the generalized hidden shift problem which is easier than injective hidden shift problem and hence more tractable. We state some of our observations about this problem. Finally we show that the average classical query complexity of the non-injective hidden shift problem over groups of form (Z/mZ)^n when m is a constant is exponential, which also immediately implies that the classical average query complexity of the non-injective hidden shift problem is exponential. We also show that the worst-case classical query complexity of the generalized injective hidden shift problem over the same group is high, which implies that the classical query complexity of the hidden shift problem is high.

This thesis is on quantum algorithms. It has three main themes: (1) quantum walk based search algorithms, (2) quantum rejection sampling, and (3) the Boolean function hidden shift problem. The first two parts deal with generic techniques for constructing quantum algorithms, and the last part is on quantum algorithms for a specific algebraic problem. In 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. In 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. In 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.

This thesis is on quantum algorithms. It has three main themes: (1) quantum walk based search algorithms, (2) quantum rejection sampling, and (3) the Boolean function hidden shift problem. The first two parts deal with generic techniques for constructing quantum algorithms, and the last part is on quantum algorithms for a specific algebraic problem. In 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. In 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. In 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.