EUVIMEDEUVIMED entdecken
Crossref

A QUBO formulation for nowhere-zero k-flows

Ali Lotfi, Adam Carter, Mohammad Meysami, Thuan Ha, Kwabena Abrefa Nketia, Steven J. Shirtliffe, Steven Rayan

Utilitas Mathematica · 17.06.2026 · 127 · 341-365

DOI: 10.61091/um127-21 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Utilitas Mathematica, online erschienen am 17.06.2026. Verfasst von Ali Lotfi und 6 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We consider the encoding of graph problems as Quadratic Unconstrained Binary Optimization (QUBO) problems, solvable by quantum or classical annealers. However, nowhere-zero flows have not previously been included among graph problems encoded as QUBO problems. Nowhere-zero flows are related to Tutte’s \(5\)-flow conjecture and occur in many contexts in graph theory. We provide a QUBO Hamiltonian encoding of nowhere-zero flows and prove the correctness of the construction. The resulting Hamiltonian \(H_{\mathrm{mod},k}\) has zero ground-state energy if and only if the graph \(G\) has a nowhere-zero \(\mathbb{Z}_k\)-flow. By Tutte’s equivalence theorem, zero ground energy is equivalent to \(\varphi(G)\le k\), and the zero-energy degeneracy is given by the flow polynomial \(F(G;k)\). The construction uses one-hot variables for edge flow residues modulo \(k\) and auxiliary variables for the per-vertex modular quotient. We prove that correctness is independent of the choice of orientation, root vertex, and positive penalty weights. We verify the construction on \(59\) graph and \(k\) examples, including both yes-instances and no-instances. We also sweep orientations and root choices on selected robustness instances and test a finite suite of positive penalty weights. The Hamiltonian is implemented using the dimod.BinaryQuadraticModel class, compatible with the D-Wave Ocean SDK. Quantum-hardware runs and claims about potential speedup are left to future work.

Zitieren

APA

Lotfi, A., Carter, A., Meysami, M., Ha, T., Nketia, K. A., Shirtliffe, S. J., & Rayan, S. (2026). A QUBO formulation for nowhere-zero k-flows. Utilitas Mathematica, 127, 341-365. https://doi.org/10.61091/um127-21

Vancouver

Lotfi A, Carter A, Meysami M, Ha T, Nketia KA, Shirtliffe SJ, et al. A QUBO formulation for nowhere-zero k-flows. Utilitas Mathematica. 2026;127:341-365. doi:10.61091/um127-21

BibTeX
@article{Lotfi2026,
  author = {Lotfi, Ali and Carter, Adam and Meysami, Mohammad and Ha, Thuan and Nketia, Kwabena Abrefa and Shirtliffe, Steven J. and Rayan, Steven},
  title = {A QUBO formulation for nowhere-zero k-flows},
  journal = {Utilitas Mathematica},
  year = {2026},
  volume = {127},
  pages = {341--365},
  doi = {10.61091/um127-21}
}
Kostenlos starten →