Quantum determinants in polynomial time

We give an algebraic branching program of polynomial size which computes Cayley determinant of right quantum matrices.

This is a rare example of an efficient computation of a noncommutative determinant, and the first such example for quantum groups.

We extend the results to the $q$-Cayley determinant of $q$-right quantum matrices, as well as to their multiparameter generalization.

The proofs are entirely combinatorial, as we relate Cayley, Moore and Valiant determinants using bijections/involutions on words.

We then employ the celebrated determinant construction of Mahajan and Vinay (SODA'97), to obtain the results.