@article{18923,
  abstract     = {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.”},
  author       = {Wurtz, Jonathan and Sack, Stefan and Wang, Sheng-Tao},
  issn         = {2689-1808},
  journal      = {IEEE Transactions on Quantum Engineering},
  pages        = {1--14},
  publisher    = {Institute of Electrical and Electronics Engineers },
  title        = {{Solving nonnative combinatorial optimization problems using hybrid quantum–classical algorithms}},
  doi          = {10.1109/tqe.2024.3443660},
  volume       = {5},
  year         = {2024},
}