SAMOP 2023 – scientific programme

Parts | Days | Selection | Search | Updates | Downloads | Help

QI: Fachverband Quanteninformation

QI 13: Quantum Simulation

QI 13.1: Talk

Tuesday, March 7, 2023, 11:00–11:15, F428

Quantum simulation of graph complexity problems — •Durga Dasari and Joerg Wrachtrup — 3. Physics Institute, ZAQUANT, University of Stuttgart, 70569,Stuttgart, Germany

Finding the perfect matchings that cover the entire graph is known to be a computationally hard (#P) problem in graph theory. A similar analogy exists for spin-lattices, where the coverings of lattice by dimers is a hard combinatorial problem. Dimer models are well studied in statistical physics and in many-body physics. We show here how to simulate such computationally complex problems using a simple model system comprising of a single quantum probe interacting with a rectangular spin-lattice. We identify different configurations for complete lattice filling using dimers through the quantum probe coherence, and use it further to obtain the pairing statistics, that confirm the previously known results for planar graphs. We highlight here the new role of quantum sensor that allows it to go beyond its conventional sensing applications towards resolving computational complexity in graph theory.