A Quantum-Search-Aided Dynamic Programming Framework for Pareto Optimal
Routing in Wireless Multihop Networks

D. Alanis, P. Botsinis, Z. Babar, H. V. Nguyen, D. Chandra, S. X. Ng, L. Hanzo

Published:

Wireless Multihop Networks (WMHNs) have to strike a trade-off among diverse
and often conflicting Quality-of-Service (QoS) requirements. The resultant
solutions may be included by the Pareto Front under the concept of Pareto
Optimality. However, the problem of finding all the Pareto-optimal routes in
WMHNs is classified as NP-hard, since the number of legitimate routes increases
exponentially, as the nodes proliferate. Quantum Computing offers an attractive
framework of rendering the Pareto-optimal routing problem tractable. In this
context, a pair of quantum-assisted algorithms have been proposed, namely the
Non-Dominated Quantum Optimization (NDQO) and the Non-Dominated Quantum
Iterative Optimization (NDQIO). However, their complexity is proportional to
$\sqrt{N}$, where $N$ corresponds to the total number of legitimate routes,
thus still failing to find the solutions in "polynomial time". As a remedy, we
devise a dynamic programming framework and propose the so-called Evolutionary
Quantum Pareto Optimization (EQPO) algorithm. We analytically characterize the
complexity imposed by the EQPO algorithm and demonstrate that it succeeds in
solving the Pareto-optimal routing problem in polynomial time. Finally, we
demonstrate by simulations that the EQPO algorithm achieves a complexity
reduction, which is at least an order of magnitude, when compared to its
predecessors, albeit at the cost of a modest heuristic accuracy reduction.