filmov
tv
Zhengfeng Ji, Approximating Permanent of Random Matrices with Vanishing Mean
Показать описание
Abstract
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 particular 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 a mean of at least 1/polyloglog(n). In this talk, we will discuss how to improve the result, simplify the proof, and hopefully further motivate interests in understanding the central complexity theory conjectures supporting quantum supremacy claims. It is based on joint work with Zhihan Jin and Pinyan Lu.
About CFCS Quantum Day
CFCS Quantum Day, organized by Center on Frontiers of Computing Studies (CFCS), Peking University, is a one-day seminar focusing on pioneering works on supremacy, quantum simulation, and applications with near-term quantum computing hardware. Given continued uncertainty surrounding the future of COVID-19 and worldwide travel precautions, CFCS Quantum Day was held online on May 12th, 2021.
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 particular 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 a mean of at least 1/polyloglog(n). In this talk, we will discuss how to improve the result, simplify the proof, and hopefully further motivate interests in understanding the central complexity theory conjectures supporting quantum supremacy claims. It is based on joint work with Zhihan Jin and Pinyan Lu.
About CFCS Quantum Day
CFCS Quantum Day, organized by Center on Frontiers of Computing Studies (CFCS), Peking University, is a one-day seminar focusing on pioneering works on supremacy, quantum simulation, and applications with near-term quantum computing hardware. Given continued uncertainty surrounding the future of COVID-19 and worldwide travel precautions, CFCS Quantum Day was held online on May 12th, 2021.
0:43:15
1:01:46
0:22:35
![[QCrypt2018] 8.30 Zhengfeng](https://i.ytimg.com/vi/mN3Ce4gDFuQ/hqdefault.jpg)
0:21:10
0:21:47
1:07:41
1:17:01
1:02:30
1:02:32
0:22:03
1:10:10
0:31:46
0:25:32
0:00:17
0:31:43
2:57:18
0:46:44
0:41:29
1:19:58
0:57:09
0:54:16
11:27:20
11:53:06