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

An efficient algorithm for finding Matrix Product ground states

Norbert Schuch, MPI Garching

joint work with J. Ignacio Cirac, Dorit Aharonov, Itai Arad, and Sandy Irani

The Density Matrix Renormalization Group (DMRG) algorithm, a variational method over the class of Matrix Product States (MPS), is the most successful algorithm for finding ground states of one-dimensional Hamiltonians. However, there is no converge proof for DMRG, and in fact hard instances can be constructed. In this talk, we describe an algorithm which efficiently solves the optimization problem encountered in DMRG, in a time which scales polynomially in the accuracy and the length of the chain, and exponentially in the so-called bond dimension. In practice, logarithmic bond dimensions often suffice for a good approximation of ground states, leading to a quasi-polynomial scaling. This scaling is optimal, since the problem is known to be NP-hard for a polynomial bond dimension.

joint talk given on the submissions:

Norbert Schuch and J. Ignacio Cirac
Matrix product state and mean field solutions for one-dimensional systems can be found efficiently

and

Dorit Aharonov, Itai Arad and Sandy Irani
Approximating 1D ground states of bounded bond dimension