标题： 高斯矩阵行列式的量子估计界限 显示英文标题

标题： Quantum estimation bound of Gaussian matrix permanent

摘要： 精确计算矩阵行列式的值以及甚至进行乘法误差估计对于经典和量子计算机来说都是具有挑战性的。 关于随机高斯矩阵的行列式，加法误差估计与玻色采样密切相关，而实现乘法误差估计需要指数级的采样次数。 我们新开发的矩阵行列式公式及其对应的量子表达式，相比Gurvits的经典采样算法，能够更好地估计随机高斯矩阵的平均加法误差。 著名的Ryser公式已被转化为量子行列式估计器。 在处理大小为$N$的实随机高斯方阵时，量子估计器可以以小于$\epsilon(\sqrt{\mathrm{e}N})^{N}$的加法误差近似矩阵行列式，其中$\epsilon$是估计精度。 相比之下，Gurvits的经典采样算法的估计误差为$\epsilon(2\sqrt{N})^{N}$，这比量子方法的误差指数级大（$1.2^{N}$）。 正如预期的那样，量子加法误差界限无法达到$(2\pi N)^{1/4}\epsilon(\sqrt{N/\mathrm{e}})^{N}$的乘法误差界限。 此外，当使用基于量子相位估计算法的幅值估计时，量子行列式估计器的速度可以比经典估计器快多达二次方。 显示英文摘要

摘要： Exact calculation and even multiplicative error estimation of matrix permanent are challenging for both classical and quantum computers. Regarding the permanents of random Gaussian matrices, the additive error estimation is closely linked to boson sampling, and achieving multiplicative error estimation requires exponentially many samplings. Our newly developed formula for matrix permanents and its corresponding quantum expression have enabled better estimation of the average additive error for random Gaussian matrices compared to Gurvits' classical sampling algorithm. The well-known Ryser formula has been converted into a quantum permanent estimator. When dealing with real random Gaussian square matrices of size $N$, the quantum estimator can approximate the matrix permanent with an additive error smaller than $\epsilon(\sqrt{\mathrm{e}N})^{N}$, where $\epsilon$ is the estimation precision. In contrast, Gurvits' classical sampling algorithm has an estimation error of $\epsilon(2\sqrt{N})^{N}$, which is exponentially larger ($1.2^{N}$) than the quantum method. As expected, the quantum additive error bound fails to reach the multiplicative error bound of $(2\pi N)^{1/4}\epsilon(\sqrt{N/\mathrm{e}})^{N}$. Additionally, the quantum permanent estimator can be up to quadratically faster than the classical estimator when using quantum phase estimation-based amplitude estimation.