Joonsuk Huh uploaded a paper "A fast quantum algorithm for computing matrix permanent " on arxiv, which claims a polynomial-time algorithm approximating the permanent of an arbitrary matrix with multiplicative and additive errors.

Given the $\#P$-hardness result of approximating permanent, the result implies striking complexity consequences, such as $P^{\#P} \subset BQP$ and $BPP \neq BQP$ (assuming $PH$ does not collapse), as the paper explicitly states.

I skimmed the first few pages and found some interesting lines, e.g., the Glynn-Kan formula (Eqn. (6), named by the author), but unable to follow all details.

I am wondering if the status or discussions of this paper. Is there any discussion on this paper, or does anyone verify the results?



Your Answer

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

Browse other questions tagged or ask your own question.