aiqbench analysis
This is a mathematical physics paper on discrete-time quantum walks, the quantum analogue of random walks, built via Szegedy's quantization method. It establishes when quantizing a Markov chain and then aggregating it gives the same result as aggregating first, with worked examples on graphs like Platonic solids and hypercubes. For quantum computing readers, the relevance is theoretical: quantum walks underpin many quantum search and algorithm designs, so structural results like these can clarify when a quantum walk can be simplified or reduced without losing its behavior. It is foundational work with no immediate hardware or application claims.
On aggregation-quantization permutability problem for discrete-time Markov chains
arXiv:2603.14269v3 Announce Type: replace Abstract: Given random walk on a graph, the corresponding discrete-time quantum walk can be constructed using the method proposed by Szegedy. On the other hand, given a partition of the set of states of a Markov chain, one can study the corresponding aggregated process. We extend the aggregation technique to the level of quantum Markov chains. We provide conditions under which application of these two operations - Szegedy's quantization and aggregation - give the same result. These consist of the strong lumpability of the underlying Markov chain supplemented by nonlinear relations, generalizing Kolmogorov's cycle condition, that account for the coefficients of both the original and the aggregated transition matrices. In particular, we show that the conditions are satisfied in the case of the random walk on graphs equipped with equitable partitions. We present several examples, which include the classical/quantum walks on Platonic solids. We discuss also relation of discrete-time classical/quantum walks on $N$-dimensional hypercube and the Ehrenfests urn model with $N$ particles. We apply our technique for of discrete-time walks on Cayley graphs of free groups. We also compare our results with those obtained using Cantero-Moral-Velazquez uniformization of unitary matrices.
Abstract:Given random walk on a graph, the corresponding discrete-time quantum walk can be constructed using the method proposed by Szegedy. On the other hand, given a partition of the set of states of a Markov chain, one can study the corresponding aggregated process. We extend the aggregation technique to the level of quantum Markov chains. We provide conditions under which application of these two operations - Szegedy's quantization and aggregation - give the same result. These consist of the strong lumpability of the underlying Markov chain supplemented by nonlinear relations, generalizing Kolmogorov's cycle condition, that account for the coefficients of both the original and the aggregated transition matrices. In particular, we show that the conditions are satisfied in the case of the random walk on graphs equipped with equitable partitions. We present several examples, which include the classical/quantum walks on Platonic solids. We discuss also relation of discrete-time classical/quantum walks on $N$-dimensional hypercube and the Ehrenfests urn model with $N$ particles. We apply our technique for of discrete-time walks on Cayley graphs of free groups. We also compare our results with those obtained using Cantero-Moral-Velazquez uniformization of unitary matrices.
22 pages, 10 figures; v2 presentation improved; v3 formulation of Proposition 3.1 corrected, while the main idea of the work remains unchanged
Quantum Physics (quant-ph); Mathematical Physics (math-ph); Combinatorics (math.CO); Dynamical Systems (math.DS)
arXiv:2603.14269 [quant-ph]
(or arXiv:2603.14269v3 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2603.14269 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 311 words