Fundamental Problems in Classical and Quantum Algorithms

经典和量子计算中的基本问题。摘要：要实现量子计算机的巨大计算能力，必须解决许多算法问题。本项目主要研究两个问题。首先是寻找量子计算机的进一步应用，而不仅仅是破解密码系统。即寻找比经典算法提供指数加速比的量子算法。二是容错量子计算的高效实现。这是迈向量子计算实际实验实现的关键一步。研究人员还研究了不受量子密码分析影响的经典密码系统的设计。在经典计算中，在过去几年中，在一个基本的算法问题上-近似图分离器--取得了突破性的结果。这个项目既研究了近似因子是否可以改进到超过$\sqrt{logn}$，运行时间是否可以改进到$tide{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.