首页|An improved algorithm for computing hitting probabilities of quantum walks
An improved algorithm for computing hitting probabilities of quantum walks
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
Quantum walks are the quantum corresponding version of classical random walks, providing polynomial and even exponential acceleration for some classical difficult problems. In recent years, there have been numerous researches on quantum walks, among which the hitting probabilities problem is another crucial problem. In 2021, Guan et al. have proposed an HHL-based algorithm to calculate the hitting probabilities of quantum walks, which can effectively transform the original problem into an inverse matrix problem, then achieve an acceleration effect on the corresponding classical algorithm under some specific conditions. However, we propose a new algorithm consisting of an improved quantum matrix inversion algorithm with complexity O [kappa 2 log1.5(kappa/epsilon)poly log(n)], where kappa is the condition number of the matrix, n + 1 is the number of positions of the one-dimensional quantum walks, and epsilon is the expected accuracy of the output state. Compared to the HHL-based algorithm, our improved algorithm achieves an exponential improvement in the dependence on accuracy. (c) 2022 Elsevier B.V. All rights reserved.
Random walksQuantum walksQuantum computationSIMULATION
NSTL
Elsevier
