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.
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
KN to
K2N+m 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
δCq=89N2−83m2−43Nm−4N+4m 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.9575N) to
O(1.9575(2N+m)) upon one symmetric reduction of graphs symmetric about an axis passing through
m 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
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=3K2, which is equal to
4/6.
G=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/6 and provide the corresponding matching upper bound, establishing it as the capacity.