Investigating Quantum Approximation Techniques for Tackling NP-Hard Problems in Distributed Systems
DOI:
https://doi.org/10.63846/emqcw506Keywords:
NP-hard problems , quantum approximation algorithms, distributed systems, hybrid quantum-classical computing, quantum speedupAbstract
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.
References
S. Hanif, “Multiagent Coordination and Teamwork: A Case Study for Large-Scale Dynamic Ready-Mixed Concrete Delivery Problem,” Mathematics, vol. 11, no. 19, p. 4124, 2023, doi: 10.3390/math11194124.
P. Kenekayoro and B. Fawei, “Meta-Heuristic Solutions to a Student Grouping Optimization Problem Faced in Higher Education Institutions,” Journal of Advances in Mathematics and Computer Science, pp. 61–74, 2020, doi: 10.9734/jamcs/2020/v35i730304.
A. A. Juan, “Solving NP-Hard Challenges in Logistics and Transportation Under General Uncertainty Scenarios Using Fuzzy Simheuristics,” Algorithms, vol. 16, no. 12, p. 570, 2023, doi: 10.3390/a16120570.
L. Lu, J. Ou, X. Yu, and L. Zhang, “Order Acceptance and Scheduling With Delivery Under Generalized Parameters,” Naval Research Logistics (Nrl), vol. 70, no. 8, pp. 844–857, 2023, doi: 10.1002/nav.22135.
R. Gomes, D. Vieira, and M. Castro, “Application of Meta-Heuristics in 5G Network Slicing: A Systematic Review of the Literature,” Sensors, vol. 22, no. 18, p. 6724, 2022, doi: 10.3390/s22186724.
L. Olivari and G. Đukić, “Current State of Dynamic Vehicle Routing Problems Solved by Ant Colony Optimization Algorithm,” Tehnički Glasnik, vol. 15, no. 3, pp. 429–434, 2021, doi: 10.31803/tg-20210708131104.
F. Mar’i, H. Ubaidillah, W. F. Mahmudy, and A. A. Supianto, “Hybrid Artificial Bee Colony and Improved Simulated Annealing for the Capacitated Vehicle Routing Problem,” Knowledge Engineering and Data Science, vol. 5, no. 2, p. 109, 2022, doi: 10.17977/um018v5i22022p109-121.
S. M. Almufti, R. B. Marqas, P. S. Othman, and A. B. Sallow, “Single-Based and Population-Based Metaheuristics Algorithms Performances in Solving NP-hard Problems,” Iraqi Journal of Science, 2021, doi: 10.24996/10.24996/ijs.2021.62.5.34.
Q. Wang, S. Ji, P. Peng, M. Li, P. Huang, and Z. Qin, “Optimizing Distance Computation in Distributed Graph Systems,” Ieee Access, vol. 8, pp. 191673–191682, 2020, doi: 10.1109/access.2020.3032727.
E. Pelofske, G. Hahn, and H. Djidjev, “Decomposition Algorithms for Solving NP-hard Problems on a Quantum Annealer,” J Signal Process Syst, vol. 93, no. 4, pp. 405–420, 2020, doi: 10.1007/s11265-020-01550-1.
Z. Chen, X. Long, L. Chen, Y. Wu, J. Wu, and S. Liu, “Intra‐cluster Aggregation Aware Routing for Distributed Training in Wireless Sensor Networks,” Concurr Comput, vol. 35, no. 17, 2021, doi: 10.1002/cpe.6795.
C. Qi, J. Xie, and H. Zhang, “Joint Antenna Placement and Power Allocation for Target Detection in a Distributed MIMO Radar Network,” Remote Sens (Basel), vol. 14, no. 11, p. 2650, 2022, doi: 10.3390/rs14112650.
S. Tkatek, S. Bahti, Y. lmezouari, and J. Abouchabaka, “Artificial Intelligence for Improving the Optimization of NP-Hard Problems: A Review,” International Journal of Advanced Trends in Computer Science and Engineering, vol. 9, no. 5, pp. 7411–7420, 2020, doi: 10.30534/ijatcse/2020/73952020.
K. B. Ali, A. J. Telmoudi, and S. Gattoufi, “Improved Genetic Algorithm Approach Based on New Virtual Crossover Operators for Dynamic Job Shop Scheduling,” Ieee Access, vol. 8, pp. 213318–213329, 2020, doi: 10.1109/access.2020.3040345.
S. Yarkoni, E. Raponi, T. Bäck, and S. Schmitt, “Quantum Annealing for Industry Applications: Introduction and Review,” Reports on Progress in Physics, vol. 85, no. 10, p. 104001, 2022, doi: 10.1088/1361-6633/ac8c54.
A.-Y. Rhonda, N. Chancellor, and P. Halffmann, “NP-hard but No Longer Hard to Solve? Using Quantum Computing to Tackle Optimization Problems,” Frontiers in Quantum Science and Technology, vol. 2, 2023, doi: 10.3389/frqst.2023.1128576.
U. F. Siddiqi, S. M. Sait, and M. Uysal, “Deep Q-Learning Based Optimization of VLC Systems With Dynamic Time-Division Multiplexing,” Ieee Access, vol. 8, pp. 120375–120387, 2020, doi: 10.1109/access.2020.3005885.
K. H. Yee, J. Bang, P. M. Alsing, W. A. Miller, and D. Ahn, “Speedup of Grover’s Search Algorithm and Closed Timelike Curves,” Quantum Sci Technol, vol. 5, no. 4, p. 045011, 2020, doi: 10.1088/2058-9565/abae7e.
A. T. Schmitz and S. Johri, “A Quantum Solution for Efficient Use of Symmetries in the Simulation of Many-Body Systems,” npj Quantum Inf, vol. 6, no. 1, 2020, doi: 10.1038/s41534-019-0232-1.
V. Gebhart, L. Pezzé, and A. Smerzi, “Quantifying Computational Advantage of Grover’s Algorithm With the Trace Speed,” Sci Rep, vol. 11, no. 1, 2021, doi: 10.1038/s41598-020-80153-z.
R. Seidel, C. K. Becker, S. Bock, N. Tcholtchev, I.-D. Gheorghe-Pop, and M. Hauswirth, “Automatic Generation of Grover Quantum Oracles for Arbitrary Data Structures,” Quantum Sci Technol, vol. 8, no. 2, p. 025003, 2023, doi: 10.1088/2058-9565/acaf9d.
T. Zhang, “Optimization With Robust Non-Oracular Quantum Search,” Technologies (Basel), vol. 11, no. 5, p. 148, 2023, doi: 10.3390/technologies11050148.
C.-F. Chiang, “Quantum-Walk-Inspired Dynamic Adiabatic Local Search,” Entropy, vol. 25, no. 9, p. 1287, 2023, doi: 10.3390/e25091287.
M. D. Migliore, “Classical and Quantum Processing in the Deep Physical Layer,” Ieee Access, pp. 1–1, 2023, doi: 10.1109/access.2023.3280452.
L. Xu, “Quantum Support Vector Machine for Multi Classification,” Commun Theor Phys, vol. 76, no. 7, p. 075105, 2024, doi: 10.1088/1572-9494/ad48fc.
N. Ishikawa, “Quantum Speedup for Index Modulation,” Ieee Access, vol. 9, pp. 111114–111124, 2021, doi: 10.1109/access.2021.3103207.
Z. Wang, “Comparison of Quantum and Classical Algorithm in Searching a Number in a Database Case,” Highlights in Science Engineering and Technology, vol. 38, pp. 370–376, 2023, doi: 10.54097/hset.v38i.5831.
W. Zhao, Y. Wang, Y. Qu, H. Ma, and S. Wang, “Binary Classification Quantum Neural Network Model Based on Optimized Grover Algorithm,” Entropy, vol. 24, no. 12, p. 1783, 2022, doi: 10.3390/e24121783.
E. Tsai and M. Perkowski, “A Quantum Algorithm for Automata Encoding,” Facta Universitatis - Series Electronics and Energetics, vol. 33, no. 2, pp. 169–215, 2020, doi: 10.2298/fuee2002169t.
S. Lee, “Implementation of Grover’s Iterator for Quantum Searching With an Arbitrary Number of Qubits,” Ieee Access, vol. 12, pp. 43027–43038, 2024, doi: 10.1109/access.2024.3380198.
Y. Yang, K. Jang, A. Baksi, and H. Seo, “Optimized Implementation and Analysis of CHAM in Quantum Computing,” Applied Sciences, vol. 13, no. 8, p. 5156, 2023, doi: 10.3390/app13085156.
N. Innan, “A Variational Quantum Perceptron With Grover’s Algorithm for Efficient Classification,” Phys Scr, vol. 99, no. 5, p. 055120, 2024, doi: 10.1088/1402-4896/ad3e38.
M. Elmasry, A. Younes, I. Elkabani, and A. Elsayed, “Quantum Pattern Classification in a Three-Qubit System,” Symmetry (Basel), vol. 15, no. 4, p. 883, 2023, doi: 10.3390/sym15040883.
H. Sakhouf, M. Daoud, and R. A. Laamara, “Simple Scheme for Implementing the Grover Search Algorithm With Superconducting Qubits,” Journal of Physics B Atomic Molecular and Optical Physics, vol. 54, no. 17, p. 175501, 2021, doi: 10.1088/1361-6455/ac24ad.
K. Jang, “Quantum Implementation of AIM: Aiming for Low-Depth,” Applied Sciences, vol. 14, no. 7, p. 2824, 2024, doi: 10.3390/app14072824.
E. Matwiejew, J. Pye, and J. Wang, “Quantum Optimisation for Continuous Multivariable Functions by a Structured Search,” Quantum Sci Technol, vol. 8, no. 4, p. 045013, 2023, doi: 10.1088/2058-9565/ace6cc.
G. Song et al., “SPEEDY Quantum Circuit for Grover’s Algorithm,” Applied Sciences, vol. 12, no. 14, p. 6870, 2022, doi: 10.3390/app12146870.
M. R. Habibi, S. Golestan, A. Soltanmanesh, J. M. Guerrero, and J. C. Vasquez, “Power and Energy Applications Based on Quantum Computing: The Possible Potentials of Grover’s Algorithm,” Electronics (Basel), vol. 11, no. 18, p. 2919, 2022, doi: 10.3390/electronics11182919.
Z. Chen, T. Qiu, W. Zhang, and H. Ma, “Effects of Initial States on the Quantum Correlations in the Generalized Grover Search Algorithm*,” Chinese Physics B, vol. 30, no. 8, p. 080303, 2021, doi: 10.1088/1674-1056/ac05a9.
A. Wicaksana, A. Anthony, and A. W. Wicaksono, “Web-App Realization of Shor’s Quantum Factoring Algorithm and Grover’s Quantum Search Algorithm,” Telkomnika (Telecommunication Computing Electronics and Control), vol. 18, no. 3, p. 1319, 2020, doi: 10.12928/telkomnika.v18i3.14755.
G. Reinelt, “TSPLIB - A Traveling Salesman Problem Library.,” INFORMS J. Comput., vol. 3, no. 4, pp. 376–384, 1991, [Online]. Available: http://dblp.uni-trier.de/db/journals/informs/informs3.html#Reinelt91
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Chandra Yogatama, Randi D. Wibisono
This work is licensed under a Creative Commons Attribution 4.0 International License.
