InterJournal Complex Systems, 82
Status: Accepted
Manuscript Number: [82]
Submission Date: 963011
Permanent uncertainty: On the quantum evaluation of the determinant and the permanent of a matrix
Author(s): Lidror Troyansky , Naftali Tishby

Subject(s): CX.09

Category: Brief Article


We investigate the possibility of evaluating permanents and determinants of matrices by quantum computation. All current algorithms for the evaluation of the permanent of a real matrix have exponential time complexity and are known to be in the class $P^{#P}$. Any method to evaluate or approximate the permanent is thus of fundamental interest to complexity theory. Permanents and determinants of matrices play a basic role in quantum statistical mechanics of identical bosons and fermions, as the only possible many particle states made of single particle wave functions. We study a novel many-particle quantum-computational model in which an observable operator can be constructed, in polynomial-time complexity, to yield the determinant or the permanent of an arbitrary matrix as its expectation value. Both quantities are estimated, in this model, by quantum mechanics systems in a polynomial time, using fermions and bosons respectively. It turns out that the {em variance} of the measurements in a "noise-free case" is zero for the determinant and exponential (in the rank of the matrix) for the permanent. The intrinsic measurement variance is therefore the quantum mechanical correspondence to the computational complexity gap.

Retrieve Manuscript
Submit referee report/comment

Public Comments: