2019/11/27 by Ji, Zhengfeng, Jin, Zhihan, Lu, Pinyan
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.1911.11962
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/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/polylog(n). We note that if it can be further improved to 1/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/ε, or PTAS (polynomial in n but exponential in 1/ε), where ε is the approximation parameter.