April 25, 2014

July 27-31, 2009
Workshop on Quantum Marginals and Density Matrices

Abstracts - Invited Speakers

Variational Reduced Density Matrix Theory: Successes and Failures
Paul W. Ayers
Department of Chemistry; McMaster Univ.; Hamilton ON L8S 4M1
Coauthors: Dimitri Van Neck, Patrick Bultinck, Helen Van Aggelen, Brecht Verstichel

Because the molecular Hamiltonian contains only one-body and two-body operators, the two-electron reduced density matrix contains all the information needed to evaluate the energy, as well as most of the other properties of interest to chemists and molecular physicists. A straightforward minimization of the energy is confounded by the N-representability problem, which can only be addressed approximately. The resulting theory has both advantages and disadvantages compared to more traditional wavefunction-based approaches. The biggest advantage is that it performs well even when the molecule of interest has strong multireference character and the “Hartree-Fock plus correction” wavefunction paradigms fail. Also, as a lower-bound method, it provides a complementary tool to variational wavefunction approaches. The biggest disadvantages are the computational cost (which may yet be surmounted) and problems with dissociation and degeneracy that seem to afflict all approaches based on a “reduced” description of the system.


The reduced density matrix method and some complexity issues
Bastiaan Braams
Emory University

I will review the classical formalism of electronic structure theory that is based on the two-body reduced density matrix and associated representability conditions. The N-representability problem is unsolved and results from computational complexity theory indicate that it won't be solved in any concise form. I hope on the one hand to make clear that it doesn't matter, and on the other hand to outline the challenge of obtaining what could be called anyway a solution to the N-representability problem. Finally I will discuss the computational complexity of the Hartree-Fock problem. As an algebraic problem with general 2-body terms in the hamiltonian (not limited to Coulomb interaction) it is NP-hard, while in the setting of parameterized complexity theory, with the number of electrons as the parameter, it is W[1]-hard.



The DMRG and Correlator Product States
Garnet Kin-Lic Chan
Department of Chemistry and Chemical Biology, Cornell University, Ithaca NY14853-1301

I will describe applications of the DMRG to quantum chemistry. In addition, I will also talk about a new class of variational wavefunctions - the correlator product states - that generalise the DMRG in a practical way to encode higher dimensional correlations.


Estimating the spectrum of an operator - a technique for the analysis of spectral relations via representation theory
Matthias Christandl
Ludwig-Maximilians-Universität München

The optimal way of estimating the spectrum of an operator is by projection onto irreducible representations of the unitary group and symmetric group. Formulated in this form by Keyl and Werner, the mathematical content of spectrum estimation has been discovered independently and in many variations by mathematicians and physicists during the last decades.

In this talk, I will show how spectrum estimation can be applied in order to study relations among operators via representation theory (and vice versa). Examples are: 1) the study of Horn's problem (addition of Hermitian operators) via Littlewood-Richardson coefficients and 2) the study of the quantum marginal problem via the Kronecker coefficients of the symmetric group.

This is a joint work with Graeme Mitchison and Aram Harrow.



Simulating strongly correlated fermions
J. Eisert
University of Potsdam
Coauthors: C. Pineda, T. Barthel

We introduce a scheme for efficiently describing pure states of strongly correlated fermions in higher dimensions using unitary circuits. A local way of computing local expectation values is presented. We formulate a dynamical reordering scheme, corresponding to time-adaptive Jordan-Wigner transformation that avoids non-local string operators and only keeps suitably ordered the causal cone. Primitives of such a reordering scheme are highlighted. Fermionic unitary circuits can be contracted with the same complexity as in the spin case. The scheme gives rise to a variational description of fermionic models that does not suffer from a sign problem. We present a numerical example on a 27x27 fermionic lattice model to show the functioning of the approach. We also discuss the contraction complexity of general fermionic networks.


for related work see also


The Pauli exclusion principle and beyond
Alexander Klyachko
Bilkent University

The original Pauli exclusion principle claims that no quantum state can be occupied by more than one electron. This can be stated as inequality (y|r|y) = 1 on one-electron density matrix r. Nowadays the Pauli principle is replaced by skew symmetry of the multilelectron state. In this talk I review a recent solution of a longstanding problem about impact of this replacement on the electron density matrix. It goes far beyond the original Pauli principle and leads to numerous additional constraints. If time permits I will also discuss some physical implications.


Quantum marginal problem
Alexnder Klyachko
Bilkent University

Classical marginal problem is about existence of a body with given projections onto some coordinate subspaces. In the talk I primary address to a quantum version of this propblem about existence of a state of a multicomponent quantum system with given reduced density matrices. I will explain its reduction to Schubert calculus and its connection with representations of the symmetric group. Some applications to quantum information will be discussed.


N-representability is QMA-complete
Yi-Kai Liu
Coauthors: Matthias Christandl and Frank Verstraete

We study the computational complexity of the N-representability problem in quantum chemistry. We show that this problem is QMA-complete, which is the quantum generalization of NP-complete. Our proof uses a simple mapping from spin systems to fermionic systems, together with a convex optimization technique that reduces the problem of finding ground states to N-representability.

(This talk will include a short introduction to complexity theory and QMA-completeness.)


QMA-complete problems for stoquastic Hamiltonians and Markov matrices
Peter Love
Haverford College
Coauthors: Stephen Jordan

We show that finding the lowest eigenvalue of a 3-local symmetric stochastic matrix is QMA-complete. We also show that finding the highest energy of a stoquastic Hamiltonian is QMA-complete and that adiabatic quantum computation in the highest energy state and certain other excited states of a stoquastic Hamiltonian is universal. These results give a new QMA-complete problem arising in the classical setting of Markov chains, and new adiabatically universal Hamiltonians which arise in many physical systems.


de Finetti theorems for quantum states
Robert Koenig (Caltech) and Graeme Mitchison (University of Cambridge)
Institute for Quantum Information, Caltech, MC 305-16, Pasadena 91125, USA// DAMTP, University of Cambridge, Wilberforce Road, Cambridge CB3 0WA UK
Coauthors: (partly based on joint work with M. Christandl, R. Renner and M. Wolf)

We give an introduction to de Finetti theorems for quantum states. Such a theorem asserts that, given a symmetric state on a system composed of n subsystems, the state obtained by tracing out n-k of the subsystems can be represented approximately as a convex sum of product states. Furthermore, the precision of the approximation increases as k/n decreases, i.e. as a larger fraction of the subsystems are traced out. This can be proved using simple representation-theoretic ideas, which can also be extended to prove a number of interesting variants of the de Finetti theorem. Finally, we consider states that are both symmetric and unitarily invariant (symmetric Werner states). These give a rich supply of examples and have a close connection to the de Finetti theorem for probability distributions. They can also be used to establish limits on the closeness of approximation by product states, and therefore provide information about the tightness of de Finetti theorems.

joint work with Matthias Christandl and Renato Renner


Non-commutative polynomial optimization and the varianional RDM method
Stefano Pironio
Group of Applied Physics, University of Geneva
Coauthors: Artur Garcia, Miguel Navascues, Antonio Acin

A standard problem in optimization theory is to find the minimum of a polynomial function subject to polynomial inequality constraints. We introduce a generalization of this problem where the optimization variables are not real numbers, but non-commutative variables, i.e., operators acting on Hilbert spaces of arbitrary dimension. We show how semidefinite programming (SDP) can be used to solve this problem. Specifically, we introduce a sequence of SDP relaxations of the original problem, whose optima converge monotically to the global optimum.

Our method can find applications to compute the ground state energy of quantum many-body systems. In particular, it gives a new interpretation to and should strengthens the RDM method used in quantum chemistry to compute electronic energies. Our method provides a computation technique for many-body systems that is not based on states (and thus directly linked to entanglement) but that is rather based on the algebraic structure of quantum operators.


De Finetti and entropies
Renato Renner
ETH Zurich
Coauthors: Matthias Christandl, Graeme Mitchison, Robert Koenig

The estimation of the entropy of permutation invariant systems plays a crucial role in various information-theoretic applications, in particular in the context of quantum cryptography.

In this talk, I will review the connections between (generalized) entropies and de Finetti type theorems (including their quantum versions). In particular, I will show how de Finetti's theorem can be used to derive bounds on entropic quantities.


Density matrices in real-space renormalization group methods
Frank Verstraete
University of Vienna

We will discuss the role of density matrices in real-space renormalization group methods, and include detours via computational complexity and density functional theory.



Bosonic N-representability problem is also QMA-complete
Tzu-Chieh Wei
Institute for Quantum Computing, University of Waterloo
Coauthors: Michele Mosca and Ashwin Nayak

Computing the ground-state energy of interacting electron (fermion) problems has recently been shown to be hard for QMA, a quantum analogue of the complexity class NP. Fermionic problems are usually hard, a phenomenon widely attributed to the so-called sign problem occurring in Quantum Monte Carlo simulations. The corresponding bosonic problems are, according to conventional wisdom, tractable. Here, we discuss the complexity of interacting boson problems and show that they are also QMA-hard. In addition, we show that the bosonic version of the so-called N-representability problem is QMA-complete, as hard as its fermionic version. As a consequence, these problems are unlikely to have efficient quantum algorithms.


A new inequality for the von Neumann entropy
Andreas Winter
University of Bristol
Coauthors: Noah Linden, Ben Ibinson

This talk will be mainly based on a paper with N Linden. Pippenger has initiated the generalization of the programme to find all the "laws of information theory" to quantum entropy. The standard inequalities derive from strong subadditivity (SSA). SSA of the von Neumann entropy, proved in 1973 by Lieb and Ruskai, is a cornerstone of quantum coding theory. All other known inequalities for entropies of quantum systems may be derived from it. Here we prove a new inequality for the von Neumann entropy which we show is independent of strong subadditivity: it is an inequality which is true for any four party quantum state, provided that it satisfies three linear relations (constraints) on the entropies of certain reduced states. In the talk I will also discuss the possibility of finding an unconstrained inequality (work with N Linden and B Ibinson).


Bell inequalities and joint measurability - relating classical and quantum marginal problems
Michael M. Wolf
Niels Bohr Institute
Coauthors: David Perez-Garcia, Carlos Fernandez


Back to top