This paper presents quantum bosonic shortest path searching (QBSPS), a natural, practical and highly heuristic physical algorithm for reasoning about the recognition of network structure via quantum dynamics. QBSPS is based on an Anderson-like itinerant bosonic system in which a boson's Green function is used as a navigation pointer for one to accurately approach the terminals. QBSPS is demonstrated by rigorous mathematical and physical proofs and plenty of simulations, showing how it can be used as a greedy routing to seek the shortest path between different locations. In methodology, it is an interesting and new algorithm rooted in the quantum mechanism other than combinatorics. In practice, for the all-pairs shortest-path problem in a random scale-free network with N vertices, QBSPS runs in O (μ( N ) ln ln N ) time. In application, we suggest that the corresponding experimental realizations are feasible by considering path searching in quantum optical communication networks; in this situation, the method performs a pure local search on networks without requiring the global structure that is necessary for current graph algorithms.
This paper presents quantum bosonic shortest path searching (QBSPS), a natural, practical and highly heuristic physical algorithm for reasoning about the recognition of network structure via quantum dynamics. QBSPS is based on an Anderson-like itinerant bosonic system in which a boson's Green function is used as a navigation pointer for one to accurately approach the terminals. QBSPS is demonstrated by rigorous mathematical and physical proofs and plenty of simulations, showing how it can be used as a greedy routing to seek the shortest path between different locations. In methodology, it is an interesting and new algorithm rooted in the quantum mechanism other than combinatorics. In practice, for the all-pairs shortest-path problem in a random scale-free network with N vertices, QBSPS runs in O (μ( N ) ln ln N ) time. In application, we suggest that the corresponding experimental realizations are feasible by considering path searching in quantum optical communication networks; in this situation, the method performs a pure local search on networks without requiring the global structure that is necessary for current graph algorithms.
A fully-quantum network implies the creation of quantum entanglement between a given source node and some other destination node, with a number of quantum repeaters in between. This paper tackles the problem of quantum entanglement distribution by solving the routing problem over an infrastructure based on quantum repeaters and with a finite number of pairs of entangled qubits available in each link. The network model considers that link purification is available such that a nested purification protocol can be applied at each link to generate entangled qubits with higher fidelity than the original ones. A low-complexity multi-objective routing algorithm to find the shortest path between any two given nodes is proposed and assessed for random networks, using a fairly general path extension mechanism that can fit a large family of particular technological requirements. Different types of quantum protocols require different levels of fidelity for the entangled qubit pairs. For that reason, the proposed algorithm identifies the shortest path between two nodes that assures an end-to-end fidelity above a specified threshold. The minimum requirements for the end-to-end entanglement fidelity depend on the whole extension of the paths, and cannot be looked at as a local property of each link. Moreover, one needs to keep track not only of the shortest path, but also of longer paths holding more entangled qubits than the shorter paths in order to satisfy the fidelity criterion. Thus, standard single parameter shortest-path algorithms do not necessarily converge to the optimal solution. The problem of finding the best path in a network subject to multiple criteria (known as multi-objective routing) is, in general, an NP-hard problem due to the rapid growth of the number of stored paths. This work proposes a metric that identifies and discards paths that are objectively worse than others. By doing so, the time complexity of the proposed algorithm scales near-to-linearly with respect to the number of nodes in the network, showing that the shortest-path problem in quantum networks can be solved with a complexity very close to the one of the classical counterparts. That is analytically proved for the case where all the links of a path have the same fidelity (homogeneous model). The algorithm is also adapted to a particular type of path extension, where different links along a path can be purified to different degrees, asserting its flexibility and near-to-linearity even when heterogeneous fidelities along the sections of a path are considered.
Classical algorithms have been used to search over some space for finding the shortest paths problem between two points in a network and a minimal weight spanning tree for routing. Any classical algorithm deterministic or probabilistic will clearly used O(N) steps since on the average it will measure a large fraction of N records. Quantum algorithm is the fastest possible algorithm that can do several operations simultaneously due to their wave like properties. This wave gives an O( N ) steps quantum algorithm for identifying that record, where was used classical Dijkstra’s algorithm for finding shortest path problem in the graph of network and implement quantum search. Also we proposed the structure for non-classical algorithms and design the various phases of the probabilistic quantum-classical algorithm for classical and quantum parts. Finally, we represent the result of implementing and simulating Dijkstra's algorithm as the probabilistic quantum-classical algorithm.
Quantum algorithms run on quantum computers are qualitatively different from those that run on classical computers. Quantum computing algorithms can be used for several problems in graph theory. Most of the classical algorithms involve searching over some space for finding the shortest-paths problem between two points in a graph and a minimal weight spanning tree. We modified classical Dijkstra's algorithm and implement quantum search instead of classical search, of which it will lead to more efficient algorithm. Also we proposed the structure for non-classical algorithms and design the various phases of the probabilistic quantum-classical algorithm for classical and quantum parts. Finally, we represent the result of implementing and simulating Dijkstra's algorithm as the probabilistic quantum-classical algorithm.
Algorithms and data structures are important in information technology (particularly in 6G terahertz wireless communications), logistics, transportation, and route planning in medicine. One of the fundamental algorithms that find application in many practical problems is the shortest path algorithm. The shortest path algorithm is used to find the optimal route between two vertices while minimizing the length or number of intermediate nodes. This problem is one of the 21 NP-hard problems formulated by Richard Karp in 1972. It still poses a serious challenge to science, since there is no polynomial algorithm that can provide an exact solution to this problem. The article considers approaches to solving the problem of finding the shortest path on a graph, and discusses their advantages and disadvantages. Various algorithms, such as the Bellman-Ford algorithm, Dijkstra, and the A* algorithm, are considered; their efficiency and applicability in various situations are analyzed. Issues of optimization of shortest path algorithms are discussed, such as the use of heuristics, graph preprocessing, and other methods that can improve the performance and accuracy of algorithms. The article proposes an optimization of Dijkstra’s algorithm with quantum acceleration. The stability of the quantum algorithm and the magnitude of distortions in a circuit with a different number of qubits are estimated. It is shown that with an increase in the intensity of distortions, the probability of detecting the desired element decreases, and the time spent on its search increases. When using Grover’s algorithm to optimize a path in a quantum network, these interferences cause an increase in the time it takes to find the optimal path and an increase in the probability of choosing an incorrect route. It is shown that an increase in the number of qubits and, accordingly, the number of iterations makes the algorithm more stable. It is demonstrated that the stability of Grover’s algorithm for circuits with a large number of qubits has a similar nature. The work of quantum circuits on 9, 10 and 11 qubits, the difference in the probabilities of correct operation differs by less than 10–3. Thus, from the obtained dependencies, it is possible to predict the nature of such an influence on circuits with an even larger number of qubits, the stability of which cannot be studied due to the insufficient computing power of classical computers. The most efficient way to modify Dijkstra’s algorithm is to replace the priority queue in the classical version of the algorithm with some quantum data structure that finds the minimum element for the next iteration of the algorithm. Despite the fact that quantum search does not provide a potential gain in asymptotics, another quantum modification of Dijkstra’s algorithm can be used. Namely, instead of maintaining and searching for a minimum in the priority queue, use the quantum algorithm immediately to search for a vertex that needs to be added to the shortest path tree, which will additionally acceleration the graph traversal by Dijkstra’s algorithm.
Given an undirected, weighted graph, with n vertices and m edges, and two special vertices s and t, the problem is to find the shortest path between them. We give two bounded-error quantum algorithms with improved runtime in the adjacency list model that solve the problem on special classes of graphs defined via pathfinding probabilities of classical random walks and the electrical network framework. Firstly, we give a simple quantum algorithm based on sampling edges from a graph via the quantum flow state and running a classical algorithm on the sampled edges. It runs in O~(l2m) expected time and uses O(logn) space on graphs where the shortest s-t path is also a minimum resistance s-t subgraph. Our main algorithm can be thought of as a divide and conquer version of this approach and works on a special class of graphs where classical loop-erased random walk has a probability q>0.537 of finding the shortest s-t path. In such cases the quantum algorithm outputs the shortest s-t path with high probability in O(ℓm) expected time and O(logn) space, where l is the length (or total weight, in case of weighted graphs) of the shortest s-t path. This algorithm can be parallelised to O~(lm) circuit depth when using O(llogn) space. With the latter we partially resolve with an affirmative answer the open problem of whether a path between two vertices can be found in the number of steps required to detect it.
This paper investigates the application of quantum walks to routing protocols within wireless networks. Traditional routing algorithms often struggle with efficiency and convergence speed, particularly in dynamic and complex network topologies. We propose a novel approach utilizing quantum walk principles to explore network connectivity and identify optimal routes. Our methodology employs a quantum walk algorithm to simulate network traversal, leveraging quantum superposition and interference to potentially achieve faster convergence and reduced latency compared to classical approaches. The core of the system relies on a discrete-time quantum walk on a graph representing the wireless network, where nodes are the walkers and edges represent communication links. The algorithm aims to minimize the walk length, effectively finding the shortest path between source and destination nodes. We present a theoretical framework and outline the key components of a quantum walk-based routing protocol. While this research focuses on the theoretical aspects and does not include experimental validation, it lays the foundation for future work exploring the practical feasibility and performance benefits of quantum walk routing in real-world wireless network scenarios.