**Title:** Quantum matching problems

**Speaker:** Youming Qiao, UTS

**Time/Location:** 2-3pm, 16 March 2016 (Wed) / CB10.02.410, UTS

**Abstract:**We describe two algorithmic problems, both of which can be viewed as quantum analogues of the perfect matching problem on bipartite graphs. Given several square matrices, we are asked to:

The first problem is the well-known polynomial identity testing problem, for which a deterministic efficient solution implies a strong arithmetic circuit lower bound. The second problem has a rich history and has appeared in various forms in a remarkable number of mathematical and computational areas. For example, it is a key problem in the theory of arithmetic circuits with divisions, as recently studied by Hrubeš and Wigderson. After introducing these problems, we will present a couple of ingredients in a recent deterministic efficient algorithm for the second problem. These include a polynomial degree upper bound on generating the ring of matrix semi-invariants, and a linear algebraic analogue of the augmenting path technique.