Accelerating NP-Hard Optimization via Quantum-Inspired Classical Algorithms

Abstract

A primary challenge of computational science is solving NP-hard optimization problems since they are too complicated and cannot be effectively solved deterministically in large instances. Even though quantum computing can solve these problems with the help of its key properties quantum parallelism and tunneling, the modern hardware is yet not sufficiently developed. In this case, QICAs are considered as a new method in which the key aspects of quantum mechanics, such as superposition, entanglement, interference and tunneling are replicated in classical, non-quantum computers. It aims to attain rapid optimization of NP-hard problems through a hybrid approach that combines cartography-based exploration, variable state reduction with tensor networks as well as an inclusion of a variant-based approach inspired by QAOA. A number of standard problems are used to test the model, e.g., the Traveling Salesman Problem (TSP), the 0/1 Knapsack Problem and Max-Cut Problem. Genetic Algorithms, Simulated Annealing and Ant Colony Optimization trials all concur that QICA converges to superior solutions much faster and it can nonetheless handle bigger-sized problems. More precisely, the algorithm provides better approximation results as well as lesser computing power requirements, thus demonstrating the effectiveness of quantum-inspired methods in the case of classical systems. They establish the fact that QICAs have the potential to solve challenging optimization problems, particularly in the cases where quantum machines are absent or inaccessible. The way of solving the problem represented in the study is quite innovative and serves as a bridge between the theory of quantum and practical implementation in the optimization field.