We study scattering quantum walks on highly symmetric graphs and use the walks to solve search problems on these graphs. The particle making the walk resides on the edges of the graph, and at each time step scatters at the vertices. All of the vertices have the same scattering properties except for a subset of special vertices. The object of the search is to find a special vertex. A quantum circuit implementation of these walks is presented in which the set of special vertices is specified by a quantum oracle. We consider the complete graph, a complete bipartite graph, and an $M$ -partite graph. In all cases, the dimension of the Hilbert space in which the time evolution of the walk takes place is small (between three and six), so the walks can be completely analyzed analytically. Such dimensional reduction is due to the fact that these graphs have large automorphism groups. We find the usual quadratic quantum speedups in all cases considered.We study scattering quantum walks on highly symmetric graphs and use the walks to solve search problems on these graphs. The particle making the walk resides on the edges of the graph, and at each time step scatters at the vertices. All of the vertices have the same scattering properties except for a subset of special vertices. The object of the search is to find a special vertex. A quantum circuit implementation of these walks is presented in which the set of special vertices is specified by a quantum oracle. We consider the complete graph, a complete bipartite graph, and an $M$-partite graph. In all cases, the dimension of the Hilbert space in which the time evolution of the walk takes place is small (between three and six), so the walks can be completely analyzed analytically. Such dimensional reduction is due to the fact that these graphs have large automorphism groups. We find the usual quadratic quantum speedups in all cases considered.

arXiv:0805.1237Physical Review AJan 26, 200972 citations

Quantum graphs

Peter Kuchment

Waves in Random MediaJan 1, 200411 citations

Quantum graphs

Theoretical and mathematical physicsSep 22, 20080 citations

Symmetric Reduction Techniques for Quantum Graph Colouring

Lord Sen, Shyamapada Mukherjee

This paper introduces an efficient quantum computing method for reducing special graphs in the context of the graph coloring problem. The special graphs considered include both symmetric and non-symmetric graphs where the axis passes through nodes only, edges only, and both together. The presented method reduces the number of coloring matrices, which is important for realization of the number of quantum states required, from $K^{N}$ to $K^{\frac{N+m}{2}}$ upon one symmetric reduction of graphs symmetric about an axis passing through $m$ nodes, where $K$ is the number of colours required and \emph{N} being total number of nodes. Similarly for other types also, the number of quantum states is reduced. The complexity in the number of qubits has been reduced by $δC_q= \frac{9N^2}{8}-\frac{3m^2}{8}-\frac{3Nm}{4}-\frac{N}{4}+\frac{m}{4}$ upon one symmetric reduction of graphs, symmetric about an axis passing through $m$ nodes and other types as presented in the paper. Additionally, the number of gates and number of iterations are reduced massively compared to state-of-the-art quantum algorithms. Like for a graph with 20 nodes and symmetric line passing through 2 nodes, the number of iterations decreased from 5157 to 67. Therefore, the procedure presented for solving the graph coloring problem now requires a significantly reduced number of qubits compared to before. The run time of the proposed algorithm for these special type of graphs are reduced from $O(1.9575^{N})$ to $O(1.9575^{(\frac{N+m}{2})})$ upon one symmetric reduction of graphs symmetric about an axis passing through $m$ nodes and similarly for others cases.This paper introduces an efficient quantum computing method for reducing special graphs in the context of the graph coloring problem. The special graphs considered include both symmetric and non-symmetric graphs where the axis passes through nodes only, edges only, and both together. The presented method reduces the number of coloring matrices, which is important for realization of the number of quantum states required, from $K^{N}$ to $K^{\frac{N+m}{2}}$ upon one symmetric reduction of graphs symmetric about an axis passing through $m$ nodes, where $K$ is the number of colours required and \emph{N} being total number of nodes. Similarly for other types also, the number of quantum states is reduced. The complexity in the number of qubits has been reduced by $δC_q= \frac{9N^2}{8}-\frac{3m^2}{8}-\frac{3Nm}{4}-\frac{N}{4}+\frac{m}{4}$ upon one symmetric reduction of graphs, symmetric about an axis passing through $m$ nodes and other types as presented in the paper. Additionally, the number of gates and number of iterations are reduced massively compared to state-of-the-art quantum algorithms. Like for a graph with 20 nodes and symmetric line passing through 2 nodes, the number of iterations decreased from 5157 to 67. Therefore, the procedure presented for solving the graph coloring problem now requires a significantly reduced number of qubits compared to before. The run time of the proposed algorithm for these special type of graphs are reduced from $O(1.9575^{N})$ to $O(1.9575^{(\frac{N+m}{2})})$ upon one symmetric reduction of graphs symmetric about an axis passing through $m$ nodes and similarly for others cases.

arXiv:2510.16784Oct 19, 20250 citations

Basics of Quantum Graphs

Sovan Samanta, Antonios Kalampakas, Tofigh Allahviranloo

Studies in computational intelligenceJan 1, 20250 citations

Quantum-Inspired Hardware Acceleration for Graph Algorithms

Jincheng Zhang

This paper explores the potential of quantum-inspired hardware acceleration for graph algorithms. Traditional hardware acceleration techniques often struggle to efficiently exploit the inherent parallelism within graph computations. We propose a novel approach leveraging concepts from quantum mechanics, specifically superposition and entanglement, to design specialized hardware architectures. This approach aims to achieve significant performance improvements by enabling parallel processing and optimized data movement within graph algorithms. The core claim is that specialized hardware, inspired by quantum principles, can dramatically speed up graph algorithms. This research investigates the feasibility and potential impact of such designs, paving the way for future advancements in graph processing. The presented methodology focuses on architectural design and performance estimation, without requiring experimental validation.This paper explores the potential of quantum-inspired hardware acceleration for graph algorithms. Traditional hardware acceleration techniques often struggle to efficiently exploit the inherent parallelism within graph computations. We propose a novel approach leveraging concepts from quantum mechanics, specifically superposition and entanglement, to design specialized hardware architectures. This approach aims to achieve significant performance improvements by enabling parallel processing and optimized data movement within graph algorithms. The core claim is that specialized hardware, inspired by quantum principles, can dramatically speed up graph algorithms. This research investigates the feasibility and potential impact of such designs, paving the way for future advancements in graph processing. The presented methodology focuses on architectural design and performance estimation, without requiring experimental validation.

Aug 29, 20260 citations

M

-partite graph. In all cases, the dimension of the Hilbert space in which the time evolution of the walk takes place is small (between three and six), so the walks can be completely analyzed analytically. Such dimensional reduction is due to the fact that these graphs have large automorphism groups. We find the usual quadratic quantum speedups in all cases considered.

K^{N}

K^{\frac{N+m}{2}}

upon one symmetric reduction of graphs symmetric about an axis passing through

m

nodes, where

K

is the number of colours required and \emph{N} being total number of nodes. Similarly for other types also, the number of quantum states is reduced. The complexity in the number of qubits has been reduced by

δC_q= \frac{9N^2}{8}-\frac{3m^2}{8}-\frac{3Nm}{4}-\frac{N}{4}+\frac{m}{4}

upon one symmetric reduction of graphs, symmetric about an axis passing through

m

nodes and other types as presented in the paper. Additionally, the number of gates and number of iterations are reduced massively compared to state-of-the-art quantum algorithms. Like for a graph with 20 nodes and symmetric line passing through 2 nodes, the number of iterations decreased from 5157 to 67. Therefore, the procedure presented for solving the graph coloring problem now requires a significantly reduced number of qubits compared to before. The run time of the proposed algorithm for these special type of graphs are reduced from

O(1.9575^{N})

O(1.9575^{(\frac{N+m}{2})})

upon one symmetric reduction of graphs symmetric about an axis passing through

m

nodes and similarly for others cases.