Quantum Algorithms

We report new directions in which to generalize the success of quantum algorithms. The first gives exponential speedups over classical algorithms for detecting non-linear structures. The algorithm draws its inspiration from optics, where light can be highly focussed when reflected from a conic surface. The second gives a span program based quantum algorithm that achieves quadratic speedup for the evaluation of boolean formulae. The third gives an exponential speedup over classical algorithms for additive approximation to the Tutte polynomial evaluated at certain roots of unity. This leads to an additive approximation of partition functions of statistical mechanics models including the Potts model. We also report new breakthroughs in fault tolerant quantum computation, based on error detecting codes. And we give an analysis of a Knill type scheme for fault tolerance with a rigorously proved noise threshold of 11000. We introduce a new technique for analyzing local Hamiltonians --- the detectability lemma. We show how to generalize the first step of Dinurs proof of the classical PCP theorem, gap amplification, to the quantum case. Whether or not the quantum PCP theorem is true is a central open question in Hamiltonian complexity.