In this work we focus on the notion of quantum hitting time for discrete-time Szegedy quantum walks, compared to its classical counterpart. Under suitable hypotheses, quantum hitting time is known to be of the order of the square root of classical hitting time: this quadratic speedup is a remarkable example of the computational advantages associated with quantum approaches. Our purpose here is twofold. On one hand, we provide a detailed proof of quadratic speedup for time-reversible walks within the Szegedy framework, in a language that should be familiar to the linear algebra community. Moreover, we explore the use of a general distribution in place of the stationary distribution in the definition of quantum hitting time, through theoretical considerations and numerical experiments.
翻译:在这项工作中,我们把注意力集中在离散时间Szegedy量子行走的量子击打时间的概念上,与其古典的对应词相比。在适当的假设下,量子击打时间已知是经典击打时间平方根的顺序:这种二次加速是量子方法的计算优势的一个显著例子。我们在这里的目的有两个方面。一方面,我们用线性代数群应该熟悉的语言,详细证明在Szegedy框架内可逆时间行走的二次加速。此外,我们探索如何通过理论考虑和数字实验,在量子击时间的定义中使用一般分布,取代固定分布。