Diffusion Computation versus Quantum Computation: A Comparative Model for Order Finding and Factoring
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 --normalized state vector, followed by an optional readout of selected coordinates. Let be an odd integer which is neither prime nor a prime power, and let have odd multiplicative order . We construct, without knowing in advance, a weighted Cayley graph whose vertex set is the cyclic subgroup and whose edges correspond to the powers for . Using an explicit spectral decomposition together with an elementary doubling lemma, we show that can be recovered from a single heat-kernel value after at most 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 of distinct prime factors of . Our comparison with Shor's algorithm is \emph{conceptual and model-based}. We replace unitary evolution by Markovian evolution, and we report complexity in two cost measures: digital steps and diffusion steps. Finally, we include illustrative examples and discussion of practical implementations.