Quantum Algorithms
Abstract
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 1/1000. We introduce a new technique for analyzing local Hamiltonians --- the detectability lemma. We show how to generalize the first step of Dinur's 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2013
- Accession Number
- ADA579025
Entities
People
- Umesh Vazirani
Organizations
- University of California, Berkeley