Quantum determinants in polynomial time

Igor Pak, Daniel Soskin

arXiv:2607.13186v1 Primary: math.QA Secondary: cs.DM, cs.DS, math.CO

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

Disclosure

“yavskyy, Vladimir Retakh and Avi Wigderson, for interesting discussions and helpful remarks. The ﬁrst author (IP) was partially supported by the NSF grant CCF-2302173. Use of AI. During the preparation of this manuscript, the authors used Claude (Anthropic, Claude Opus 4.8) to make numerous experiments in the combinatorics of words, in our search for the desired sign-reversing involution. We also used it to make ﬁgures and proof check the examples. Additionally, we used ChatGPT (O”
PDF page 24

Classification: Proof ideas or individual proof-step assistance
Multiplier: 8
Verified: 2026-08-23T18:53:52.602755Z

Structural counts

Pages 27 pdf

Theorems 4 source

Lemmas 18 source

Propositions 0 source

Corollaries 1 source

Definitions 3 source

Displayed equations 108 source

Bibliography entries 91 source

Appendix pages 0 estimated

Count notes

Source counts use the expanded primary TeX file main.tex.
Appendix pages include the first PDF page with an explicit Appendix heading through the final page.