Quantum computers have the potential to solve Quadratic Unconstrained Binary Optimization (QUBO) problems with lower computational complexity than classical ones. Considering the current limitations of quantum hardware, the joint use of classical and quantum paradigms could exploit both advantages. Quantum routines can make some complex tasks for classical computers feasible. For example, in the Grover Adaptive Search (GAS) procedure, the problem cost function is classically shifted iteratively, whenever a negative value is found through the quantum Grover Search (GS) algorithm, until the minimum is achieved. This quantum-classical approach is characterized by many degrees of freedom, e.g. the number of GS iterations in each call and the stop condition of the algorithm, which should be appropriately tuned for an effective and fast convergence to the optimal solution. The availability of software routines could permit the best management of the GAS parameters. This work proposes new mechanisms for GAS parameters management and compares them with the existing ones, like one available in the Qiskit framework. The proposed mechanisms can automatically arrange the parameters according to the algorithm evolution and their previous experience, thus ensuring a more frequent and faster achievement of the optimal solution. Even though these strategies can be further improved, the results are encouraging. The analysis is done to identify the best policy for different problems. It lays the foundation for designing an automatic toolchain for QUBO solving, which can obtain the best possible implementation of the GAS algorithm for each submitted problem.
Engineering Grover Adaptive Search: Exploring the Degrees of Freedom for Efficient QUBO Solving / Giuffrida, L.; Volpe, D.; Cirillo, G. A.; Zamboni, M.; Turvani, G.. - In: IEEE JOURNAL ON EMERGING AND SELECTED TOPICS IN CIRCUITS AND SYSTEMS. - ISSN 2156-3365. - STAMPA. - 12:3(2022), pp. 614-623. [10.1109/JETCAS.2022.3202566]
Engineering Grover Adaptive Search: Exploring the Degrees of Freedom for Efficient QUBO Solving
Giuffrida L.;Volpe D.;Cirillo G. A.;Zamboni M.;Turvani G.
2022
Abstract
Quantum computers have the potential to solve Quadratic Unconstrained Binary Optimization (QUBO) problems with lower computational complexity than classical ones. Considering the current limitations of quantum hardware, the joint use of classical and quantum paradigms could exploit both advantages. Quantum routines can make some complex tasks for classical computers feasible. For example, in the Grover Adaptive Search (GAS) procedure, the problem cost function is classically shifted iteratively, whenever a negative value is found through the quantum Grover Search (GS) algorithm, until the minimum is achieved. This quantum-classical approach is characterized by many degrees of freedom, e.g. the number of GS iterations in each call and the stop condition of the algorithm, which should be appropriately tuned for an effective and fast convergence to the optimal solution. The availability of software routines could permit the best management of the GAS parameters. This work proposes new mechanisms for GAS parameters management and compares them with the existing ones, like one available in the Qiskit framework. The proposed mechanisms can automatically arrange the parameters according to the algorithm evolution and their previous experience, thus ensuring a more frequent and faster achievement of the optimal solution. Even though these strategies can be further improved, the results are encouraging. The analysis is done to identify the best policy for different problems. It lays the foundation for designing an automatic toolchain for QUBO solving, which can obtain the best possible implementation of the GAS algorithm for each submitted problem.File | Dimensione | Formato | |
---|---|---|---|
IEEE_2022___Giuffrida_Final_Source_files.pdf
accesso aperto
Descrizione: Pre print EARLY ACCESS
Tipologia:
2. Post-print / Author's Accepted Manuscript
Licenza:
Pubblico - Tutti i diritti riservati
Dimensione
3.09 MB
Formato
Adobe PDF
|
3.09 MB | Adobe PDF | Visualizza/Apri |
Turvani-Engineering.pdf
accesso riservato
Tipologia:
2a Post-print versione editoriale / Version of Record
Licenza:
Non Pubblico - Accesso privato/ristretto
Dimensione
1.57 MB
Formato
Adobe PDF
|
1.57 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2971802