Abstract: We describe two algorithmic problems, both of which can be viewed as quantum analogues of the perfect matching problems 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 symbolic determinant identity test problem, for which a deterministic efficient solution implies circuit lower bounds. The second problem has found several applications in arithmetic circuit complexity. After introducing several formulations of these problems, we will briefly overview some recent progress on these problems. Based on joint works with Gábor Ivanyos and K. V. Subrahmanyam, arXiv:1508.00690 and arXiv:1508.01554.

Date: 28 October 2015