##### Department of Mathematics,

University of California San Diego

****************************

### Quantum Information and Computation Seminar

## Zeph Landau

#### University of California, Berkeley

## The detectability lemma: making sense of the notion of quantum constraint satisfaction

##### Abstract:

The quantum analogue of a constraint satisfaction problem is a sum of local Hamiltonians---each local Hamiltonian specifies a local constraint whose violation contributes to the energy of the given quantum state. Formalizing the intuitive connection between the ground (minimal) energy of the Hamiltonian and the minimum number of violated constraints is problematic, since the number of constraints being violated is not well defined when the terms in the Hamiltonian do not commute. This presentation will indicate how to make this connection and explain the relationship to the quest for a quantum PCP result.

Host: Jamie Pommersheim

### February 22, 2010

### 1:00 PM

### AP&M 6402

****************************