Time: 1:00pm Tuesday, 22nd March.
Location: SIT 459
Speaker: Youming Qiao, UTS
Title: Quantum matching problems
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:
(1) decide if there is a full-rank matrix in the linear span of them;
(2) decide if there is a shrunk subspace. That is a subspace U, s.t. the union of the images under these matrices is of smaller dimension than U.
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 our 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.
Based on joint works with Gábor Ivanyos and K. V. Subrahmanyam, arXiv:1508.00690 and arXiv:1512.03531. Another recent paper on this topic is arxiv:1511.03730.