you're reading...

SACT Seminar: Quantum matching problems

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.



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: