On quantum algorithms and limitations for convex optimization and lattice problems

Optimization is the process of selecting the best option from all possibilities, and problems related to finding the best option among many options are called optimization problems. A few examples of such problems are route picking, partial loading, crew scheduling, and portfolio optimization, and those problems naturally appear everywhere in society and in our daily lives. Most optimization problems could be solved by listing all possibilities and then searching for the best one, but we aim to find a systematic strategy (known as an algorithm) that finds the optimal solution in the least amount of time, as brute-force searching is often too time-consuming. That is, we would like to find optimal algorithms for finding optimal solutions. Quantum physics provides a more accurate explanation and prediction of nature in many cases than classical physics. Therefore, a quantum computer has the potential to be more powerful and useful than a classical one for solving optimization problems, though the extent of this advantage remains an active area of research. Moreover, designing algorithms for a quantum computer requires fundamentally different ideas and concepts than for a classical computer. In this thesis, we explore the uses of quantum computers in solving several fundamental optimization problems. We specifically consider solving linear regression, finding the top eigenvectors of a matrix, and finding the shortest nonzero vector of a lattice. More precisely, we provide near-optimal quantum algorithms that are asymptotically better than the best-possible classical algorithms for linear regression with $\ell_1$-norm constraint (known as Lasso) and for approximating the top eigenvectors of a matrix. Our algorithms for finding the shortest nonzero vector of a lattice are asymptotically better than the best known classical algorithms. On the other hand, there are some problems for which no useful computational advantage is possible, even when we use quantum computers. This situation, however, can sometimes be beneficial if we do not want quantum computers to solve specific problems fast - say, problems relevant to post-quantum cryptography. In such a situation, we would like evidence demonstrating the difficulty of solving these problems on a quantum computer. To this end, we propose variants of Boolean satisfiability problems that are believed to not be more efficiently solvable on a quantum computer, and then via reductions use those (conjectured) quantum lower bounds to study the quantum limitations of several popular optimization problems like lattice problems, quantum strong simulation, and hitting set problems.

• View at Worldcat

Full Text ( Final Version , 16mb )