Physics (Internal)

Solving Classical Computational Problems by Annealing a Planar Quantum Vertex Model

This event is part of the Preliminary Oral Exam.

Dissertation Committee: Claudio Chamon, Andrei Ruckenstein, Anatoli Polkovnikov, Ami Katz, Michael El-Batanouny

Abstract: We construct a planar vertex model that encodes the result of a universal reversible classical computation in its ground state. The approach involves Boolean variables (spins) placed on links of a two-dimensional lattice, with vertices representing logic gates. Large short-ranged interactions between at most two spins implement the operation of each gate. The lattice is anisotropic with one direction corresponding to ``computational'' time, and with transverse boundaries storing the computation's input and output. While we show that the model displays no finite temperature phase transitions, independent of circuit, the computational complexity is encoded in the scaling of the relaxation rate into the ground state with the system size. To explore faster relaxation routes, we construct an explicit mapping of the vertex model into the Chimera architecture of the D-Wave machine, initiating a novel approach to reversible classical computation based on state-of-the-art implementations of quantum annealing.