Path Integral Quantum Annealing Optimizations Validated on 0-1 Multidimensional Knapsack Problem
IEEE Transactions on Emerging Topics in Computing · 2025-07 · 13 (3) · 1272-1284
DOI: 10.1109/tetc.2025.3583224 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Emerging Topics in Computing, 2025-07. Verfasst von Evelina Forno und 4 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 45 Literaturangaben. Gefördert von: European Union - NextGenerationEU Project 3A-ITALY MICS, Fluently project, Italian National Recovery and Resilience Plan.
Abstract (Originalsprache)
Quantum Annealing (QA) is a metaheuristic designed to enhance Simulated Annealing by leveraging concepts from quantum mechanics, improving parallelization on classical computers. Studies have shown promising results for this technique in the field of NP-hard problems and constrained optimization. In this article, we examine Path Integral Quantum Annealing (PIQA), a well-known technique for simulating QA on conventional computers. We then propose optimizations to the algorithm, offering hardware software developers a suite of parallelization techniques evaluated for their effectiveness in enhancing quality and speed. The proposed approach encompasses four distinct degrees of optimization, leveraging techniques based on multiple-trial parallelism and a novel pre-optimization method. The article further proposes a methodology for handling multiple instances within the search space, whereby problem data is replicated into slices and allocated to concurrent processes during the simulation. Through empirical trials, we evaluate the impact of our optimization techniques on the convergence speed of the algorithm compared to unoptimized PIQA, using the Multidimensional Knapsack Problem as a benchmark. Our findings show that these optimizations, applied individually or collectively, enable the algorithm to achieve equal or superior results with fewer simulation steps. Overall, the results highlight the potential for future implementations of optimized PIQA on dedicated hardware.
Förderung
- European Union - NextGenerationEU Project 3A-ITALY MICS
- Fluently project
- Italian National Recovery and Resilience Plan
- European Union – NextGenerationEU
- EBRAINS-Italy
Zitieren
APA
Forno, E., Pignari, R., Fra, V., Macii, E., & Urgese, G. (2025). Path Integral Quantum Annealing Optimizations Validated on 0-1 Multidimensional Knapsack Problem. IEEE Transactions on Emerging Topics in Computing, 13(3), 1272-1284. https://doi.org/10.1109/tetc.2025.3583224
Vancouver
Forno E, Pignari R, Fra V, Macii E, Urgese G. Path Integral Quantum Annealing Optimizations Validated on 0-1 Multidimensional Knapsack Problem. IEEE Transactions on Emerging Topics in Computing. 2025;13(3):1272-1284. doi:10.1109/tetc.2025.3583224
BibTeX
@article{Forno2025,
author = {Forno, Evelina and Pignari, Riccardo and Fra, Vittorio and Macii, Enrico and Urgese, Gianvito},
title = {Path Integral Quantum Annealing Optimizations Validated on 0-1 Multidimensional Knapsack Problem},
journal = {IEEE Transactions on Emerging Topics in Computing},
year = {2025},
volume = {13},
number = {3},
pages = {1272--1284},
doi = {10.1109/tetc.2025.3583224}
}
EUVIMED