Fundamental Problems in Classical and Quantum Algorithms

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

Fundamental Problems in Classical and Quantum Computation. Abstract: To realize the tremendous computational power of quantum computers there are a number of algorithmic issues that must be addressed. This project studies two major issues. The first is the search for further applications for quantum computers that go beyond the breaking of cryptosystems. i.e. the search for quantum algorithms that provide an exponential speedup over classical algorithms. The second is efficient implementation of fault-tolerant quantum computation. This is an essential step towards the actual experimental realization of quantum computation. The investigators also study the design of classical cryptosystems that are immune to quantum cryptanalysis.o In classical computing, over the last few years there have been breakthrough results on a fundamental algorithmic problem ---approximating graph separators. This project studies both whether the approximation factor can be improved beyond the $\sqrt{log n}$, whether the running time can be improved beyond $\tilde{O}(n^{1.5})$ and what insights these new techniques give into the performance of practical heuristics such as METIS for this important problem. Finally, the project studies the typical performance of a recently proposed algorithm for the Google AdWords auction.