---
OA_place: publisher
OA_type: hybrid
_id: '18923'
abstract:
- lang: eng
  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.”'
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)."
article_processing_charge: Yes (in subscription journal)
article_type: original
author:
- first_name: Jonathan
  full_name: Wurtz, Jonathan
  last_name: Wurtz
- first_name: Stefan
  full_name: Sack, Stefan
  id: dd622248-f6e0-11ea-865d-ce382a1c81a5
  last_name: Sack
  orcid: 0000-0001-5400-8508
- first_name: Sheng-Tao
  full_name: Wang, Sheng-Tao
  last_name: Wang
citation:
  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>
  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>
  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>.
  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.
  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.
  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>.
  short: J. Wurtz, S. Sack, S.-T. Wang, IEEE Transactions on Quantum Engineering 5
    (2024) 1–14.
das_tickbox: '1'
date_created: 2025-01-27T15:00:44Z
date_published: 2024-08-14T00:00:00Z
date_updated: 2026-07-06T13:29:20Z
day: '14'
ddc:
- '530'
department:
- _id: MaSe
doi: 10.1109/tqe.2024.3443660
file:
- access_level: open_access
  checksum: 19b84e35cba05bde72bfe7e0b54c3e6c
  content_type: application/pdf
  creator: dernst
  date_created: 2025-01-27T15:03:09Z
  date_updated: 2025-01-27T15:03:09Z
  file_id: '18924'
  file_name: 2024_IEEEQuantumComputing_Wurtz.pdf
  file_size: 1753095
  relation: main_file
  success: 1
file_date_updated: 2025-01-27T15:03:09Z
has_accepted_license: '1'
intvolume: '         5'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: 1-14
publication: IEEE Transactions on Quantum Engineering
publication_identifier:
  issn:
  - 2689-1808
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Solving nonnative combinatorial optimization problems using hybrid quantum–classical
  algorithms
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 5
year: '2024'
...