Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Conference on Quantum Communications, Networking, and Computing (QCNC)

Quantum Walkers and Diffusion

John C Vining, Howard A. Blair

Published Mar 31, 2025• 0 citations
Publisher

Abstract

Quantum walks model the behavior of a quantum state traversing a classically defined, generally finite, graph structure. This paper introduces blind quantum diffusion, a technique for evolving quantum walkers through a finite connected network without requiring global knowledge of the graph. We frame the multi-walker problem as a finite quantum cellular automaton where each vertex holds a walker at all times. These walkers will never collide as their vertex position is superpositioned by the network’s evolution and at each time step their positions update by conditioning swaps on quantum coins and partial comparators of the neighboring states. This model generates strong entanglement between vertex states providing a path toward structure independent diffusion driven by highly localized computation. We will examine some mathematical structures underlying state diffusion on arbitrary graphs such as the commutativity of operations and expected time for walkers to reach specified destinations.

DOI
10.1109/qcnc64685.2025.00120

Related papers

Quantum State Diffusion on a Graph

John C Vining, Howard A. Blair

Quantum walks have frequently envisioned the behavior of a quantum state traversing a classically defined, generally finite, graph structure. While this approach has already generated significant results, it imposes a strong assumption: all nodes where the walker is not positioned are quiescent. This paper will examine some mathematical structures that underlie state diffusion on arbitrary graphs, that is the circulation of states within a graph. We will seek to frame the multi-walker problem as a finite quantum cellular automaton. Every vertex holds a walker at all times. The walkers will never collide and at each time step their positions update non-deterministically by a quantum swap of walkers at opposite ends of a randomly chosen edge. The update is accomplished by a unitary transformation of the position of a walker to a superposition of all such possible swaps and then performing a quantum measurement on the superposition of possible swaps. This behavior generates strong entanglement between vertex states which provides a path toward developing local actions producing diffusion throughout the graph without depending on the specific structure of the graph through blind computation.

arXiv:2405.16394•May 26, 2024•0 citations

Universal quantum computation by discontinuous quantum walk

Michael S. Underwood, David L. Feder

Quantum walks are the quantum-mechanical analog of random walks, in which a quantum ``walker'' evolves between initial and final states by traversing the edges of a graph, either in discrete steps from node to node or via continuous evolution under the Hamiltonian furnished by the adjacency matrix of the graph. We present a hybrid scheme for universal quantum computation in which a quantum walker takes discrete steps of continuous evolution. This ``discontinuous'' quantum walk employs perfect quantum-state transfer between two nodes of specific subgraphs chosen to implement a universal gate set, thereby ensuring unitary evolution without requiring the introduction of an ancillary coin space. The run time is linear in the number of simulated qubits and gates. The scheme allows multiple runs of the algorithm to be executed almost simultaneously by starting walkers one time step apart.

arXiv:1008.3578•Physical Review A•Oct 7, 2010•55 citations

Quantum Walk-Based Algorithms for Graph Traversal and Search

Jincheng Zhang

This paper explores the application of quantum walk algorithms to graph traversal and search problems. Classical algorithms often struggle with the computational complexity of traversing and searching large graphs, leading to significant time and resource limitations. Quantum walks, utilizing superposition and interference, offer a potential pathway to achieve exponential speedups. This work details the theoretical framework for applying quantum walks to graph problems, specifically focusing on traversal and search tasks. We present a generalized approach for mapping graph structures onto quantum walk systems and discuss the key mathematical formulations involved. The core of our investigation revolves around the construction of quantum walk operators that mimic the movement and interaction rules inherent in graph traversal. We analyze the evolution of the quantum walk state and derive expressions for the probability of reaching a specific node in the graph. Furthermore, we examine the impact of graph topology on the performance of the quantum walk, highlighting the potential for tailored algorithms to exploit specific graph structures. The results demonstrate the theoretical feasibility of quantum walk algorithms for significantly accelerating graph traversal and search operations, contributing to advancements in areas such as network analysis, database management, and artificial intelligence.

•Sep 6, 2026•0 citations

Bosonic Random Walk Networks for Graph Learning

Shiv Shankar Shankar, Don Towsley

The development of Graph Neural Networks (GNNs) has led to great progress in machine learning on graph-structured data. These networks operate via diffusing information across the graph nodes while capturing the structure of the graph. Recently there has also seen tremendous progress in quantum computing techniques. In this work, we explore applications of multi-particle quantum walks on diffusing information across graphs. Our model is based on learning the operators that govern the dynamics of quantum random walkers on graphs. We demonstrate the effectiveness of our method on classification and regression tasks.

arXiv:2101.00082•Dec 31, 2020•1 citation

Coined quantum walk on a quantum network

Jigyen Bhavsar, Shashank Shekhar, Siddhartha Santra

We explore a discrete-time, coined quantum walk on a quantum network where the coherent superposition of walker moves originates from the unitary interaction of the walker coin with the qubit degrees of freedom in the quantum network. The walk dynamics leads to a growth of entanglement between the walker and the network on one hand and, on the other, between the network qubits among themselves. The initial entanglement among the network qubits plays a crucial role in determining the asymptotic values of these entanglement measures and the quantum walk statistics. Specifically, the entanglement entropy of the walker-network state and the negativity of the quantum network-qubit state saturate to values increasing with the initial network entanglement. The asymptotic time-averaged walker-position probability distribution shows increasing localization around the initial walker position with higher initial network entanglement. A potential application of these results as a characterization tool for quantum network properties is suggested.

arXiv:2406.01558•Physical Review A•Nov 20, 2024•3 citations

Quantum Walk Schemes for Universal Quantum Computation

Michael S. Underwood

Random walks are a powerful tool for the efficient implementation of algorithms in classical computation. Their quantum-mechanical analogues, called quantum walks, hold similar promise. Quantum walks provide a model of quantum computation that has recently been shown to be equivalent in power to the standard circuit model. As in the classical case, quantum walks take place on graphs and can undergo discrete or continuous evolution, though quantum evolution is unitary and therefore deterministic until a measurement is made. This thesis considers the usefulness of continuous-time quantum walks to quantum computation from the perspectives of both their fundamental power under various formulations, and their applicability in practical experiments. In one extant scheme, logical gates are effected by scattering processes. The results of an exhaustive search for single-qubit operations in this model are presented. It is shown that the number of distinct operations increases exponentially with the number of vertices in the scattering graph. A catalogue of all graphs on up to nine vertices that implement single-qubit unitaries at a specific set of momenta is included in an appendix. I develop a novel scheme for universal quantum computation called the discontinuous quantum walk, in which a continuous-time quantum walker takes discrete steps of evolution via perfect quantum state transfer through small `widget' graphs. The discontinuous quantum-walk scheme requires an exponentially sized graph, as do prior discrete and continuous schemes. To eliminate the inefficient vertex resource requirement, a computation scheme based on multiple discontinuous walkers is presented. In this model, n interacting walkers inhabiting a graph with 2n vertices can implement an arbitrary quantum computation on an input of length n, an exponential savings over previous universal quantum walk schemes. This is the first quantum walk scheme that allows for the application of quantum error correction. The many-particle quantum walk can be viewed as a single quantum walk undergoing perfect state transfer on a larger weighted graph, obtained via equitable partitioning. I extend this formalism to non-simple graphs. Examples of the application of equitable partitioning to the analysis of quantum walks and many-particle quantum systems are discussed.

•Jan 1, 2013•0 citations
Quantum walks model the behavior of a quantum state traversing a classically defined, generally finite, graph structure. This paper introduces blind quantum diffusion, a technique for evolving quantum walkers through a finite connected network without requiring global knowledge of the graph. We frame the multi-walker problem as a finite quantum cellular automaton where each vertex holds a walker at all times. These walkers will never collide as their vertex position is superpositioned by the network’s evolution and at each time step their positions update by conditioning swaps on quantum coins and partial comparators of the neighboring states. This model generates strong entanglement between vertex states providing a path toward structure independent diffusion driven by highly localized computation. We will examine some mathematical structures underlying state diffusion on arbitrary graphs such as the commutativity of operations and expected time for walkers to reach specified destinations.
Quantum walks have frequently envisioned the behavior of a quantum state traversing a classically defined, generally finite, graph structure. While this approach has already generated significant results, it imposes a strong assumption: all nodes where the walker is not positioned are quiescent. This paper will examine some mathematical structures that underlie state diffusion on arbitrary graphs, that is the circulation of states within a graph. We will seek to frame the multi-walker problem as a finite quantum cellular automaton. Every vertex holds a walker at all times. The walkers will never collide and at each time step their positions update non-deterministically by a quantum swap of walkers at opposite ends of a randomly chosen edge. The update is accomplished by a unitary transformation of the position of a walker to a superposition of all such possible swaps and then performing a quantum measurement on the superposition of possible swaps. This behavior generates strong entanglement between vertex states which provides a path toward developing local actions producing diffusion throughout the graph without depending on the specific structure of the graph through blind computation.
Quantum walks are the quantum-mechanical analog of random walks, in which a quantum ``walker'' evolves between initial and final states by traversing the edges of a graph, either in discrete steps from node to node or via continuous evolution under the Hamiltonian furnished by the adjacency matrix of the graph. We present a hybrid scheme for universal quantum computation in which a quantum walker takes discrete steps of continuous evolution. This ``discontinuous'' quantum walk employs perfect quantum-state transfer between two nodes of specific subgraphs chosen to implement a universal gate set, thereby ensuring unitary evolution without requiring the introduction of an ancillary coin space. The run time is linear in the number of simulated qubits and gates. The scheme allows multiple runs of the algorithm to be executed almost simultaneously by starting walkers one time step apart.
This paper explores the application of quantum walk algorithms to graph traversal and search problems. Classical algorithms often struggle with the computational complexity of traversing and searching large graphs, leading to significant time and resource limitations. Quantum walks, utilizing superposition and interference, offer a potential pathway to achieve exponential speedups. This work details the theoretical framework for applying quantum walks to graph problems, specifically focusing on traversal and search tasks. We present a generalized approach for mapping graph structures onto quantum walk systems and discuss the key mathematical formulations involved. The core of our investigation revolves around the construction of quantum walk operators that mimic the movement and interaction rules inherent in graph traversal. We analyze the evolution of the quantum walk state and derive expressions for the probability of reaching a specific node in the graph. Furthermore, we examine the impact of graph topology on the performance of the quantum walk, highlighting the potential for tailored algorithms to exploit specific graph structures. The results demonstrate the theoretical feasibility of quantum walk algorithms for significantly accelerating graph traversal and search operations, contributing to advancements in areas such as network analysis, database management, and artificial intelligence.
The development of Graph Neural Networks (GNNs) has led to great progress in machine learning on graph-structured data. These networks operate via diffusing information across the graph nodes while capturing the structure of the graph. Recently there has also seen tremendous progress in quantum computing techniques. In this work, we explore applications of multi-particle quantum walks on diffusing information across graphs. Our model is based on learning the operators that govern the dynamics of quantum random walkers on graphs. We demonstrate the effectiveness of our method on classification and regression tasks.
We explore a discrete-time, coined quantum walk on a quantum network where the coherent superposition of walker moves originates from the unitary interaction of the walker coin with the qubit degrees of freedom in the quantum network. The walk dynamics leads to a growth of entanglement between the walker and the network on one hand and, on the other, between the network qubits among themselves. The initial entanglement among the network qubits plays a crucial role in determining the asymptotic values of these entanglement measures and the quantum walk statistics. Specifically, the entanglement entropy of the walker-network state and the negativity of the quantum network-qubit state saturate to values increasing with the initial network entanglement. The asymptotic time-averaged walker-position probability distribution shows increasing localization around the initial walker position with higher initial network entanglement. A potential application of these results as a characterization tool for quantum network properties is suggested.
Random walks are a powerful tool for the efficient implementation of algorithms in classical computation. Their quantum-mechanical analogues, called quantum walks, hold similar promise. Quantum walks provide a model of quantum computation that has recently been shown to be equivalent in power to the standard circuit model. As in the classical case, quantum walks take place on graphs and can undergo discrete or continuous evolution, though quantum evolution is unitary and therefore deterministic until a measurement is made. This thesis considers the usefulness of continuous-time quantum walks to quantum computation from the perspectives of both their fundamental power under various formulations, and their applicability in practical experiments. In one extant scheme, logical gates are effected by scattering processes. The results of an exhaustive search for single-qubit operations in this model are presented. It is shown that the number of distinct operations increases exponentially with the number of vertices in the scattering graph. A catalogue of all graphs on up to nine vertices that implement single-qubit unitaries at a specific set of momenta is included in an appendix. I develop a novel scheme for universal quantum computation called the discontinuous quantum walk, in which a continuous-time quantum walker takes discrete steps of evolution via perfect quantum state transfer through small `widget' graphs. The discontinuous quantum-walk scheme requires an exponentially sized graph, as do prior discrete and continuous schemes. To eliminate the inefficient vertex resource requirement, a computation scheme based on multiple discontinuous walkers is presented. In this model, n interacting walkers inhabiting a graph with 2n vertices can implement an arbitrary quantum computation on an input of length n, an exponential savings over previous universal quantum walk schemes. This is the first quantum walk scheme that allows for the application of quantum error correction. The many-particle quantum walk can be viewed as a single quantum walk undergoing perfect state transfer on a larger weighted graph, obtained via equitable partitioning. I extend this formalism to non-simple graphs. Examples of the application of equitable partitioning to the analysis of quantum walks and many-particle quantum systems are discussed.