Holant problems and quantum information theory (Miriam Backens)

Abstract

Holant problems are a framework for computational counting problems defined on graphs. These problems are parametrised by sets of complex-valued functions of Boolean inputs. The holant framework is general enough to encompass many counting problems of interest. Simultaneously, it is specific enough to allow the derivation of dichotomy results, partitioning all problems into those which are in FP and those which are #P-hard. We show how important mathematical properties of constraint functions correspond to properties of interest in quantum information theory and quantum computation. This allows us to draw on results and methods from quantum theory to extend the (non-quantum) complexity classification of holant problems.
Based on arXiv:1702.00767, arXiv:1704.05798, and arXiv:1811.00817. No knowledge of quantum computing assumed.

Time

2019-09-09   14:00 ~ 15:00   

Speaker

Miriam BackensUniversity of Oxford

Room

Room 602, School of Information Management & Engineering, Shanghai University of Finance & Economics