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

• URL: http://arxiv.org/abs/2606.28687v1
• Date: Sat, 27 Jun 2026 01:59:01 GMT
• Title: A QUBO Formulation for Nowhere-Zero $k$-Flows
• Abstract summary: Nowhere-zero flows are related to Tutte's $5$-flow conjecture and appear in many contexts in graph theory.<n>We provide an encoding of nowhere-zero flows as a QUBO Hamiltonian and prove the correctness of the construction.
• Score: 0.3908906925636173
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 dimod.BinaryQuadraticModel 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.

Related papers

• Zero-Energy Problems for Supersymmetric Hamiltonians on a Chain Are $\mathrm{QMA}_1$-Complete [2.4344882758650743]
  We study exact zero modes of supersymmetric quantum systems whose interactions are arranged on a one-dimensional chain.<n>The construction gives an explicit inverse-polynomial lower bound on the ground energy of every reduced NO instance, separating it from zero.
  arXiv  Detail & Related papers  (2026-08-29T15:32:39Z)
• A Provable Oracle-Free Quantum Algorithm for Nonlinear Dynamics on Hybrid Oscillator-Qubit Processors [14.814423713691623]
  We develop a hybrid qubit-qumode algorithm for nonlinear ordinary differential equations of the form $dotmathbfx=mathbff(mathbfx)$ with warped degree$L$.<n>The algorithm propagates the state density and returns the trajectory as the peak of that density in the small-noise limit.
  arXiv  Detail & Related papers  (2026-07-30T17:10:47Z)
• An Optimal Analysis of the Product Test [42.29010058743949]
  Product testing decides whether a pure multipartite quantum state is fully unentangled across a specified tensor decomposition.<n>Despite being a fundamental property testing task and having many applications, the product test's exact (worst-case) acceptance probability curve has yet to be fully determined.<n>As a complexity-theoretic application, our results improve the one-shot soundness parameter in the Harrow-Montanaro reduction from $mathsfQMA(k)$ to $mathsfQMA(2)$.
  arXiv  Detail & Related papers  (2026-07-23T16:17:44Z)
• Quantum Brownian motion with non-Gaussian noises: Fluctuation-Dissipation Relation and nonlinear Langevin equation [0.0]
  We consider the quantum Brownian motion (QBM) model with one oscillator as the system.<n>The influence action $S_IF$ is calculated using a perturbative expansion in $$.<n>The non-Gaussian noise kernel gives rise to non-zero three-point correlation function of the corresponding force.
  arXiv  Detail & Related papers  (2026-02-11T02:03:26Z)
• Discrete symmetries in classical and quantum oscillators [51.56484100374058]
  We show the eigenfunctions $_n=zn$ of the quantum Hamiltonian in the complex Bargmann-Fock-Segal representation.<n>The superposition $=sum_n c_n_n$ arises only with incomplete knowledge of the initial data for solving the Schrdinger equation.
  arXiv  Detail & Related papers  (2026-01-05T10:04:39Z)
• On stability of k-local quantum phases of matter [0.4999814847776097]
  We analyze the stability of the energy gap to Euclids for Hamiltonians corresponding to general quantum low-density parity-check codes. We discuss implications for the third law of thermodynamics, as $k$-local Hamiltonians can have extensive zero-temperature entropy.
  arXiv  Detail & Related papers  (2024-05-29T18:00:20Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Small-time controllability for the nonlinear Schr\"odinger equation on $\mathbb{R}^N$ via bilinear electromagnetic fields [55.2480439325792]
  We address the small-time controllability problem for a nonlinear Schr"odinger equation (NLS) on $mathbbRN$ in the presence of magnetic and electric external fields. In detail, we study when it is possible to control the dynamics of (NLS) as fast as desired via sufficiently large control signals.
  arXiv  Detail & Related papers  (2023-07-28T21:30:44Z)
• Taming Dyson-Schwinger equations with null states [0.913755431537592]
  In quantum field theory, the Dyson-Schwinger equations are an infinite set of equations relating $n$-point Green's functions in a self-consistent manner. One of the main problems is that a finite truncation of the infinite system is underdetermined. In this paper, we propose another avenue in light of the null bootstrap.
  arXiv  Detail & Related papers  (2023-03-20T10:04:43Z)
• Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
  We provide a systematic treatment of boundaries based on subgroups $Ksubseteq G$ with the Kitaev quantum double $D(G)$ model in the bulk. The boundary sites are representations of a $*$-subalgebra $Xisubseteq D(G)$ and we explicate its structure as a strong $*$-quasi-Hopf algebra. As an application of our treatment, we study patches with boundaries based on $K=G$ horizontally and $K=e$ vertically and show how these could be used in a quantum computer
  arXiv  Detail & Related papers  (2022-08-12T15:05:07Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.