In this paper we briefly define distance vector routing algorithms, their advantages and possible drawbacks. On these possible drawbacks, currently widely used methods split horizon and poisoned reverse are defined and compared. The count to infinity problem is specified and classified to be a halting problem, and a proposition stating that entangled states used in quantum computation can be used to handle this problem is examined. Several solutions to this problem by using entangled states are proposed and a very brief introduction to entangled states is presented.
In this paper we briefly define distance vector routing algorithms, their advantages and possible drawbacks. On these possible drawbacks, currently widely used methods split horizon and poisoned reverse are defined and compared. The count to infinity problem is specified and classified to be a halting problem, and a proposition stating that entangled states used in quantum computation can be used to handle this problem is examined. Several solutions to this problem by using entangled states are proposed and a very brief introduction to entangled states is presented.
The basic ideas of quantum computation are introduced by a brief discussion of Bennett (1973, 1982) and Fredkin's (1982, 1997) ideas of reversible computation. After some remarks about Deutsch's (1985) pioneering work on quantum complexity and Shor's (1996) factorisation algorithm, quantum logic gates, qubits and registers are discussed. The role of quantum entanglement is stressed and Grover's (1997) quantum search algorithm described in detail. The paper ends with a review of the current experimental status of quantum computers.
Abstract In this paper, the key challenges (loss due to distance, entanglement routing, multi‐commodities) for the coming quantum internet, relying on entanglement of quantum bits (for short, qubits) on top of an existing network, are analyzed. A unifying framework enabling to compare the various entanglement distribution, purification, and routing protocols published so far is presented. With regard to entanglement routing, the introduction of different time windows will be essential in order to cope efficiently with the main challenges like complex route calculation and fidelity estimation on the one hand, actual entanglement route selection and entangled photon generation on the other hand. For a roll‐out on top of existing transmission networks, all the research publications for the last 20 years start to cover pretty well the global scheme. Nevertheless, open questions remain, like the actual advantage of some task execution prior to the online quantum path selection, or the design of algorithms approximating the multi‐commodities flow optimization problem, or the issue of dealing with a processing time not much longer than the qubit life time.
Entanglement routing in near-term quantum networks consists of choosing the optimal sequence of short-range entanglements to combine through swapping operations to establish end-to-end entanglement between two distant nodes. Similar to traditional routing technologies, a quantum routing protocol uses network information to choose the best paths to satisfy a set of end-to-end entanglement requests. However, in addition to network state information, a quantum routing protocol must also take into account the requested entanglement fidelity, the probabilistic nature of swapping operations, and the short lifetime of entangled states. In this work, we formulate a practical entanglement routing problem and analyze and categorize the main approaches to address it, drawing comparisons to, and inspiration from, classical network routing strategies where applicable. We classify and discuss the studied quantum routing schemes into reactive, proactive, and hybrid routing.
Introduction. The hope of solving the problem of the avalanche-like growth of requirements for computing power, essential for solving complex routing problems and other problems of combinatorial optimization, relies on the latest quantum computers, in the development of which governments and corporations invest multi-billion investments. The article examines modern routing algorithms and performs their analysis and verification, if the authors of the algorithm provided appropriate test programs. The purpose of the article is to review the current state of development in the field of development of routing algorithms for hybrid quantum-classical clouds, analyze them and propose a classification of algorithms. Results. Modern quantum computers (QCs) make it possible to find approximate solutions to some of mathematical problems faster than classical computers. The inaccuracy of the solutions obtained by the QC is a consequence of physical and technological limitations: calculation errors are caused by thermal noise, a small number of computational elements - qubits and connections between them, which requires the decomposition of the problem and the use of heuristic algorithms. The analysis of approaches to the solution of optimization problems on QC allows us to single out: quantum response and variational search of eigenvalues based on quantum logic gates as the general directions of development of the vast majority of algorithms for solving routing problems. The considered algorithms reduce the vehicle routing problem to a quadratic unconstrained binary optimization problem, which is isomorphic to the Hamilton-Ising model. In this form, the problem is suitable for embedding in QC, which finds an approximate solution that has the best statistical reliability or corresponds to the quantum state with the lowest energy. As a separate class, vehicle routing algorithms for classical computers that use quantum computing to accelerate problem solving can be distinguished. For example, neural networks that calculate weighting factors using QC or an ant algorithm that calculates a pheromone trail in a hybrid cloud. It should be mentioned the quantum-inspired algorithms, which are based on software tools for the simulation of QC and the corresponding libraries and allow creating an effective class of algorithms for solving problems of vehicle routing. Conclusions. Combining hardware quantum annealing with a number of software tools for calculating optimization problems for classical computers in a hybrid quantum-classical cloud service allows to obtain advantages in speed and accuracy of some types of complex optimization problems of a commercial scale, in particular, routing vehicles, which is already bringing substantial profits to a number of corporations. Keywords: vehicle routing problem, quantum computer, annealing, combinatorial optimization, traveling salesman problem, clustering, qubit.
The main purpose of this paper is to examine some (potential) applications of quantum computation in AI and to review the interplay between quantum theory and AI. For the readers who are not familiar with quantum computation, a brief introduction to it is provided, and a famous but simple quantum algorithm is introduced so that they can appreciate the power of quantum computation. Also, a (quite personal) survey of quantum computation is presented in order to give the readers a (unbalanced) panorama of the field. The author hopes that this paper will be a useful map for AI researchers who are going to explore further and deeper connections between AI and quantum computation as well as quantum theory although some parts of the map are very rough and other parts are empty, and waiting for the readers to fill in.
Routing and scheduling problems with time windows have long been important optimization problems for logistics and planning. Many classical heuristics and exact methods exist for such problems. However, there are no satisfactory methods for generating routes using quantum computing (QC), for mainly two reasons: inequality constraints, and the trade-off of feasibility and solution quality. Inequality constraints are typically handled using slack variables; and feasible solutions are found by filtering samples. These challenges are amplified in the presence of noise inherent in QC. Here, we propose a greedy algorithm that generates routes by using information from all samples obtained from the quantum computer. By noticing the relationship between qubits in our formulation as a directed acyclic graph (DAG), we designed an algorithm that adaptively constructs a feasible solution. We prove its convergence to a feasible solution, and illustrate its efficacy by solving the Fleet Sizing Vehicle Routing Problem with Time Windows (FSVRPTW). Our computational results show that this method obtains a lower objective value than the current state-of-the-art annealing approaches, both classical and hybrid, for the same amount of time using D-Wave Hybrid Solvers. We also show its robustness to noise on D-Wave Advantage2 through computational results as compared to the filtering approach on DWaveSampler, even when the filtering approach is given a longer annealing time, and a larger sample size.