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.

  • $\begingroup$ Quantum data compression can allow one to have 3 qubits to be compressed to 2 qubits. Even so, due to the error rates, these quantum error data compression schemes unreliable. The error in such data compression make it unreliable as a data compression scheme as quantum data compression does not do a frequency count of 0's and 1's, but current quantum data compression measure oneness, or zeroness, of a qubit. So, if a quantum computer would be used to compress a matrix- it would compress with a high error. Scaling the quantum data compression is still not feasible currently. $\endgroup$ Feb 22, 2016 at 4:38
  • $\begingroup$ I'm asking about quantum algorithms for computing analogs of the determent. I used the word "compress" to fallaciously to refer to homomorphic properties of some analogs of the determent. A determent is an invariant of a matrix though, not a way to compress a matrix. $\endgroup$ Feb 22, 2016 at 12:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.