13
$\begingroup$

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?

$\endgroup$
2

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.