Investigating Quantum Approximation Techniques for Tackling NP-Hard Problems in Distributed Systems
Chandra Yogatama, Randi Dwi Wibisono · ALCOM Journal of Algorithm and Computing · 2025
The resolution of NP-hard problems, including the traveling salesman problem and graph coloring, continues to be a major hurdle in computational science. While traditional algorithms are effective for smaller problems, they often require excessive computational resources for larger instances. Distributed systems present a potential remedy by harnessing parallelism, but they encounter inherent obstacles such as latency and synchronization overhead. Quantum computing emerges as a promising alternative with its potential for exponential speedups, yet it faces practical constraints like noise and scalability issues. This research investigates quantum approximation algorithms for tackling NP-hard problems in distributed systems, with an emphasis on hybrid quantum-classical methodologies. By crafting approximation techniques specifically for distributed environments and suggesting innovative approaches to incorporate quantum nodes into a distributed system, this study aims to surmount current limitations and lay the groundwork for scalable quantum-assisted problem-solving. The proposed methods undergo evaluation through theoretical analysis and experimental simulations, showcasing their capacity to address computational bottlenecks in distributed systems.