Quantum Walk on the Generalized Birkhoff Polytope Graph.

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/ϵ).