Solving nonnative combinatorial optimization problems using hybrid quantum–classical algorithms Wurtz, Jonathan Sack, Stefan ; https://orcid.org/0000-0001-5400-8508 Wang, Sheng-Tao ddc:530 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 k-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.” Institute of Electrical and Electronics Engineers 2024 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/18923 https://research-explorer.ista.ac.at/download/18923/18924 Wurtz J, Sack S, Wang S-T. Solving nonnative combinatorial optimization problems using hybrid quantum–classical algorithms. <i>IEEE Transactions on Quantum Engineering</i>. 2024;5:1-14. doi:<a href="https://doi.org/10.1109/tqe.2024.3443660">10.1109/tqe.2024.3443660</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1109/tqe.2024.3443660 info:eu-repo/semantics/altIdentifier/issn/2689-1808 info:eu-repo/semantics/openAccess