Time: 1:00pm Tuesday, 22nd March.

Location: SIT 459

Speaker: Youming Qiao, UTS

Title: Quantum matching problems

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:

(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.

### Like this:

Like Loading...

*Related*

## Discussion

## No comments yet.