Approximating the Permanent of a Random Matrix with Vanishing Mean
Approximating the Permanent of a Random Matrix with Vanishing Mean
复制标题
用消失均值逼近随机矩阵的永久矩阵
DOI：
10.1109/focs.2018.00012
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
S. Mehraban
中科院分区：
文献类型：
--
作者：
Lior Eldar;S. Mehraban
对于自然随机矩阵（包括有限域上的矩阵或高斯系综），永久式是平均难以精确计算的。如果我们只关心近似而不是精确计算，我们是否应该期望平均计算仍然是#P-困难的？在这项工作中，我们采取了第一步解决这个问题：我们提出了一个准多项式时间确定性算法，用于近似一个典型的n × n随机矩阵的永久式，单位方差和消失的平均值μ = O（ln ln n）^-1/8到逆多项式乘法误差。（或者，对于平均值为μ = 1/polylog（n）的矩阵，在时间2 ^n ^ε上可以实现永久近似，对于任意小的ε>0）。该算法显着扩展了政权的矩阵，有效的近似永久的是已知的。这是因为不像以前的算法需要矩阵[1]的条目之间的符号之间的严格相关性，[2]它可以容忍这种相关性可以忽略不计（尽管非零）的随机集合。在重要的特殊情况中，我们注意到：1）有偏高斯：每个条目都是一个单位方差为1且均值为μ的复高斯。2)有偏伯努利：每个条目是-1 + μ的概率为1/2，1的概率为1/2。这些结果反驳了一种普遍的直觉，即计算积和式的困难，甚至是近似的困难，仅仅源于我们不能处理具有许多相反符号的矩阵。高斯系综接近于计算零均值高斯矩阵的积和式的极限[3]。这个猜想是玻色子抽样范式的基本假设之一，近年来在量子霸权实验的背景下受到了广泛的关注。我们还表明，永久性的偏置高斯系综是P-难以准确计算平均。据我们所知，这是第一个自然的例子，一个计数问题，变得容易，只有当平均情况分析和近似相结合。在技术层面上，我们的方法源于Barvinok最近采取的方法[1]，[4]，[5]，[6]，他使用泰勒级数近似与永久相关的某个一元多项式的对数。我们的主要贡献是介绍一个平均情况下分析这些相关的多项式。我们补充我们的方法与一个新的技术迭代计算泰勒级数近似的函数，是在附近的曲线在复平面上的分析。这种方法可以看作是复分析中解析延拓的一种计算形式。
The permanent is #P-hard to compute exactly on average for natural random matrices including matrices over finite fields or Gaussian ensembles. Should we expect that it remains #P-hard to compute on average if we only care about approximation instead of exact computation? In this work we take a first step towards resolving this question: We present a quasi-polynomial time deterministic algorithm for approximating the permanent of a typical n × n random matrix with unit variance and vanishing mean µ = O(ln ln n)^-1/8 to within inverse polynomial multiplicative error. (alternatively, one can achieve permanent approximation for matrices with mean µ = 1/polylog(n) in time 2^n^ε, for arbitrarily small ε>0). The proposed algorithm significantly extends the regime of matrices for which efficient approximation of the permanent is known. This is because unlike previous algorithms which require a stringent correlation between the signs of the entries of the matrix [1], [2] it can tolerate random ensembles in which this correlation is negligible (albeit non-zero). Among important special cases we note: 1) Biased Gaussian: each entry is a complex Gaussian with unit variance 1 and mean µ. 2) Biased Bernoulli: each entry is -1 + µ with probability 1/2, and 1 with probability 1/2. These results counter the common intuition that the difficulty of computing the permanent, even approximately, stems merely from our inability to treat matrices with many opposing signs. The Gaussian ensemble approaches the threshold of a conjectured hardness [3] of computing the permanent of a zero mean Gaussian matrix. This conjecture is one of the baseline assumptions of the BosonSampling paradigm that has received vast attention in recent years in the context of quantum supremacy experiments. We furthermore show that the permanent of the biased Gaussian ensemble is #P-hard to compute exactly on average. To our knowledge, this is the first natural example of a counting problem that becomes easy only when average case analysis and approximation are combined. On a technical level, our approach stems from a recent approach taken by Barvinok [1], [4], [5], [6] who used Taylor series approximation of the logarithm of a certain univariate polynomial related to the permanent. Our main contribution is to introduce an average-case analysis of such related polynomials. We complement our approach with a new technique for iteratively computing a Taylor series approximation of a function that is analytical in the vicinity of a curve in the complex plane. This method can be viewed as a computational version of analytic continuation in complex analysis.