{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T08:38:20Z","timestamp":1773218300443,"version":"3.50.1"},"reference-count":39,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2021,9,23]],"date-time":"2021-09-23T00:00:00Z","timestamp":1632355200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>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\/\u03f5), where \u03f5 is the threshold used in the mixing times. This result is better than the classical mixing time, which is O(m1.5\/\u03f5).<\/jats:p>","DOI":"10.3390\/e23101239","type":"journal-article","created":{"date-parts":[[2021,9,23]],"date-time":"2021-09-23T09:59:15Z","timestamp":1632391155000},"page":"1239","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Quantum Walk on the Generalized Birkhoff Polytope Graph"],"prefix":"10.3390","volume":"23","author":[{"given":"Rafael","family":"Ca\u00e7\u00e3o","sequence":"first","affiliation":[{"name":"Department of Industrial, Manufacturing & Systems Engineering, Texas Tech University, Lubbock, TX 79430, USA"}]},{"given":"Lucas","family":"Cortez","sequence":"additional","affiliation":[{"name":"Department of Industrial, Manufacturing & Systems Engineering, Texas Tech University, Lubbock, TX 79430, USA"}]},{"given":"Ismael","family":"de Farias","sequence":"additional","affiliation":[{"name":"Department of Industrial, Manufacturing & Systems Engineering, Texas Tech University, Lubbock, TX 79430, USA"}]},{"given":"Ernee","family":"Kozyreff","sequence":"additional","affiliation":[{"name":"Campus of Itapeva, Universidade Estadual Paulista (Unesp), Itapeva 18409-010, SP, Brazil"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7428-9896","authenticated-orcid":false,"given":"Jalil","family":"Khatibi Moqadam","sequence":"additional","affiliation":[{"name":"National Laboratory of Scientific Computing (LNCC), Petr\u00f3polis 25651-076, RJ, Brazil"}]},{"given":"Renato","family":"Portugal","sequence":"additional","affiliation":[{"name":"National Laboratory of Scientific Computing (LNCC), Petr\u00f3polis 25651-076, RJ, Brazil"}]}],"member":"1968","published-online":{"date-parts":[[2021,9,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Nemhauser, G., and Wolsey, L. (1988). Integer and Combinatorial Optimization, Wiley.","DOI":"10.1002\/9781118627372"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF02614365","article-title":"A Polynomial Time Primal Network Simplex Algorithm for Minimum Cost Flows","volume":"8","author":"Orlin","year":"1997","journal-title":"Math. Program."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1145\/1008731.1008733","article-title":"Solving convex programs by random walks","volume":"51","author":"Bertsimas","year":"2004","journal-title":"J. ACM"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1002\/rsa.20222","article-title":"Random Walks on the Vertices of Transportation Polytopes with Constant Number of Sources","volume":"33","author":"Cryan","year":"2008","journal-title":"Random Struct. Algorithms"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Aharonov, D., Ambainis, A., Kempe, J., and Vazirani, U. (2001, January 6\u20138). Quantum walks on graphs. Proceedings of the Thirty-Third annual ACM Symposium on Theory of Computing, Crete, Greece.","DOI":"10.1145\/380752.380758"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1038\/s41586-019-1666-5","article-title":"Quantum supremacy using a programmable superconducting processor","volume":"574","author":"Arute","year":"2019","journal-title":"Nature"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Wu, Y., Bao, W.S., Cao, S., Chen, F., Chen, M.C., Chen, X., Chung, T.H., Deng, H., Du, Y., and Fan, D. (2021). Strong quantum computational advantage using a superconducting quantum processor. arXiv.","DOI":"10.1103\/PhysRevLett.127.180501"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Portugal, R. (2018). Quantum Walks and Search Algorithms, Springer.","DOI":"10.1007\/978-3-319-97813-0"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1007\/s11128-020-02938-5","article-title":"Implementation of quantum walks on IBM quantum computers","volume":"19","author":"Acasiete","year":"2020","journal-title":"Quantum Inf. Process."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Preskill, J. (2018). Quantum Computing in the NISQ era and beyond. arXiv.","DOI":"10.22331\/q-2018-08-06-79"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1090\/conm\/625\/12491","article-title":"Combinatorics and Geometry of Transportation Polytopes: An Update","volume":"625","author":"Kim","year":"2014","journal-title":"Contemp. Math."},{"key":"ref_12","first-page":"1","article-title":"Random walks on graphs: A survey","volume":"2","year":"1993","journal-title":"Combinatorics"},{"key":"ref_13","unstructured":"Chv\u00e1tal, V. (1980). Linear Programming, W.H. Freeman and Company."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Bondy, J., and Murty, U. (1976). Graph Theory with Applications, North-Holland.","DOI":"10.1007\/978-1-349-03521-2"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1539","DOI":"10.1016\/j.jcta.2013.05.003","article-title":"Perturbation of Transportation Polytopes","volume":"120","author":"Liu","year":"2013","journal-title":"J. Comb. Theory A"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0095-8956(72)90060-3","article-title":"Transportation Polytopes","volume":"13","author":"Bolker","year":"1972","journal-title":"J. Comb. Theory B"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1002\/sapm1941201224","article-title":"The Distribution of a Product from Several Sources to Numerous Locations","volume":"20","author":"Hitchcock","year":"1941","journal-title":"J. Math. Phys."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"136","DOI":"10.2307\/1907301","article-title":"Optimum Utilization of the Transportation System","volume":"17","author":"Koopmans","year":"1947","journal-title":"Econometrica"},{"key":"ref_19","first-page":"1","article-title":"Primal transportation and transshipment algorithms","volume":"24","author":"Ahrens","year":"1980","journal-title":"Z. Oper. Res."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1287\/moor.27.3.485.310","article-title":"The stable allocation (or ordinal transportation) problem","volume":"27","author":"Balinski","year":"2002","journal-title":"Math. Oper. Res."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1137\/0606048","article-title":"On Transportation Problems with Upper Bounds on Leading Rectangles","volume":"6","author":"Barnes","year":"1985","journal-title":"SIAM J. Algebr. Discret. Methods"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1306","DOI":"10.1016\/j.jcta.2009.03.010","article-title":"Graphs of Transportation Polytopes","volume":"116","author":"Kim","year":"2009","journal-title":"J. Comb. Theory A"},{"key":"ref_23","unstructured":"Dantzig, G., and Veinott, A. (1968). Facets and Vertices of Transportation Polytopes. Mathematics of the Decision Sciences, Part 1, AMS."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/PL00001277","article-title":"Four Questions on the Birkhoff Polytope","volume":"2","author":"Pak","year":"2000","journal-title":"Ann. Comb."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1287\/moor.8.3.381","article-title":"The Complexity of Vertex Enumeration Methods","volume":"8","author":"Dyer","year":"1983","journal-title":"Math. Oper. Res."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1002\/rsa.3240010105","article-title":"Asymptotic Analysis of a Random Walk on a Hyper-Cube with Many Dimensions","volume":"1","author":"Diaconis","year":"1990","journal-title":"Random Struct. Algorithms"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1137\/S0097539702411915","article-title":"Random Walks on Truncated Cubes and Sampling 0\u20131 Knapsack Solutions","volume":"34","author":"Morris","year":"2004","journal-title":"SIAM J. Comput."},{"key":"ref_28","unstructured":"Moore, C., and Russell, A. (2002, January 13\u201315). Quantum Walks on the Hypercube. Proceedings of the 6th International Workshop on Randomization and Approximation Techniques RANDOM, Cambridge, MA, USA."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"042312","DOI":"10.1103\/PhysRevA.77.042312","article-title":"Mixing times in quantum walks on the hypercube","volume":"77","author":"Marquezino","year":"2008","journal-title":"Phys. Rev. A"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"042341","DOI":"10.1103\/PhysRevA.82.042341","article-title":"Mixing times in quantum walks on two-dimensional grids","volume":"82","author":"Marquezino","year":"2010","journal-title":"Phys. Rev. A"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"335302","DOI":"10.1088\/1751-8113\/43\/33\/335302","article-title":"Bounds for mixing time of quantum walks on finite graphs","volume":"43","author":"Kargin","year":"2010","journal-title":"J. Phys. A Math. Theor."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"050501","DOI":"10.1103\/PhysRevLett.124.050501","article-title":"How Fast Do Quantum Walks Mix?","volume":"124","author":"Chakraborty","year":"2020","journal-title":"Phys. Rev. Lett."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"022423","DOI":"10.1103\/PhysRevA.102.022423","article-title":"Analog quantum algorithms for the mixing of Markov chains","volume":"102","author":"Chakraborty","year":"2020","journal-title":"Phys. Rev. A"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"032115","DOI":"10.1103\/PhysRevA.98.032115","article-title":"Simulation of quantum walks and fast mixing with classical processes","volume":"98","author":"Apers","year":"2018","journal-title":"Phys. Rev. A"},{"key":"ref_35","unstructured":"Dervovic, D. (2020). Quantum Computation, Markov Chains and Combinatorial Optimisation. [Ph.D. Thesis, University College London]."},{"key":"ref_36","unstructured":"Christof, T., and Loebel, A. (2021, August 05). PORTA: POlyhedron Representation Transformation Algorithm, v. 1.4.1. 2015. Available online: http:\/\/porta.zib.de."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Levin, D., and Peres, Y. (2017). Markov Chains and Mixing Times, AMS. [2nd ed.].","DOI":"10.1090\/mbk\/107"},{"key":"ref_38","unstructured":"Guruswami, V. (2016). Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey). arXiv."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"012305","DOI":"10.1103\/PhysRevA.94.012305","article-title":"Transient temperature and mixing times of quantum walks on cycles","volume":"94","author":"Daz","year":"2016","journal-title":"Phys. Rev. A"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/10\/1239\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:03:39Z","timestamp":1760166219000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/10\/1239"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,23]]},"references-count":39,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2021,10]]}},"alternative-id":["e23101239"],"URL":"https:\/\/doi.org\/10.3390\/e23101239","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,23]]}}}