论文标题
高斯矩阵永久的量子估计结合
Quantum estimation bound of Gaussian matrix permanent
论文作者
论文摘要
对于经典计算机和量子计算机来说，矩阵永久性的精确计算甚至乘法误差估计都具有挑战性。关于随机高斯矩阵的持久性，添加性误差估计与玻色子采样密切相关，并且实现乘法误差估计需要指数级的采样。与Gurvits的经典采样算法相比，我们新开发的用于矩阵永久物的公式及其相应的量子表达能够更好地估算随机高斯矩阵的平均添加剂误差。众所周知的Ryser公式已转换为量子永久估计器。当处理尺寸$ n $的真实随机高斯正方形矩阵时，量子估计器可以将矩阵永久近似，其添加误差小于$ε（\ sqrt {\ sqrt {\ mathrm {e} n} n} n}）^{n} $，其中$ε$是估计精度。相比之下，Gurvits的经典采样算法的估计误差为$ε（2 \ sqrt {n}）^{n} $，其呈指数级（$ 1.2^{n} $），而不是量子方法。正如预期的那样，量子添加误差绑定无法达到$（2πn）^{1/4}ε（\ 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 $ε(\sqrt{\mathrm{e}N})^{N}$, where $ε$ is the estimation precision. In contrast, Gurvits' classical sampling algorithm has an estimation error of $ε(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πN)^{1/4}ε(\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.
