The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

MQI

Seminar

A constructive algorithm for the commutative Quantum Lovász Local Lemma

Cubitt, T (University of Cambridge)
Thursday 28 November 2013, 15:00-16:00

Seminar Room 1, Newton Institute

Abstract

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

The recently proven Quantum Lovász Local Lemma generalises the well-known Lovász 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".

Presentation

[ppt ]

Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧