NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization

Loading...
Thumbnail Image
Access rights
openAccess
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
Date
2023
Major/Subject
Mcode
Degree programme
Language
en
Pages
30
1-30
Series
Quantum, Volume 7
Abstract
Quantum algorithms are gaining extreme popularity due to their potential to significantly outperform classical algorithms. Yet, practical applications of quantum algorithms to optimization problems meet challenges related to the efficiency of the existing quantum algorithms training, the shape of their cost landscape, the accuracy of their output, and their ability to scale to large-size problems. Here, we present a gradient-based quantum algorithm for hardware-efficient circuits with amplitude encoding. We show that simple linear constraints can be directly incorporated into the circuit without additional modification of the objective function with penalty terms. We employ numerical simulations to test it on MaxCut problems with complete weighted graphs with thousands of nodes and run the algorithm on a superconducting quantum processor. We find that being applied to unconstrained MaxCut problems with more than 1000 nodes, the hybrid approach combining our algorithm with a classical solver called CPLEX realizes a better solution than the CPLEX alone. This demonstrates that hybrid optimization is one of the leading use cases for modern quantum devices.
Description
Funding Information: We thank Dr. Margarita Veshchezerova, Dr. Alexey Melnikov, Vishal Shete, and Karan Pinto for their valuable discussions and suggestions. Publisher Copyright: © 2023 Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften. All Rights Reserved.
Keywords
Other note
Citation
Perelshtein , M R , Pakhomchik , A I , Melnikov , A A , Podobrii , M , Termanova , A , Kreidich , I , Nuriev , B , Iudin , S , Mansell , C W & Vinokur , V M 2023 , ' NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization ' , Quantum , vol. 7 , pp. 1-30 . https://doi.org/10.22331/q-2023-11-21-1186