pdf files of
Programme Booklet >>
and
Abstracts of all Talks >>

You will receive a hard copy of these files at the registration desk.

Sponsors

Pauli Center for Theoretical Studies

The Swiss National Science Foundation

ETH Zurich (Computer Science and Physics Department)

Quantum Science and Technology

CQT Singapore

QAP European Project

Sandia National Laboratories

Institute for Quantum Computing

id Quantique

Span programs and quantum algorithms

Ben Reichardt, University of Waterloo

We show that the general adversary lower bound on quantum query complexity is nearly tight, by giving a matching quantum walk algorithm. The result gives a new semi-definite program for quantum query complexity, and shows an equivalence to the span program model of computation. Span programs compose easily, and this yields a quantum recursion method. Classical algorithms cannot compose in this way. Applying the technique to solve problems defined recursively with independent inputs, i.e., to evaluating formulas, gives an optimal quantum formula-evaluation algorithm. Span programs are a promising model for developing more quantum algorithms.