There are a wide variety of determent-like constructions. Some like the permanent or immanents are variations on the ordinary determinant for matrices over fields or commutative rings. Some like quasideterminants extend the theory of determinants to non-commutative rings.
At least permanents have a rich complexity theory, perhaps the others do to.
For any of these constructions, is there a quantum algorithm that asymptotically out preforms the fastest classical algorithms for computing it?
I'm asking because some post-quantum crypto systems like http://arxiv.org/abs/1407.1270 and code-based crypto suffer from extremely large key sizes due to representing public keys as matrices. A priori, it might be possible to "compress" that large matrix into something like a characteristic polynomial but using some non-commutative analog of the determinant. This approach sounds less viable if quantum computers could compute some analogs of the determinant more quickly.