Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
复制标题
DOI：
10.1007/s11128-015-1230-7
复制
发表时间：
2016-04-01
影响因子：
2.5
通讯作者：
Portugal, Renato
中科院分区：
文献类型：
--
作者：
Portugal, Renato
创造的量子行走（QW）正在许多环境中使用，其目标是理解量子系统和为量子计算机构建量子算法。利用量子理论似乎允许基于相同经典模型（在本例中为经典随机游走）的不同量化版本这一事实，提出了诸如 Szegedy 模型和连续时间 QW 之类的替代模型。在这项工作中，我们展示了创造的 QW 与 Szegedy 的 QW 等效的条件。这些 QW 模型都有一大类实例，从某种意义上说，当我们将发生创造的 QW 的图转换为发生 Szegedy QW 的二分图时，演化算子是相等的，反之亦然。我们还表明，使用创造的 QW 模型的抽象搜索算法可以使用带有汇的二部图放入 Szegedy 的搜索框架中。
Coined quantum walks (QWs) are being used in many contexts with the goal of understanding quantum systems and building quantum algorithms for quantum computers. Alternative models such as Szegedy's and continuous-time QWs were proposed taking advantage of the fact that quantum theory seems to allow different quantized versions based on the same classical model, in this case the classical random walk. In this work, we show the conditions upon which coined QWs are equivalent to Szegedy's QWs. Those QW models have in common a large class of instances, in the sense that the evolution operators are equal when we convert the graph on which the coined QW takes place into a bipartite graph on which Szegedy's QW takes place, and vice versa. We also show that the abstract search algorithm using the coined QW model can be cast into Szegedy's searching framework using bipartite graphs with sinks.