TY - JOUR

T1 - Quantum walk on the generalized birkhoff polytope graph

AU - Cação, Rafael

AU - Cortez, Lucas

AU - de Farias, Ismael

AU - Kozyreff, Ernee

AU - Moqadam, Jalil Khatibi

AU - Portugal, Renato

N1 - Funding Information:
Acknowledgments: LRCTC acknowledges financial support from Edward E. Whitacre Jr. College of Engineering’s Dean’s office. RFC acknowledges financial support from Edward E. Whitacre Jr. College of Engineering and J.T. and Margaret Talkington Scholarship. IRdF thanks Jesus de Loera for enlightening discussions on the properties of the transportation polytope. JKM acknowledges financial support from CNPq grant number 302203/2021-4. RP acknowledges financial support from FAPERJ grant number CNE E-26/202.872/2018, and CNPq grant number 308923/2019-7. The authors acknowledge the High-Performance Computing Center (HPCC) at Texas Tech University for providing computational resources that have contributed to the research results reported within this paper. URL: http://www.hpcc.ttu.edu, accessed on 5 August 2021.
Publisher Copyright:
© 2021 by the authors. Licensee MDPI, Basel, Switzerland.

PY - 2021/10

Y1 - 2021/10

N2 - 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 /ɛ).

AB - 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 /ɛ).

KW - Counting

KW - Generalized Birkhoff polytope

KW - Quantum walk

KW - Sampling

KW - Transportation problem

UR - http://www.scopus.com/inward/record.url?scp=85115999389&partnerID=8YFLogxK

U2 - 10.3390/e23101239

DO - 10.3390/e23101239

M3 - Article

AN - SCOPUS:85115999389

SN - 1099-4300

VL - 23

JO - Entropy

JF - Entropy

IS - 10

M1 - 1239

ER -