[{"acknowledgement":"The authors would like to thank Alexander Keesling, Maddie Cain, Nate Gemelke, and Phillip Weinberg for helpful discussions and Danylo Lykov who had early contributions to this work.\r\n10.13039/100000185-Defense Advanced Research Projects Agency Noisy Intermediate-Scale Quantum Devices (Grant Number: W911NF2010021), DARPA Small Business Technology Transfer program (Grant Number: 140D0422C0035).","OA_type":"hybrid","das_tickbox":"1","type":"journal_article","oa_version":"Published Version","OA_place":"publisher","file":[{"date_updated":"2025-01-27T15:03:09Z","relation":"main_file","checksum":"19b84e35cba05bde72bfe7e0b54c3e6c","success":1,"date_created":"2025-01-27T15:03:09Z","file_size":1753095,"access_level":"open_access","file_name":"2024_IEEEQuantumComputing_Wurtz.pdf","content_type":"application/pdf","file_id":"18924","creator":"dernst"}],"department":[{"_id":"MaSe"}],"publication_identifier":{"issn":["2689-1808"]},"ddc":["530"],"article_type":"original","oa":1,"date_updated":"2026-07-06T13:29:20Z","_id":"18923","status":"public","language":[{"iso":"eng"}],"author":[{"full_name":"Wurtz, Jonathan","last_name":"Wurtz","first_name":"Jonathan"},{"first_name":"Stefan","full_name":"Sack, Stefan","last_name":"Sack","id":"dd622248-f6e0-11ea-865d-ce382a1c81a5","orcid":"0000-0001-5400-8508"},{"first_name":"Sheng-Tao","last_name":"Wang","full_name":"Wang, Sheng-Tao"}],"scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"article_processing_charge":"Yes (in subscription journal)","date_created":"2025-01-27T15:00:44Z","publication_status":"published","citation":{"mla":"Wurtz, Jonathan, et al. “Solving Nonnative Combinatorial Optimization Problems Using Hybrid Quantum–Classical Algorithms.” <i>IEEE Transactions on Quantum Engineering</i>, vol. 5, Institute of Electrical and Electronics Engineers, 2024, pp. 1–14, doi:<a href=\"https://doi.org/10.1109/tqe.2024.3443660\">10.1109/tqe.2024.3443660</a>.","ista":"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.","apa":"Wurtz, J., Sack, S., &#38; Wang, S.-T. (2024). Solving nonnative combinatorial optimization problems using hybrid quantum–classical algorithms. <i>IEEE Transactions on Quantum Engineering</i>. Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/tqe.2024.3443660\">https://doi.org/10.1109/tqe.2024.3443660</a>","ieee":"J. Wurtz, S. Sack, and S.-T. Wang, “Solving nonnative combinatorial optimization problems using hybrid quantum–classical algorithms,” <i>IEEE Transactions on Quantum Engineering</i>, vol. 5. Institute of Electrical and Electronics Engineers, pp. 1–14, 2024.","chicago":"Wurtz, Jonathan, Stefan Sack, and Sheng-Tao Wang. “Solving Nonnative Combinatorial Optimization Problems Using Hybrid Quantum–Classical Algorithms.” <i>IEEE Transactions on Quantum Engineering</i>. Institute of Electrical and Electronics Engineers, 2024. <a href=\"https://doi.org/10.1109/tqe.2024.3443660\">https://doi.org/10.1109/tqe.2024.3443660</a>.","ama":"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>","short":"J. Wurtz, S. Sack, S.-T. Wang, IEEE Transactions on Quantum Engineering 5 (2024) 1–14."},"abstract":[{"text":"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.”","lang":"eng"}],"quality_controlled":"1","file_date_updated":"2025-01-27T15:03:09Z","publication":"IEEE Transactions on Quantum Engineering","title":"Solving nonnative combinatorial optimization problems using hybrid quantum–classical algorithms","intvolume":"         5","day":"14","date_published":"2024-08-14T00:00:00Z","page":"1-14","year":"2024","month":"08","volume":5,"publisher":"Institute of Electrical and Electronics Engineers","has_accepted_license":"1","doi":"10.1109/tqe.2024.3443660"}]