University of Cambridge > > Isaac Newton Institute Seminar Series > A constructive algorithm for the commutative Quantum Lovsz Local Lemma

A constructive algorithm for the commutative Quantum Lovsz Local Lemma

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Mustapha Amrani.

Mathematical Challenges in Quantum Information

Co-authors: Martin Schwarz (University of Vienna), Frank Verstraete (University of Vienna)

The recently proven Quantum Lovsz Local Lemma generalises the well-known Lovsz Local Lemma. It states that, if a collection of subspace constraints are “weakly dependent”, there necessarily exists a state satisfying all constraints. It implies e.g. that certain instances of the quantum kQSAT satisfiability problem are necessarily satisfiable, or that many-body systems with “not too many” interactions are never frustrated.

However, the QLLL only asserts existence; it says nothing about how to find the quantum state that satisfies the constraints. Inspired by Moser’s breakthrough classical results, we present a constructive version of the QLLL in the setting of commuting constraints, proving that a simple quantum algorithm converges efficiently to the sought quantum state. As well as proving a constructive commutative QLLL , this provides a non-trivial poly-time example of a new type of “dissipative quantum algorithm”.

This talk is part of the Isaac Newton Institute Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2017, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity