<p>Joonsuk Huh uploaded a paper &quot;<a href="https://arxiv.org/abs/2205.01328" rel="noreferrer">A fast quantum algorithm for computing matrix permanent</a>
&quot; on arxiv, which claims a polynomial-time algorithm approximating the permanent of an arbitrary matrix with multiplicative and additive errors.</p>
<p>Given the <span class="math-container">$\#P$</span>-hardness result of approximating permanent, the result implies striking complexity consequences, such as <span class="math-container">$P^{\#P} \subset BQP$</span> and <span class="math-container">$BPP \neq BQP$</span> (assuming <span class="math-container">$PH$</span> does not collapse), as the paper explicitly states.</p>
<p>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.</p>
<p>I am wondering if the status or discussions of this paper. Is there any discussion on this paper, or does anyone verify the results?</p>

CC BY-SA 4.0
2022-05-08T14:25:45.173Z
We are all waiting for Aaronson's blog post :)
Lamine
CC BY-SA 4.0
2022-05-13T23:30:06.463Z
He's already commented on it: https://scottaaronson.blog/?p=6405#comment-1939064 https://scottaaronson.blog/?p=6405#comment-1939221
delete000
<quantum-computing><permanent>
New quantum algorithm for approximating permanent
Hhan
# New quantum algorithm for approximating permanent

(Asked by: username_0 on 2022-05-06)

Joonsuk Huh uploaded a paper "[A fast quantum algorithm for computing matrix permanent](https://arxiv.org/abs/2205.01328)
" 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?

**Tags:** quantum-computing, permanent
> **Comments:**
> **username_1**: We are all waiting for Aaronson's blog post :)  
> **username_2**: He's already commented on it: https://scottaaronson.blog/?p=6405#comment-1939064 https://scottaaronson.blog/?p=6405#comment-1939221  

---

## 0 answers

