Quantum determinants in polynomial time
arXiv:2607.13186
The paper presents a polynomial‑size algebraic branching program that efficiently computes the Cayley determinant for right quantum matrices and its q‑generalizations, using combinatorial bijections and the Mahajan‑Vinay determinant construction.
Abstract
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 -Cayley determinant of -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.
27 pages