EUVIMEDEUVIMED entdecken
Crossref

Imaginary Hamiltonian variational Ansatz for combinatorial optimization problems

Xiaoyang Wang, Yahui Chai, Xu Feng, Yibin Guo, Karl Jansen, Cenk Tüysüz

Physical Review A · 18.03.2025 · 111 (3)

DOI: 10.1103/physreva.111.032612 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Physical Review A, online erschienen am 18.03.2025. Verfasst von Xiaoyang Wang und 5 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 62 Literaturangaben. Gefördert von: National Natural Science Foundation of China, National Key Research and Development Program of China, HORIZON EUROPE Framework Programme.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Obtaining exact solutions to combinatorial optimization problems using classical computing is computationally expensive. The current tenet in the field is that quantum computers can address these problems more efficiently. While promising algorithms require fault-tolerant quantum hardware, variational algorithms have emerged as viable candidates for near-term devices. The success of these algorithms hinges on multiple factors, with the design of the ansatz having the utmost importance. It is known that popular approaches such as quantum approximate optimization algorithm (QAOA) and quantum annealing suffer from adiabatic bottlenecks, that lead to either larger circuit depth or evolution time. On the other hand, the evolution time of imaginary time evolution is bounded by the inverse energy gap of the Hamiltonian, which is constant for most non-critical physical systems. In this work, we propose imaginary Hamiltonian variational ansatz ($i$HVA) inspired by quantum imaginary time evolution to solve the MaxCut problem. We introduce a tree arrangement of the parametrized quantum gates, enabling the exact solution of arbitrary tree graphs using the one-round $i$HVA. For randomly generated $D$-regular graphs, we numerically demonstrate that the $i$HVA solves the MaxCut problem with a small constant number of rounds and sublinear depth, outperforming QAOA, which requires rounds increasing with the graph size. Furthermore, our ansatz solves MaxCut exactly for graphs with up to 24 nodes and $D \leq 5$, whereas only approximate solutions can be derived by the classical near-optimal Goemans-Williamson algorithm. We validate our simulated results with hardware demonstrations on a graph with 67 nodes.

Förderung

  • National Natural Science Foundation of China
  • National Key Research and Development Program of China
  • HORIZON EUROPE Framework Programme

Zitieren

APA

Wang, X., Chai, Y., Feng, X., Guo, Y., Jansen, K., & Tüysüz, C. (2025). Imaginary Hamiltonian variational Ansatz for combinatorial optimization problems. Physical Review A, 111(3). https://doi.org/10.1103/physreva.111.032612

Vancouver

Wang X, Chai Y, Feng X, Guo Y, Jansen K, Tüysüz C. Imaginary Hamiltonian variational Ansatz for combinatorial optimization problems. Physical Review A. 2025;111(3). doi:10.1103/physreva.111.032612

BibTeX
@article{Wang2025,
  author = {Wang, Xiaoyang and Chai, Yahui and Feng, Xu and Guo, Yibin and Jansen, Karl and Tüysüz, Cenk},
  title = {Imaginary Hamiltonian variational Ansatz for combinatorial optimization problems},
  journal = {Physical Review A},
  year = {2025},
  volume = {111},
  number = {3},
  doi = {10.1103/physreva.111.032612}
}
Kostenlos starten →