Fundamental Problems in Classical and Quantum Algorithms

经典和量子计算中的基本问题。摘要：为了实现量子计算机的巨大计算能力，必须解决许多算法问题。这个项目研究两个主要问题。第一个是寻找量子计算机在破解密码系统之外的进一步应用。也就是说，寻找比经典算法提供指数级加速的量子算法。二是容错量子计算的高效实现。这是量子计算实际实验实现的重要一步。研究人员还研究了经典密码系统的设计，这些系统不受量子密码分析的影响。在经典计算中，在过去的几年里，在一个基本的算法问题上取得了突破性的成果——近似图分隔符。该项目研究了近似因子是否可以在$\sqrt{log n}$之外得到改进，运行时间是否可以在$\tilde{O}(n^{1.5})$之外得到改进，以及这些新技术对METIS等实用启发式算法在这一重要问题上的性能有何启示。最后，该项目研究了最近提出的b谷歌AdWords拍卖算法的典型性能。

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.oIn 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.