Quantum walk on the generalized birkhoff polytope graph

Rafael Cação, Lucas Cortez, Ismael de Farias, Ernee Kozyreff, Jalil Khatibi Moqadam, Renato Portugal

Research output: Contribution to journalArticlepeer-review


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 m suppliers). We analyze two types of initial states. If the walker starts on a single node, the quantum mixing time does not depend on m, 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 /ɛ).

Original languageEnglish
Article number1239
Issue number10
StatePublished - Oct 2021


  • Counting
  • Generalized Birkhoff polytope
  • Quantum walk
  • Sampling
  • Transportation problem


Dive into the research topics of 'Quantum walk on the generalized birkhoff polytope graph'. Together they form a unique fingerprint.

Cite this