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

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

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

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

arXivarxiv/2606.28687Jun 27, 2026quant-phscore 0

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…

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2606.28687
curl -X POST /api/v1/records/arxiv/2606.28687/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.28687/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'