Abstract

Holant problems are a frameworkfor computational counting problems defined on graphs. These problems areparametrised by sets of complex-valued functions of Boolean inputs. The holantframework is general enough to encompass many counting problems of interest.Simultaneously, it is specific enough to allow the derivation of dichotomyresults, partitioning all problems into those which are in FP and those whichare #P-hard. We show how important mathematical properties of constraintfunctions correspond to properties of interest in quantum information theoryand quantum computation. This allows us to draw on results and methods fromquantum theory to extend the (non-quantum) complexity classification of holantproblems.

Based onarXiv:1702.00767, arXiv:1704.05798, and arXiv:1811.00817. No knowledge ofquantum computing assumed.

Time

9月9日（星期一） 14:00--15:00

Speaker

Miriam Backens studied Physics at MurrayEdwards College, Cambridge for her undergraduate degree, followed by Part IIIMathematics. She then did a DPhil in quantum computing at the Department ofComputer Science, University of Oxford, supervised by Bob Coecke and SamsonAbramsky in the Quantum Group. Her thesis is Completeness and the ZX-calculus.

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

Her research focuses onalgorithms and computational complexity, as well as quantum computation and quantuminformation theory.

Venue

信息管理与工程学院602室

上海财经大学（第三教学楼西侧）

上海市杨浦区武东路100号