Quantum Annealing (QA) is an emerging technique, derived from Simulated Annealing, providing metaheuristics for multivariable optimisation problems. Studies have shown that it can be applied to solve NP-hard problems with faster convergence and better quality of result than other traditional heuristics, with potential applications in a variety of fields, from transport logistics to circuit synthesis and optimisation. In this paper, we present a hardware architecture implementing a QA-based solver for the Multidimensional Knapsack Problem, designed to improve the performance of the algorithm by exploiting parallelised computation. We synthesised the architecture using as a target an Altera FPGA board and simulated the execution for solving a set of benchmarks available in the literature. Simulation results show that the proposed implementation is about 100 times faster than a single-thread general-purpose CPU without impact on the accuracy of the solution.
A Parallel Hardware Architecture For Quantum Annealing Algorithm Acceleration / Forno, Evelina; Acquaviva, Andrea; Yuki, Kobayashi; Macii, Enrico; Urgese, Gianvito. - ELETTRONICO. - (2018). ((Intervento presentato al convegno IFIP/IEEE International Conference on Very Large Scale Integration (VLSI-SoC 2018) tenutosi a Verona nel 8-10 October 2018.
Titolo: | A Parallel Hardware Architecture For Quantum Annealing Algorithm Acceleration |
Autori: | |
Data di pubblicazione: | 2018 |
Abstract: | Quantum Annealing (QA) is an emerging technique, derived from Simulated Annealing, providing meta...heuristics for multivariable optimisation problems. Studies have shown that it can be applied to solve NP-hard problems with faster convergence and better quality of result than other traditional heuristics, with potential applications in a variety of fields, from transport logistics to circuit synthesis and optimisation. In this paper, we present a hardware architecture implementing a QA-based solver for the Multidimensional Knapsack Problem, designed to improve the performance of the algorithm by exploiting parallelised computation. We synthesised the architecture using as a target an Altera FPGA board and simulated the execution for solving a set of benchmarks available in the literature. Simulation results show that the proposed implementation is about 100 times faster than a single-thread general-purpose CPU without impact on the accuracy of the solution. |
ISBN: | 978-1-5386-4756-1 |
Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
forno2018parallel_pre_print.pdf | Articolo principale Postprint | 2. Post-print / Author's Accepted Manuscript | PUBBLICO - Tutti i diritti riservati | Visibile a tuttiVisualizza/Apri |
08644777_post_print_editoriale.pdf | Articolo principale | 2a Post-print versione editoriale / Version of Record | Non Pubblico - Accesso privato/ristretto | Administrator Richiedi una copia |
http://hdl.handle.net/11583/2725886