量子科技中心_量科网

该论文提出了一种用于马尔可夫链谱隙估计的量子算法，该算法在所有参数下关于顶点数量都是准最优的（即最优至多对数因子），并且若允许的相对误差超过某个临界值，其关于谱隙倒数本身也是准最优的。特别值得注意的是，相较于最优可能的经典算法，这些结果实现了近二次方的优势。该算法还改进了现有量子技术水平，研究人员认为这不仅具有理论意义，在实际应用中也可能产生重要影响：了解马尔可夫链的谱隙可以加速马尔可夫链蒙特卡洛中的采样过程。该工作采用量子奇异值变换方法，并由此发展了一套关于马尔可夫链转移矩阵块编码的理论，这些理论可能具有独立的研究价值。特别地，研究人员针对代数定义的两类马尔可夫链转移矩阵，提出了显式的块编码方法。