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

2019-09-09   

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

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

 

Speaker

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.

 

Venue

信息管理与工程学院602

上海财经大学(第三教学楼西侧)

上海市杨浦区武东路100