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 -