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

Waves in Random Media

Quantum graphs special section

Published Jan 1, 2004• 0 citations
Publisher
DOI
10.1088/0959-7174/14/1/006

Related papers

Quantum searches on highly symmetric graphs

Daniel Reitzner, Mark S. Hillery, Edgar Feldman +1 more

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.1237•Physical Review A•Jan 26, 2009•73 citations

Quantum graphs

Theoretical and mathematical physics•Sep 22, 2008•0 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.

arXiv:2510.16784•Oct 19, 2025•2 citations

Quantum Private Information Retrieval on Forests

Mohamed Nomeir, Sennur Ulukus

We consider the problem of graph private information retrieval (PIR) in the quantum setting. We focus on a specific type of graphs, namely the forest graphs. A forest graph is a union of disjoint trees. We consider the quantum setting where all the servers share an entangled state. Each server is allowed to send only one qudit per retrieval round. We design a scheme for the forest graphs that achieves the rate of $\frac{3}{N}$. The scheme uses a GHZ state as the initial entangled state between the servers prior to the scheme initiation. We compare our scheme with the only work done in the literature that considered the quantum setting of graph PIR. We show that our scheme is more efficient in this setting. We derive the quantum capacity for the case of $G=3K_2$, which is equal to $4/6$. $G=3K_2$ is a special case of the forest graph. We design a scheme that is specialized for this graph, achieving a rate equal to $4/6$ and provide the corresponding matching upper bound, establishing it as the capacity.

cs.ITCross-listedarXiv:2611.03558•Nov 3, 2026•0 citations

Quantum graphs

Peter Kuchment

Waves in Random Media•Jan 1, 2004•12 citations

Basics of Quantum Graphs

Sovan Samanta, Antonios Kalampakas, Tofigh Allahviranloo

Studies in computational intelligence•Jan 1, 2025•0 citations
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 MMM-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.
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 KNK^{N}KN to KN+m2K^{\frac{N+m}{2}}K2N+m​ upon one symmetric reduction of graphs symmetric about an axis passing through mmm nodes, where KKK 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 δCq=9N28−3m28−3Nm4−N4+m4δC_q= \frac{9N^2}{8}-\frac{3m^2}{8}-\frac{3Nm}{4}-\frac{N}{4}+\frac{m}{4}δCq​=89N2​−83m2​−43Nm​−4N​+4m​ upon one symmetric reduction of graphs, symmetric about an axis passing through mmm 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.9575N)O(1.9575^{N})O(1.9575N) to O(1.9575(N+m2))O(1.9575^{(\frac{N+m}{2})})O(1.9575(2N+m​)) upon one symmetric reduction of graphs symmetric about an axis passing through mmm nodes and similarly for others cases.
We consider the problem of graph private information retrieval (PIR) in the quantum setting. We focus on a specific type of graphs, namely the forest graphs. A forest graph is a union of disjoint trees. We consider the quantum setting where all the servers share an entangled state. Each server is allowed to send only one qudit per retrieval round. We design a scheme for the forest graphs that achieves the rate of 3N\frac{3}{N}N3​. The scheme uses a GHZ state as the initial entangled state between the servers prior to the scheme initiation. We compare our scheme with the only work done in the literature that considered the quantum setting of graph PIR. We show that our scheme is more efficient in this setting. We derive the quantum capacity for the case of G=3K2G=3K_2G=3K2​, which is equal to 4/64/64/6. G=3K2G=3K_2G=3K2​ is a special case of the forest graph. We design a scheme that is specialized for this graph, achieving a rate equal to 4/64/64/6 and provide the corresponding matching upper bound, establishing it as the capacity.