A QUBO Formulation for Nowhere-Zero $k$-Flows

Quantum Physics arXiv:2606.28687 (quant-ph) [Submitted on 27 Jun 2026] Title:A QUBO Formulation for Nowhere-Zero $k$-Flows Authors:Ali Lotfi, Adam Carter, Mohammad Meysami, Thuan Ha, Kwabena Abrefa Nketia, Steven J. Shirtliffe, Steven Rayan View a PDF of the paper titled A QUBO Formulation for Nowhere-Zero $k$-Flows, by Ali Lotfi and 6 other authors View PDF HTML (experimental) Abstract:We consider the encoding of graph problems as Quadratic Unconstrained Binary Optimization (QUBO) problems, which are solvable by either quantum or classical annealers. Yet, the class of problems encoded as QUBO problems has not previously included nowhere-zero flows. Nowhere-zero flows are related to Tutte's $5$-flow conjecture and appear in many contexts in graph theory. We provide an encoding of nowhere-zero flows as a QUBO Hamiltonian and prove the correctness of the construction. Our construction yields a Hamiltonian $H_{\mathrm{mod},k}$ whose ground state has zero 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)$. In particular, when the ground-state energy is zero, this is also the ground-state degeneracy. The construction uses one-hot variables to represent the edge flow residues modulo $k$ and auxiliary variables to represent the per-vertex modular quotient. We prove that the correctness of the construction is independent of the choice of orientation, root vertex, and positive penalty weights. We verify the construction on $59$ examples of graphs and values of $k$ that include both yes-instances and no-instances. We exhaustively sweep orientations and root choices on selected robustness instances and test a finite suite of positive penalty weights. The resulting Hamiltonian is implemented using the this http URL class, which is compatible with the D-Wave Ocean SDK. Quantum-hardware runs and claims about potential speedup using these devices are left to follow-up work. Comments: Subjects: Quantum Physics (quant-ph); Combinatorics (math.CO) Cite as: arXiv:2606.28687 [quant-ph] (or arXiv:2606.28687v1 [quant-ph] for this version) https://doi.org/10.48550/arXiv.2606.28687 Focus to learn more arXiv-issued DOI via DataCite (pending registration) Journal reference: Util. Math. 127 (2026), 341--365 Related DOI: https://doi.org/10.61091/um127-21 Focus to learn more DOI(s) linking to related resources Submission history From: Steven Rayan [view email] [v1] Sat, 27 Jun 2026 01:59:01 UTC (23 KB) Full-text links: Access Paper: View a PDF of the paper titled A QUBO Formulation for Nowhere-Zero $k$-Flows, by Ali Lotfi and 6 other authorsView PDFHTML (experimental)TeX Source view license Current browse context: quant-ph new | recent | 2026-06 Change to browse by: math math.CO References & Citations INSPIRE HEP NASA ADSGoogle Scholar Semantic Scholar export BibTeX citation Loading... BibTeX formatted citation × loading... Data provided by: Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv (What is alphaXiv?) Links to Code Toggle CatalyzeX Code Finder for Papers (What is CatalyzeX?) DagsHub Toggle DagsHub (What is DagsHub?) GotitPub Toggle Gotit.pub (What is GotitPub?) Huggingface Toggle Hugging Face (What is Huggingface?) ScienceCast Toggle ScienceCast (What is ScienceCast?) Demos Demos Replicate Toggle Replicate (What is Replicate?) Spaces Toggle Hugging Face Spaces (What is Spaces?) Spaces Toggle TXYZ.AI (What is TXYZ.AI?) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower (What are Influence Flowers?) Core recommender toggle CORE Recommender (What is CORE?) Author Venue Institution Topic About arXivLabs arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs. Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)