The Fast Algorithm For Evaluating Permanents And Its Applications

The permanent of a square matrix is a function of the matrix similar to the determinant.It is considered a#P-Complete problem and it is more difficult than NP problem.This paper mainly has studied the compute methods of the permanent and proposed a new algorithm to compute the permanent.The mainly works of this paper is as follows.Proposed a new algorithm for calculating the permanent and analyzed the time complexity of the new algorithm.This algorithm can make efficient use of computer storage resources and speed up the computation with the idea of“space for time”.In terms of time complexity,the new algorithm Store-zehcin needs n2^n-1-n multiplication calculations and n2^n-1-2ⁿ+1 addition calculations when the order of the matrix is n,while the the Ryser algorithm needs(2ⁿ-1)(n-1)multiplication calculations and(n+1)(2ⁿ-n)-2 addition calculations and the R-NW algorithm needs n2^n-1+n+2 multiplication calculations and(n+1)2^n-1+n²-n-1 addition calculations.The result shows that the Store-zechin algorithm can indeed compute the permanent in fewer steps.Discussed the availability of the algorithm.This paper compared the execution time of Ryser and Store-zechin algorithm on“Tianhe II”computer.The result shows that when the matrix order is 50,Store-zechin can reduce the time by 0.5378 seconds.In fact,for supremacy,we think it not only needs to distinguish between specific issues,but also needs to distinguish between specific applications.On the battlefield,even if the quantum computer has only a few seconds of advantages,it is also an impossible task for traditional computers,while in diplomacy or commerce,a quantum must have advantages over days,years or even decades to complete quantum supremacy.So the 0.5378 seconds also has its practical significance.Explained that algorithm can be used to measure the degree of realization of supremacy on the boson-sampling.Permanent has actually been used in the field of quantum simulation computing,and it is mainly active on the boson-sampling problem.This paper compared the time of calculating the permanent on a top boson-sampling and a top supercomputer.The result shows that current boson-sampling machine cannot match the top supercomputers and the realization of quantum supremacy of this field is just a goal.