|Current Workshop | Overview||Back | Home | Search ||
Computational Complexity of Quantum Hamiltonian Systems
spectra and entanglement entropies
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
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
This talk will be concerned with a novel approach to the classical simulation of ground
state properties of quantum many-body systems . 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  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 ? 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.
 C.M. Dawson, J. Eisert, and T.J. Osborne, arXiv:0705.3456.
 J. Eisert, Phys. Rev. Lett. 97 (2006).
 D. Gross and J. Eisert, Phys. Rev. Lett. 98 (2007).
Locality in Quantum Dynamics and Applications
We will review recent work on the dynamics of quantum spin systems. In particular, we
will focus on new techniques, primarily initiated
as expressed by Lieb-Robinson Bounds.
Simulating Quantum Correlations with Finite Communication
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
consider the following combinatorial problem. We are given three
1-Dimensional spin chains are hard
Daniel Gottesman, Perimeter Institute,
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.
algorithm for the Hamiltonian NAND tree
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
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,
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 |
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,
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.
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 , 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.
 M. Cramer, J. Eisert, M.B. Plenio, Phys. Rev. Lett. 98 (2007).
 M. Plenio, J. Eisert, M. Cramer, J. Dreissig, Phys. Rev. Lett.
 M. Cramer, J. Eisert, M.B. Plenio, J. Dreissig, Phys. Rev. A 73
 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
 M. Cramer, C.M. Dawson, J. Eisert, T.J. Osborne, cond-mat/0703314.
Wolfgang Duer, IQOQI,
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.
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 ﬁnd 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
2. Institut fuer Theoretische Physik, Universitat Innsbruck, Technikerstrasse 25, A-6020 Innsbruck, Austria.
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.
 Work in progress.