Solving nonnative combinatorial optimization problems using hybrid quantum

article Solving nonnative combinatorial optimization problems using hybrid quantum–classical algorithms published yes Jonathan Wurtz author Stefan Sack author dd622248-f6e0-11ea-865d-ce382a1c81a50000-0001-5400-8508 Sheng-Tao Wang author MaSe department 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.” https://research-explorer.ista.ac.at/download/18923/18924/2024_IEEEQuantumComputing_Wurtz.pdf application/pdfno https://creativecommons.org/licenses/by/4.0/ IEEE2024 eng IEEE Transactions on Quantum Engineering 2689-180810.1109/tqe.2024.3443660 51-14 Wurtz J, Sack S, Wang S-T. 2024. Solving nonnative combinatorial optimization problems using hybrid quantum–classical algorithms. IEEE Transactions on Quantum Engineering. 5, 1–14. Wurtz J, Sack S, Wang S-T. Solving nonnative combinatorial optimization problems using hybrid quantum–classical algorithms. IEEE Transactions on Quantum Engineering. 2024;5:1-14. doi:<a href="https://doi.org/10.1109/tqe.2024.3443660">10.1109/tqe.2024.3443660</a> J. Wurtz, S. Sack, S.-T. Wang, IEEE Transactions on Quantum Engineering 5 (2024) 1–14. Wurtz, Jonathan, Stefan Sack, and Sheng-Tao Wang. “Solving Nonnative Combinatorial Optimization Problems Using Hybrid Quantum–Classical Algorithms.” IEEE Transactions on Quantum Engineering. IEEE, 2024. <a href="https://doi.org/10.1109/tqe.2024.3443660">https://doi.org/10.1109/tqe.2024.3443660</a>. Wurtz, J., Sack, S., & Wang, S.-T. (2024). Solving nonnative combinatorial optimization problems using hybrid quantum–classical algorithms. IEEE Transactions on Quantum Engineering. IEEE. <a href="https://doi.org/10.1109/tqe.2024.3443660">https://doi.org/10.1109/tqe.2024.3443660</a> J. Wurtz, S. Sack, and S.-T. Wang, “Solving nonnative combinatorial optimization problems using hybrid quantum–classical algorithms,” IEEE Transactions on Quantum Engineering, vol. 5. IEEE, pp. 1–14, 2024. Wurtz, Jonathan, et al. “Solving Nonnative Combinatorial Optimization Problems Using Hybrid Quantum–Classical Algorithms.” IEEE Transactions on Quantum Engineering, vol. 5, IEEE, 2024, pp. 1–14, doi:<a href="https://doi.org/10.1109/tqe.2024.3443660">10.1109/tqe.2024.3443660</a>. 189232025-01-27T15:00:44Z2026-08-12T06:42:26Z