Solving Nonnative Combinatorial Optimization Problems Using Hybrid Quantum–Classical Algorithms
Combinatorial optimization is a challenging problem applicable in a wide range of fields from logistics to finance. Recently, quantum computing has been used to attempt to solve these problems using a range of algorithms, including parameterized quantum circuits, adiabatic protocols, and quantum ann...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2024-01-01
|
| Series: | IEEE Transactions on Quantum Engineering |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10636813/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832584003182395392 |
|---|---|
| author | Jonathan Wurtz Stefan H. Sack Sheng-Tao Wang |
| author_facet | Jonathan Wurtz Stefan H. Sack Sheng-Tao Wang |
| author_sort | Jonathan Wurtz |
| collection | DOAJ |
| description | Combinatorial optimization is a challenging problem applicable in a wide range of fields from logistics to finance. Recently, quantum computing has been used to attempt to solve these problems using a range of algorithms, including parameterized quantum circuits, adiabatic protocols, and quantum annealing. These solutions typically have several challenges: 1) there is little to no performance gain over classical methods; 2) not all constraints and objectives may be efficiently encoded in the quantum ansatz; and 3) the solution domain of the objective function may not be the same as the bit strings of measurement outcomes. This work presents “nonnative hybrid algorithms”: a framework to overcome these challenges by integrating quantum and classical resources with a hybrid approach. By designing nonnative quantum variational anosatzes that inherit some but not all problem structure, measurement outcomes from the quantum computer can act as a resource to be used by classical routines to indirectly compute optimal solutions, partially overcoming the challenges of contemporary quantum optimization approaches. These methods are demonstrated using a publicly available neutral-atom quantum computer on two simple problems of Max <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-Cut and maximum independent set. We find improvements in solution quality when comparing the hybrid algorithm to its “no quantum” version, a demonstration of a “comparative advantage.” |
| format | Article |
| id | doaj-art-dcf54041139647dfab229e675228eb5c |
| institution | Kabale University |
| issn | 2689-1808 |
| language | English |
| publishDate | 2024-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Transactions on Quantum Engineering |
| spelling | doaj-art-dcf54041139647dfab229e675228eb5c2025-01-28T00:02:29ZengIEEEIEEE Transactions on Quantum Engineering2689-18082024-01-01511410.1109/TQE.2024.344366010636813Solving Nonnative Combinatorial Optimization Problems Using Hybrid Quantum–Classical AlgorithmsJonathan Wurtz0https://orcid.org/0000-0001-7237-0789Stefan H. Sack1https://orcid.org/0000-0001-5400-8508Sheng-Tao Wang2https://orcid.org/0000-0003-1403-5901QuEra Computing Inc., Boston, MA, USAQuEra Computing Inc., Boston, MA, USAQuEra Computing Inc., Boston, MA, USACombinatorial optimization is a challenging problem applicable in a wide range of fields from logistics to finance. Recently, quantum computing has been used to attempt to solve these problems using a range of algorithms, including parameterized quantum circuits, adiabatic protocols, and quantum annealing. These solutions typically have several challenges: 1) there is little to no performance gain over classical methods; 2) not all constraints and objectives may be efficiently encoded in the quantum ansatz; and 3) the solution domain of the objective function may not be the same as the bit strings of measurement outcomes. This work presents “nonnative hybrid algorithms”: a framework to overcome these challenges by integrating quantum and classical resources with a hybrid approach. By designing nonnative quantum variational anosatzes that inherit some but not all problem structure, measurement outcomes from the quantum computer can act as a resource to be used by classical routines to indirectly compute optimal solutions, partially overcoming the challenges of contemporary quantum optimization approaches. These methods are demonstrated using a publicly available neutral-atom quantum computer on two simple problems of Max <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-Cut and maximum independent set. We find improvements in solution quality when comparing the hybrid algorithm to its “no quantum” version, a demonstration of a “comparative advantage.”https://ieeexplore.ieee.org/document/10636813/Combinatorial mathematicsoptimizationquantum advantagequantum algorithmquantum computing |
| spellingShingle | Jonathan Wurtz Stefan H. Sack Sheng-Tao Wang Solving Nonnative Combinatorial Optimization Problems Using Hybrid Quantum–Classical Algorithms IEEE Transactions on Quantum Engineering Combinatorial mathematics optimization quantum advantage quantum algorithm quantum computing |
| title | Solving Nonnative Combinatorial Optimization Problems Using Hybrid Quantum–Classical Algorithms |
| title_full | Solving Nonnative Combinatorial Optimization Problems Using Hybrid Quantum–Classical Algorithms |
| title_fullStr | Solving Nonnative Combinatorial Optimization Problems Using Hybrid Quantum–Classical Algorithms |
| title_full_unstemmed | Solving Nonnative Combinatorial Optimization Problems Using Hybrid Quantum–Classical Algorithms |
| title_short | Solving Nonnative Combinatorial Optimization Problems Using Hybrid Quantum–Classical Algorithms |
| title_sort | solving nonnative combinatorial optimization problems using hybrid quantum x2013 classical algorithms |
| topic | Combinatorial mathematics optimization quantum advantage quantum algorithm quantum computing |
| url | https://ieeexplore.ieee.org/document/10636813/ |
| work_keys_str_mv | AT jonathanwurtz solvingnonnativecombinatorialoptimizationproblemsusinghybridquantumx2013classicalalgorithms AT stefanhsack solvingnonnativecombinatorialoptimizationproblemsusinghybridquantumx2013classicalalgorithms AT shengtaowang solvingnonnativecombinatorialoptimizationproblemsusinghybridquantumx2013classicalalgorithms |