Fundamental Problems in Classical and Quantum Algorithms

经典与量子计算中的基本问题。翻译后摘要：要实现量子计算机的巨大计算能力，有一些算法的问题，必须加以解决。 本项目主要研究两个问题。首先是寻找量子计算机的进一步应用，超越密码系统的破坏。即，对提供超过经典算法的指数加速的量子算法的搜索。二是容错量子计算的高效实现。这是迈向量子计算实际实验实现的重要一步。 研究人员还研究了对量子密码分析免疫的经典密码系统的设计。在经典计算中，在过去的几年里，在一个基本的算法问题上取得了突破性的成果--近似图分隔符。该项目研究了近似因子是否可以提高到$\sqrt{log n}$以上，运行时间是否可以提高到$\tilde{O}（n^{1.5}）$以上，以及这些新技术对METIS等实际算法性能的影响。最后，该项目研究了最近提出的Google 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.