CIRCUIT-BASED QUANTUM ALGORITHMS

Abstract

The topic of this thesis is circuit-based quantum algorithms, which consists of three parts. First, it investigates the potential of the unbounded fan-out gate and the global tunable gate in building constant-depth quantum circuits. Two types of constant-depth constructions are proposed for implementing uniformly controlled gates, Boolean fan-in gates and query gates for quantum memory models. Second, the thesis addresses the optimal stopping problem, which involves choosing the right moment to stop the underlying process to maximize the expected payoff. Given mild assumptions, a quantum version of the least squares Monte Carlo algorithm is introduced, offering an almost quadratic speedup in time complexity over classical algorithms. Finally, the time complexity of quantum divide-and-conquer algorithms is studied. Two scenarios are considered: one where the recursive calls are input-independent, allowing a bottom-up approach to achieve speedup for various string problems, and another where recursive calls depend on the input, which can be addressed by two generic theorems, which yield a quantum speedup for a computational geometry problem and a string problem.