{"ID":2822714,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2601.02518","arxiv_id":"2601.02518","title":"Diffusion Computation versus Quantum Computation: A Comparative Model for Order Finding and Factoring","abstract":"We study a hybrid computational model for integer factorization in which the only non-classical resource is access to an \\emph{iterated diffusion process} on a finite graph. Concretely, a \\emph{diffusion step} is defined to be one application of a symmetric stochastic matrix (the half-lazy walk operator) to an $\\ell^{1}$--normalized state vector, followed by an optional readout of selected coordinates. Let $N\\ge 3$ be an odd integer which is neither prime nor a prime power, and let $b\\in(\\mathbb{Z}/N\\mathbb{Z})^\\ast$ have odd multiplicative order $r={\\rm ord}_N(b)$. We construct, without knowing $r$ in advance, a weighted Cayley graph whose vertex set is the cyclic subgroup $\\langle b\\rangle$ and whose edges correspond to the powers $b^{\\pm 2^t}$ for $t\\le \\lfloor \\log_2 N\\rfloor+1$. Using an explicit spectral decomposition together with an elementary doubling lemma, we show that $r$ can be recovered from a single heat-kernel value after at most $O((\\log_2 N)^2)$ diffusion steps, with an effective bound. We then combine this order-finding model with the standard reduction from factoring to order finding (in the spirit of Shor's framework) to obtain a randomized factorization procedure whose success probability depends only on the number $m$ of distinct prime factors of $N$. Our comparison with Shor's algorithm is \\emph{conceptual and model-based}. We replace unitary $\\ell^2$ evolution by Markovian $\\ell^1$ evolution, and we report complexity in two cost measures: digital steps and diffusion steps. Finally, we include illustrative examples and discussion of practical implementations.","short_abstract":"We study a hybrid computational model for integer factorization in which the only non-classical resource is access to an \\emph{iterated diffusion process} on a finite graph. Concretely, a \\emph{diffusion step} is defined to be one application of a symmetric stochastic matrix (the half-lazy walk operator) to an $\\ell^{1...","url_abs":"https://arxiv.org/abs/2601.02518","url_pdf":"https://arxiv.org/pdf/2601.02518v1","authors":"[\"Carlos A. Cadavid\",\"Paulina Hoyos\",\"Jay Jorgenson\",\"Lejla Smajlović\",\"J. D. Vélez\"]","published":"2026-01-05T19:45:38Z","proceeding":"math.SP","tasks":"[\"math.SP\",\"cs.CR\"]","methods":"[\"Diffusion Model\"]","has_code":false}