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

The query complexity of Hamiltonian simulation and unitary implementation

Dominic W. Berry, Caltech

joint work with Andrew M. Childs

We present a general method for simulating a Hamiltonian given a black box for its matrix elements in a fixed basis. This method improves upon previous simulations of sparse Hamiltonians, but also applies to the non-sparse case. A major application is the implementation of black-box unitary transformations. We show how to implement a general N x N unitary transformation with bounded error using Õ(N^2/3) queries to a black box for its entries (ignoring logarithmic factors). In fact, except in pathological cases, it appears that the implementation can be performed with only Õ(N^1/2) queries, which is optimal.  In contrast, standard methods use Õ(N²) elementary operations.