This blog is directed at quantum enthusiasts and professionals.
The most famous combinatorial problem today is known as the Traveling Salesman Problem (TSP) which seeks to find the minimum tour length among a group of nodes, with each node visited only once. A feature unique to TSPs, requires the tour to end at same location the tour started. Thus, the objective of the TSP is to calculate the distance between nodes, or pair of nodes, in order to determine the shortest roundtrip distance between the starting node and the goal node, and back again.
The TSP is classified as a NP-hard problem. These are a class of problems incapable of being solved in polynomial time by a non-deterministic Turing machine. In layman’s terms, a NP-hard problem is simply any problem that is very difficult or impossible for a classical computer to solve. TSP is considered a NP-hard problem due to the fact that the number of potential routes scales by several orders of magnitude, as the number of nodes (think cities, streets, houses, etc.) increases.
Logistics and path planning are common TSPs, and present very real problems for the telecom industry, working on 5G and 6G wireless communication problems. Likewise, transportation companies working with logistics and inspections also deal with TSPs on a routine basis. Additionally, search and rescue operations in disaster zones have also emerged as an unexpected TSP.
One of the most difficult logistic routing problems to solve are Inventory Routing Problems (IRP), where a proper vehicle selection is made, based on the economics of balancing inventory and transportation costs against environmental impacts. IRB problems must determine the shortest route between n cities, which requires a comparison of (n-1) total permutation vectors. This presents a very difficult problem to solve for classical computer systems. For instance, it would take several years for a modern computer to determine the optimal path for a TSP matrix comprised of 60 nodes.
Optimal path selection for a large number of nodes is a complex problem to solve, though achievable upon converting it to TSP. For instance, every year the U.S. Postal Service (USPS) routes over 150 billion pieces of mail globally. Conventional nearest-neighbor machine learning algorithms are employed to recognize handwriting in order to determine the recipient’s mailing address. The sheer magnitude of this TSP matrix complexity induces a computationally expensive framework that would benefit from the next-generation of Quantum Computers (QCs). Quantum computing technology would reduce TSP’s nearest-neighbor query complexity polynomially.
Currently, researchers employ heuristic and metaheuristic techniques when attempting to solve difficult TSP path optimization problems. Although precise solutions are not guaranteed by metaheuristics, optimal results are approximated with incredible accuracy. This is done by using Asymmetric TSPs (ATSP), where the goal is obtaining the minimum sum of the weights of all edges in a fully-connected directed graph. The most common graph algorithm for optimizing the type of enumerations required for TSP is the branch-and-bound Method.
In turn, novel Bounded-Error Quantum Polynomial-Time (BQP) techniques have shown promise for solving NP-hard max and min bisection problems using QCs. Here, graph theory describes an undirected graph bisection problem, explaining that a max-bisection problem divides vertices into two subsets of the same size, in order to maximize the number of edges between subsets. Conversely, the min-bisection problem minimizes the number of edges in the graph subsets.
QCs are not ideal for solving combinatorial optimization problems. That said, NP-hard problems like TSP, do achieve poly-time constant-space performance enhancements using QC. This can speed up the quadratic searches integral to TSP and other non-BQP, NP Complete (NP-C, a NP-hard problem that is quickly solved) problems. Still, while QC’s are expected to add value to combinatorial NP-hard problems, like TSP by expediting the execution phase; they are not expected to benefit the NP-C problem.
Based on what little we know about quantum computing at this point, researchers theorize that QC’s unique ability for subatomic particles to be in more than one state at any given time, a phenomenon known as quantum superposition, makes the technology likely to excel at solving BQP, or conjecture-based decisioning problems. What do these BQP problems look like? Good question. No one really knows yet since BQP problems present problems that hard, if not impossible, for classical computers to locate or verify.
References
Bordihn, H., Nagy, B., Vaszil, G., Dimitrijevs, M., & Yakaryilmaz, A. (2018). Uncountable classical and quantum complexity classes. https://search-proquest-com.proxy1.ncu.edu/docview/2196544053?accountid=28180
Clay Mathematics Institute. (n.d.) P vs NP Problem, Millinium Problems. https://www.claymath.org/millennium-problems/p-vs-np-problem
Cook, S. (n.d.) The P Versus NP Problem. https://www.claymath.org/sites/default/files/pvsnp.pdf
Hou, Y., Zhao, X., Li, Q., Chen, J., Li, Y., & Zheng, Z. (2019). Solving Large-Scale NP-Complete Problem with an Optical Solver Driven by a Dual-Comb ‘Clock.’ https://ieeexplore-ieee-org.proxy1.ncu.edu/stamp/stamp.jsp?tp=&arnumber=8749317
Jaradat, A., Matalkeh, B., & Diabat, W. (2019). Solving Traveling Salesman Problem using Firefly Algorithm and K-means Clustering. https://ieeexplore-ieee-org.proxy1.ncu.edu/stamp/stamp.jsp?tp=&arnumber=8717463
Jeganathan, S. (2017). Opportunities and Threats: Part 1: An Overview, Promises, and Introduction to Quantum Cryptography. https://eds-b-ebscohost-com.proxy1.ncu.edu/eds/pdfviewer/pdfviewer?vid=17&sid=9ef42423-10cb-402b-8242-6e8844da0123%40pdc-v-sessmgr05
Patterson, M. & Friesen, D. (2019). Variants of the Traveling Salesman Problem. https://eds-b-ebscohost-com.proxy1.ncu.edu/eds/pdfviewer/pdfviewer?vid=3&sid=9ef42423-10cb-402b-8242-6e8844da0123%40pdc-v-sessmgr05
Wallden, P. & Kashefi, E. (2019). Cyber Security in the Quantum Era. https://eds-a-ebscohost-com.proxy1.ncu.edu/eds/pdfviewer/pdfviewer?vid=10&sid=28232b4a-f18b-4dbc-a923-cedc9ea23406%40sdc-v-sessmgr01
Wiebe, N., Kapoor, A., Svore, K. (2014). Quantum Algorithms for Nearest-Neighbor Methods for Supervised and Unsupervised Learning. https://arxiv.org/pdf/1401.2142.pdf
Xu, Y., & Che, C. (2019). A Brief Review of the Intelligent Algorithm for Traveling Salesman Problem in UAV Route Planning. https://ieeexplore-ieee-org.proxy1.ncu.edu/stamp/stamp.jsp?tp=&arnumber=8784651