1

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.

Jeff Burdges
  • 1,216
  • 6
  • 11
  • 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. – user3483902 Feb 22 '16 at 04:38
  • 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. – Jeff Burdges Feb 22 '16 at 12:14

0 Answers0