2019-09-09 | Miriam Backens:Holant problems and quantum information theory



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.



99日(星期一)  14:00--15:00



Miriam Backens studied Physics at Murray Edwards College, Cambridge for her undergraduate degree, followed by Part III Mathematics. She then did a DPhil in quantum computing at the Department of Computer Science, University of Oxford, supervised by Bob Coecke and Samson Abramsky in the Quantum Group. Her thesis is Completeness and the ZX-calculus.

Subsequently, She spent two years as a postdoc with Ashley Montanaro at the School of Mathematics, University of Bristol. In 2017, She returned to Oxford as a postdoc with Leslie Ann Goldberg in the Theory and Algorithms group. As of 2019, she is a Career Development Fellow in Computer Science at Balliol College.

Her research focuses on algorithms and computational complexity, as well as quantum computation and quantum information theory.