Approximating Permanent of Random Matrices with Vanishing Mean: Made Better and Simpler
| Title: | Approximating Permanent of Random Matrices with Vanishing Mean: Made Better and Simpler |
|---|---|
| Authors: | Ji, Zhengfeng, Jin, Zhihan, Lu, Pinyan |
| Publication Year: | 2019 |
| Collection: | Computer Science Quantum Physics |
| Subject Terms: | Computer Science - Data Structures and Algorithms, Quantum Physics |
| More Details: | The algorithm and complexity of approximating the permanent of a matrix is an extensively studied topic. Recently, its connection with quantum supremacy and more specifically BosonSampling draws special attention to the average-case approximation problem of the permanent of random matrices with zero or small mean value for each entry. Eldar and Mehraban (FOCS 2018) gave a quasi-polynomial time algorithm for random matrices with mean at least $1/\mathbf{\mathrm{polyloglog}} (n)$. In this paper, we improve the result by designing a deterministic quasi-polynomial time algorithm and a PTAS for random matrices with mean at least $1/\mathbf{\mathrm{polylog}}(n)$. We note that if it can be further improved to $1/\mathbf{\mathrm{poly}}(n)$, it will disprove a central conjecture for quantum supremacy. Our algorithm is also much simpler and has a better and flexible trade-off for running time. The running time can be quasi-polynomial in both $n$ and $1/\epsilon$, or PTAS (polynomial in $n$ but exponential in $1/\epsilon$), where $\epsilon$ is the approximation parameter. Comment: 30 pages |
| Document Type: | Working Paper |
| Access URL: | http://arxiv.org/abs/1911.11962 |
| Accession Number: | edsarx.1911.11962 |
| Database: | arXiv |
| Description not available. |