<p>There are a wide variety of determent-like constructions.  Some like the <a href="https://en.wikipedia.org/wiki/Computing_the_permanent" rel="nofollow">permanent</a> or immanents are variations on the ordinary determinant for matrices over fields or commutative rings. Some like <a href="https://en.wikipedia.org/wiki/Quasideterminant" rel="nofollow">quasideterminants</a> extend the theory of determinants to non-commutative rings.</p>

<p>At least permanents have a <a href="https://cstheory.stackexchange.com/questions/16471/lower-bound-for-determinant-and-permanent">rich</a> complexity theory, perhaps the others do to. </p>

<p>For any of these constructions, is there a quantum algorithm that asymptotically out preforms the fastest classical algorithms for computing it?</p>

<p>I'm asking because some post-quantum crypto systems like <a href="http://arxiv.org/abs/1407.1270" rel="nofollow">http://arxiv.org/abs/1407.1270</a> 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. </p>

CC BY-SA 3.0
2016-02-22T04:38:22.730Z
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
CC BY-SA 3.0
2016-02-22T12:14:54.190Z
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
<quantum-computing><cr.crypto-security><permanent>
Quantum algorithms for generalizations of determinants
Jeff Burdges
# Quantum algorithms for generalizations of determinants

(Asked by: username_0 on 2016-02-20)

There are a wide variety of determent-like constructions. Some like the [permanent](https://en.wikipedia.org/wiki/Computing_the_permanent) or immanents are variations on the ordinary determinant for matrices over fields or commutative rings. Some like [quasideterminants](https://en.wikipedia.org/wiki/Quasideterminant) extend the theory of determinants to non-commutative rings.

At least permanents have a [rich](https://cstheory.stackexchange.com/questions/16471/lower-bound-for-determinant-and-permanent) 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.

**Tags:** quantum-computing, cr.crypto-security, permanent

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  

---

## 0 answers

