Quantum walk on the generalized birkhoff polytope graph
Nenhuma Miniatura disponível
Data
2021-10-01
Autores
Cação, Rafael
Cortez, Lucas
de Farias, Ismael
Kozyreff, Ernee [UNESP]
Moqadam, Jalil Khatibi
Portugal, Renato
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
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 /ɛ).
Descrição
Palavras-chave
Counting, Generalized Birkhoff polytope, Quantum walk, Sampling, Transportation problem
Como citar
Entropy, v. 23, n. 10, 2021.