Lorentz Center - Computational Complexity of Quantum Hamiltonian Systems from 23 Jul 2007 through 27 Jul 2007
  Current Workshop  |   Overview   Back  |   Home   |   Search   |     

    Computational Complexity of Quantum Hamiltonian Systems
    from 23 Jul 2007 through 27 Jul 2007

Density-matrix spectra and entanglement entropies



Density-matrix spectra and entanglement entropies

Ingo Peschel
Fachbereich Physik, Freie Universität Berlin

The complexity of quantum states can be seen in the spectra of the reduced density

matrices which arise upon dividing the system into two parts.  In the talk, a brief review

of these density-matrices, their spectra and the methods of calculation will be given for

solvable many-particle systems. The resulting entanglement entropies and implications

for the DMRG method will also be discussed.



Polynomial-time algorithm for simulation of weakly-interacting quantum spin systems
Sergey Bravyi
IBM Watson Research Center, Yorktown Heights, USA
We describe an algorithm that computes the ground state energy and correlation
functions for 2-local Hamiltonians in which interactions between qubits are  weak
compared to single-qubit terms. The running time of the algorithm is polynomial in the
number of qubits and the required precision. Specifically, we consider Hamiltonians of
the form H=H(0)+epsilon V, where H(0) describes non-interacting qubits, V is a
perturbation that involves arbitrary two-qubit interactions on a graph of bounded degree,
and epsilon is a small parameter. The algorithm works if the absolute value of epsilon is 
below a certain threshold value that depends only upon the spectral gap of H(0), the 
maximal degree of the graph, and the maximal norm of the two-qubit interactions in V. 
The main technical ingredient of the algorithm is generalized Kirkwood-Thomas ansatz 
for the ground state. The parameters of the ansatz are computed using perturbative 
expansions in powers of epsilon. Our algorithm is closely related to the coupled cluster 
method used in the quantum chemistry.



Classical simulation of and quantum computation with quantum many-body systems
Jens Eisert, Imperial College London, United Kingdom

This talk will be concerned with a novel approach to the classical simulation of ground
state properties of quantum many-body systems [1]. We will introduce a unified
formulation of variational methods for simulating ground state properties of quantum
many-body systems. The key feature is a novel variational method over quantum circuits
via infinitesimal unitary transformations, inspired by flow equation methods. This gives
rise to a unifying picture of several existing variational techniques for simulating strongly
correlated systems: variational classes are represented as efficiently contractible unitary
networks, including, the matrix-product states of density matrix renormalization (DMRG),
multiscale entanglement renormalization (MERA) states, weighted graph states,
quantum cellular automata, and others. In particular, this provides a tool for varying over
classes of states, such as MERA, for which so far no efficient way of variation is known,
including two-dimensional systems.  We will discuss several examples. The issue of the
classical complexity [2] will be touched.
In the second part of the talk, we will look at a converse question with similar methods
Acknowledging that one cannot classically efficiently keep track of many-body states
under measurement, we explore whether we could make a virtue of necessity, and ask
What states then serve as resource states for measurement-based quantum
computation [3]? We find that a large class of new such states can
be found, and will systematically explore how many properties can eventually be
relaxed, while retaining a model for quantum computation. Such ideas might be helpful
in tailoring quantum computer models to actual physical architectures.
[1] C.M. Dawson, J. Eisert, and T.J. Osborne, arXiv:0705.3456.
[2] J. Eisert, Phys. Rev. Lett. 97 (2006).
[3] D. Gross and J. Eisert, Phys. Rev. Lett. 98 (2007).



Locality in Quantum Dynamics and Applications


Bruno Nachtergaele, University of California, Davis, USA


We will review recent work on the dynamics of quantum spin systems. In particular, we

will focus on new techniques, primarily initiated by Hastings, that apply locality properties

as expressed by Lieb-Robinson Bounds.



Simulating Quantum Correlations with Finite Communication


Oded Regev, Tel Aviv University, Dept. of Computer Science, Tel Aviv, Israel


Assume Alice and Bob share some bipartite $d$-dimensional quantum state. As is well

known, by performing two-outcome measurements, Alice and Bob can produce

correlations that cannot be obtained classically. We show that by using only two bits of

communication, Alice and Bob can classically simulate any such correlations.

All previous protocols for exact simulation required the communication to grow to infinity

with the dimension $d$.  Our protocol and analysis are based on a power series method,

resembling Krivine's bound on Grothendieck's constant, and on the computation of

volumes of spherical tetrahedra.



A PromiseBQP-complete String Rewriting Problem

Pavel Wocjan, School of EE & CS, University of Central Florida, Orlando, USA


We consider the following combinatorial problem.  We are given three
strings s, t, and t' of length L over some fixed finite alphabet
and an integer m that is polylogarithmic in L.  We have a symmetric
relation on substrings of constant length that specifies which
substrings are allowed to be replaced with each other.  Let Delta(n)
denote the difference between the numbers of possibilities to obtain t
from s and t' from s after n replacements. The problem is
to determine the sign of Delta(m).

As promises we have a gap condition and a growth condition.  The former
states that |Delta (m)| >= epsilon c^m where epsilon is
inverse polylogarithmic in L and c>0 is a constant.  The latter is
given by Delta(n) <= c^n for all n.

We show that this problem is PromiseBQP-complete, i.e., it represents
the class of problems which can be solved efficiently on a quantum

This talk is based on the paper http://arxiv.org/abs/0705.1180 by Dominik Janzing and me.

1-Dimensional spin chains are hard
Daniel Gottesman, Perimeter Institute, Waterloo, Ontario, Canada
Kitaev defined a complexity class QMA ("Quantum Merlin-Arthur"), which is essentially
the quantum version of the class NP: QMA is, roughly speaking, the set of problems
where the answer may be difficult to find, but is easy to check on a quantum computer.
As with NP, QMA has complete problems; if you can solve a QMA-complete problem, 
you can solve any problem in QMA.  In particular, Kitaev showed that the 5-local 
Hamiltonian problem, which asks for the ground state energy of a Hamiltonian 
interacting up to 5 qubits in a term, is QMA-complete.  A series of later results improved
this to show that finding the ground state energy remains QMA-complete even for a 
Hamiltonian only interacting nearest-neighbor qubits in a 2-dimensional lattice.  In this
talk, I will sketch a proof that nearest-neighbor interactions in a line are sufficient.  The 
individual particles are not qubits now, but 12-state systems.  This result implies that 
there can exist 1-dimensional systems that cannot relax to their own ground states in a
reasonable amount of time.



A Quantum algorithm for the Hamiltonian NAND tree

Eddie Farhi, Center for Theoretical Physics, MIT, Cambridge, MA, USA

I will discuss the recent result of Goldstone, Gutmann and myself in which we give a

quantum algorithm for the balanced binary NAND tree problem in the Hamiltonian oracle

model. The algorithm uses a continuous time quantum walk with a run time proportional

to sqrt(N).  We also show a lower bound of sqrt(N) for the NAND tree problem in this

Hamiltonian oracle setting.



Perturbation Theory Gadgets and Reductions in QMA


Julia Kempe, Tel Aviv University, Israel

Most physical systems are described by a sum of local Hamiltonians, i.e. Hamiltonians

that act on a few particles each. Computing the ground state energy of these systems is

notoriously hard in general and has been studied in many settings, like for instance on

square lattices. Kitaev was the first to cast the problem in complexity theoretic terms in

connection with quantum computing: he showed that the 5-Local Hamiltonian problem is

as hard as any problem in QMA, the quantum analogue of the complexity class NP. We

will review  this connection and describe some gadget constructions to reduce locality of

Hamiltonians in this setting, using some rigorous perturbation theory techniques on the

way.  We will also briefly review the connection to adiabatic quantum computing.



Information propagation and classical simulation of disordered quantum systems
Tobias Osborne, Royal Holloway, University of London, Dept. of Mathematics, Engham, UK
It has become clear that there is an intimate link between the propagation of information
through interacting quantum systems and the computational cost of simulating their
dynamics: the faster that information can propagate through a low-dimensional quantum 
spin system the harder it is, in the worst case, to simulate its dynamics. I'll describe this
connection and show that if information propagates at an effective "speed of light" then
this means one can simulate the dynamics efficiently as long as |t| < c log(system
diameter), where c is a constant. This is the best one can hope for, in general. There is a
situation, however, where better results exist, namely, for systems with disorder. I'll
describe settings where the presence of disorder suppresses information propagation,
and hence substantially simplifies the task of simulation.
An Area Law for One Dimensional Quantum Systems
Matthew Hastings, Los Alamos National Laboratory, Los Alamos, NM, USA
The ground states of quantum systems with local interactions and an excitation gap
represent a very special class of states.  For one thing, the correlations in these systems 
are known to decay exponentially in space.  In this talk, I will consider the entanglement 
in these systems, and prove an area law in one dimension, showing a bound on the 
entanglement entropy of a region which is independent of the size of the region.  Using
other properties of these systems, I will then relate the Von Neumann entropy to the 
Renyi entropy and to the ability to approximate the ground state by a matrix product 
state.  Finally, I will discuss the implications of this result, as well as other conjectured
area laws, for simulation of these systems on classical computers.

Jens Eisert, Imperial College London, United Kingdom


Poster 1: Area laws in critical bosonic and fermionic systems
The entanglement entropy of a distinguished region of a quantum many-body system
reflects the entanglement present in its pure ground state. In this work [1], we establish
scaling laws for this entanglement for critical quasi-free fermionic and bosonic lattice
systems, without resorting to numerical means [2,3]. We consider the geometrical setting
of D-dimensional half-spaces. Intriguingly, we find a difference in the scaling properties
depending on whether the system is bosonic - where an area-law is first proven to hold –
or fermionic, extending previous findings for cubic regions. For bosonic systems with
nearest neighbor interaction we prove the conjectured area-law by computing the
logarithmic negativity analytically. We identify a length scale associated with
entanglement, different from the correlation length. For fermions we determine the 
logarithmic correction to the area-law, which depend on the topology of the Fermi 
surface. We find that Lifshitz quantum phase transitions are accompanied with a non-
analyticity in the prefactor of the leading order term.
[1] M. Cramer, J. Eisert, M.B. Plenio, Phys. Rev. Lett. 98 (2007).
[2] M. Plenio, J. Eisert, M. Cramer, J. Dreissig, Phys. Rev. Lett. 
94 (2005).
[3] M. Cramer, J. Eisert, M.B. Plenio, J. Dreissig, Phys. Rev. A 73 
[4] M.M. Wolf, Phys. Rev. Lett. 96 (2006).
Poster 2: Quenching, local relaxation, and a central limit theorem for
non-equilibrium quantum lattice systems
A reasonable physical intuition in the study of interacting quantum systems says that, 
independent of the initial state, the system will tend to equilibrate. In this work we study a 
setting where relaxation to a steady state is exact, namely for the Bose-Hubbard
model where the system is quenched from a Mott quantum phase to the strong
superfluid regime. We find that the evolving state locally relaxes to a steady state with 
maximum entropy constrained by second moments, maximizing the entanglement, to a 
state which is different from the thermal state of the new Hamiltonian. Remarkably, in the
infinite system limit this relaxation is true for all large times, and no time average is 
necessary. For large but finite system size we give a time interval for which the system 
locally "looks relaxed"  up to a prescribed error. Our argument includes a central limit
theorem for harmonic systems and exploits the finite speed of sound.  
Additionally, we show that for all periodic initial configurations, reminiscent of charge 
density waves, the system relaxes locally. We sketch experimentally accessible
signatures in optical lattices as well as implications for the foundations of quantum
statistical mechanics.
[1] M. Cramer, C.M. Dawson, J. Eisert, T.J. Osborne, cond-mat/0703314.
Wolfgang Duer, IQOQI, Innsbruck, Austria
Classical spin models and the quantum stabilizer formalism
We introduce a connection of a large class of classical statistical mechanical models on
arbitrary graphs -including Ising and Potts model with magnetic fields as special 
instances- to quantum information theory. We show how to express the partition function
Z_G of such models as overlaps between stabilizer (or graph) states that encode the
interaction pattern and complete product states that specify the interaction strengthes 
and temperature. We utilize this connection in both directions. For instance, we obtain 
new classical algorithms to calculate Z_G and to establish general symmetry- and
high-low temperature duality relations. We also show that techniques and results 
established in classical statistical mechanics (e.g. the transfer matrix method and 
efficient classical simulation techniques) can be utilized in measurement-based quantum 
computation, e.g. to obtain new ways of classically simulating measurement-based-
quantum computations on certain resource states.


Artur Garcia-Saez, ICFO-The Institute of Photonic Sciences, Castelldefels (Barcelona), Spain


Thermal bound entanglement in macroscopic systems and the area law

Does bound entanglement naturally appear in quantum many-body systems? We

address this question by showing the existence of bound-entangled thermal states for

harmonic oscillator systems consisting of an arbitrary number of particles. By explicit

calculations of the negativity for different partitions, we find a range of temperatures for

which no entanglement can be distilled by means of local operations, despite the system

being globally entangled. We offer an interpretation of this result in terms of the

entanglement area law, typical of these systems. Finally, we discuss generalizations

of this result to other systems, including spin chains.



H.J. Briegel1, 2, W. Duer1, 2, B. Kraus1, 2, M. van den Nest1, E. Rico2

1.Institute of Quantum Optics and Quantum Information of the Austrian Academy of Science, A-6020 Innsbruck, Austria.

2. Institut fuer Theoretische Physik, Universitat Innsbruck, Technikerstrasse 25, A-6020 Innsbruck, Austria.


Valence Bond States and Links Models


An antiferromagnet spin-1 model is characterized on a 2D lattice with the following


1) The Hamiltonian is made out of nearest neighbor interactions.

2) It is homogeneous, translational and rotational invariant.

3) The ground state is a real singlet state of SU(2) (non-chiral).

4) It has a local spin-1 representation.

[1] Work in progress.