Cação Rafael, Cortez Lucas, de Farias Ismael, Kozyreff Ernee, Khatibi Moqadam Jalil, Portugal Renato
Department of Industrial, Manufacturing & Systems Engineering, Texas Tech University, Lubbock, TX 79430, USA.
Campus of Itapeva, Universidade Estadual Paulista (Unesp), Itapeva 18409-010, SP, Brazil.
Entropy (Basel). 2021 Sep 23;23(10):1239. doi: 10.3390/e23101239.
We study discrete-time quantum walks on generalized Birkhoff polytope graphs (GBPGs), which arise in the solution-set to certain transportation linear programming problems (TLPs). It is known that quantum walks mix at most quadratically faster than random walks on cycles, two-dimensional lattices, hypercubes, and bounded-degree graphs. In contrast, our numerical results show that it is possible to achieve a greater than quadratic quantum speedup for the mixing time on a subclass of GBPG (TLP with two consumers and suppliers). We analyze two types of initial states. If the walker starts on a single node, the quantum mixing time does not depend on , even though the graph diameter increases with it. To the best of our knowledge, this is the first example of its kind. If the walker is initially spread over a maximal clique, the quantum mixing time is O(m/ϵ), where is the threshold used in the mixing times. This result is better than the classical mixing time, which is O(m1.5/ϵ).
我们研究广义伯克霍夫多胞体图（GBPGs）上的离散时间量子游走，这些图出现在某些运输线性规划问题（TLPs）的解集之中。已知在循环图、二维晶格、超立方体和有界度图上，量子游走的混合速度最多比随机游走快二次方倍。相比之下，我们的数值结果表明，对于GBPG的一个子类（具有两个消费者和供应商的TLP），有可能在混合时间上实现大于二次方的量子加速。我们分析了两种类型的初始状态。如果游走者从单个节点开始，量子混合时间不依赖于 ，尽管图的直径会随着它增大。据我们所知，这是此类的首个例子。如果游走者最初分布在一个最大团上，量子混合时间为O(m/ϵ)，其中 是混合时间中使用的阈值。这个结果优于经典混合时间O(m1.5/ϵ)。
