Search Talks

Alongside the effort underway to build quantum computers, it is important to better understand which classes of problems they will find easy and which others even they will find intractable. Inspired by the success of the statistical study of classical constraint optimization problems, we study random ensembles of the QMA$_1$-complete quantum satisfiability (QSAT) problem introduced by Bravyi. QSAT appropriately generalizes the NP-complete classical satisfiability (SAT) problem. We show that, as the density of clauses/projectors is varied, the ensembles exhibit quantum phase transitions between phases that are product satisfiable, entangled satisfiable and unsatisfiable. Remarkably, almost all instances of QSAT for a fixed interaction graph exhibit the same dimension of the satisfying manifold. This establishes the generic QSAT decision problem as equivalent to a purely graph theoretic property and that the hardest typical instances are likely to be localized in a bounded range of clause density. Based on papers: C.R. Laumann, R. Moessner, A. Scardicchio, and S.L. Sondhi. Phase transitions and random quantum satisfiability. QIC 10 (1/2), (2009). arXiv:0903.1904 C.R. Laumann, A.M. Lauchli, R. Moessner, A. Scardicchio, and S.L. Sondhi. On product, generic and random generic quantum satisfiability. arXiv:0910.2058

In quantum field theory it is possible to create negative local energy densities. This would violate the Generalized Second Law (GSL) unless there is some sort of energy condition requiring the negative energy to be counterbalanced by positive energy. TO explore what this energy condition is, I will assume that the GSL holds in semiclassical gravity for all future causal horizons. From CPT symmetry it follows that the time-reverse of the GSL, properly understood, holds for all past causal horizons. These two conditions together then imply that the Averaged Null Energy Condition (ANEC) holds on any null line, i.e. a complete achronal lightlike null geodesic. In curved spacetimes, the ANEC can be violated on general geodesics. But even if the ANEC only holds on null lines, theorems by Sorkin, Penrose and Woolgar, and by Graham and Olum imply that semiclassical gravity should satisfy positivity of energy, topological censorship, and should not admit closed timelike curves. These results can thus be seen as consequences of the GSL. However, these theorems don't apply when gravitational fluctuations are taken into account. In that case, the GSL argument suggests a modification to the ANEC which may make these theorems applicable to perturbative quantum gravity.

The scaling analysis in the large spin limit of Feynman amplitudes for the Bosonic colored group field theory are considered in any dimension starting with dimension 4. By an explicit integration of two colors, we show that the model is positive. This formulation could be useful for the constructive analysis of this type of models.