标题： 一种快速量子算法计算矩阵行列式 显示英文标题

标题： A fast quantum algorithm for computing matrix permanent

摘要： 计算矩阵行列式是一个经典上难以处理的问题。 本文提出了第一个用于计算矩阵行列式的有效量子算法。 我们将著名的Ryser公式转换为单个量子重叠积分和多项式量子重叠积分的和，分别用乘法误差和加法误差协议来估计矩阵行列式。 我们表明，对于一组特殊的矩阵，矩阵行列式的乘法误差估计是可能的。 这样的量子算法意味着量子计算机可能比我们预期的更强大。 根据矩阵范数的大小以及2-范数与1-范数之间的比率，我们可以获得指数级小的加法误差估计，并且我们的量子协议在对Gurvits的经典采样算法的估计方面表现更好。 我们的量子算法实现了量子计算和计算复杂性理论中开辟新方向的里程碑。 它可能解决关键的计算复杂性问题，例如确定有界误差量子多项式时间（BQP）相对于多项式层次结构的位置，这是一个重大的复杂性问题。 此外，我们的量子算法直接展示了矩阵行列式与量子Ising哈密顿量的实时配分函数之间的计算复杂性联系。 显示英文摘要

摘要： Computing a matrix permanent is known to be a classically intractable problem. This paper presents the first efficient quantum algorithm for computing matrix permanents. We transformed the well-known Ryser's formula into a single quantum overlap integral and a polynomial sum of quantum overlap integrals to estimate a matrix permanent with the multiplicative error and additive error protocols, respectively. We show that the multiplicative error estimation of a matrix permanent would be possible for a special set of matrices. Such a quantum algorithm would imply that quantum computers can be more powerful than we expected. Depending on the size of a matrix norm and the ratio between 2-norm and 1-norm, we can obtain an exponentially small additive error estimation and better estimation against Gurvits' classical sampling algorithm with our quantum protocol. Our quantum algorithm attains the milestone of opening a new direction in quantum computing and computational complexity theory. It might resolve crucial computational complexity issues like locating the bounded error quantum polynomial time (BQP) relative to the polynomial hierarchy, which has been a big complexity question. Moreover, our quantum algorithm directly shows the computational complexity connection between the matrix permanent and the real-time partition function of the quantum Ising Hamiltonian.