Recently, there has been considerable interest in solving optimization problems by mapping these onto a binary representation, sparked mostly by the use of quantum annealing machines. Such binary representation is reminiscent of a discrete physical two-state system, such as the Ising model. As such, physics-inspired techniques-commonly used in fundamental physics studies-are ideally suited to solve optimization problems in a binary format. While binary representations can be often found for paradigmatic optimization problems, these typically result in k-local higher-order unconstrained binary optimization cost functions. In this work, we discuss the effects of locality reduction needed for solvers such as the D-Wave quantum annealer, the Fujitsu Digital Annealer, or the Toshiba Simulated Bifurcation Machine that can only accommodate 2-local (quadratic) cost functions. General locality reduction approaches require the introduction of ancillary variables which cause an overhead over the native problem. Using a parallel tempering Monte Carlo solver on Azure Quantum, as well as k-local binary problems with planted solutions, we show that post reduction to a corresponding 2-local representation the problems become considerably harder to solve. We further quantify the increase in computational hardness introduced by the reduction algorithm by measuring the variation of number of variables, statistics of the coefficient values, and the entropic family size. Our results demonstrate the importance of avoiding locality reduction when solving optimization problems.Recently, there has been considerable interest in solving optimization problems by mapping these onto a binary representation, sparked mostly by the use of quantum annealing machines. Such binary representation is reminiscent of a discrete physical two-state system, such as the Ising model. As such, physics-inspired techniques-commonly used in fundamental physics studies-are ideally suited to solve optimization problems in a binary format. While binary representations can be often found for paradigmatic optimization problems, these typically result in k-local higher-order unconstrained binary optimization cost functions. In this work, we discuss the effects of locality reduction needed for solvers such as the D-Wave quantum annealer, the Fujitsu Digital Annealer, or the Toshiba Simulated Bifurcation Machine that can only accommodate 2-local (quadratic) cost functions. General locality reduction approaches require the introduction of ancillary variables which cause an overhead over the native problem. Using a parallel tempering Monte Carlo solver on Azure Quantum, as well as k-local binary problems with planted solutions, we show that post reduction to a corresponding 2-local representation the problems become considerably harder to solve. We further quantify the increase in computational hardness introduced by the reduction algorithm by measuring the variation of number of variables, statistics of the coefficient values, and the entropic family size. Our results demonstrate the importance of avoiding locality reduction when solving optimization problems.

Dec 17, 20202 citations

Truncated-Binary Encoding: Spectral Degree Reduction of Combinatorial Optimization Problems for Quantum Hardware

Tristan Zaborniak

Exact-binary encoding compiles a discrete cost function network (CFN) into a higher-order unconstrained binary optimization (HUBO) problem whose maximum monomial degree grows with the cardinalities of the underlying CFN variables. Given that quantum optimization hardware generally favours quadratic unconstrained binary optimization or low-degree HUBO Hamiltonians, high-cardinality CFNs therefore incur substantial overhead in the form of circuit depth, or ancilla qubits when degree-reduction techniques are employed. To ameliorate these issues, we propose \textit{truncated-binary encoding} (TBE): a modification of exact-binary encoding in which Ising-basis monomials exceeding a chosen cutoff $k_\text{max}$ are dropped from the encoded cost. We establish a tight $L^\infty$ bound on the truncation error in terms of the omitted couplings, derive sufficient conditions on the energy gap and on the single bit-flip basin barrier under which TBE preserves the global minimum and its local-minimum structure, and characterize a noise floor condition on the spectral profile under which the truncation residual acts as a perturbative correction to the underlying landscape. We then express the encoded coefficients directly as Walsh transforms of the underlying CFN cost tables, and prove a bound under which smoothness of each cost table implies rapid decay of its high-degree Walsh mass. Together these results yield a principled \textit{a priori} criterion for selecting $k_\text{max}$ and for judging whether a given CFN admits a small- $k_\text{max}$ TBE.Exact-binary encoding compiles a discrete cost function network (CFN) into a higher-order unconstrained binary optimization (HUBO) problem whose maximum monomial degree grows with the cardinalities of the underlying CFN variables. Given that quantum optimization hardware generally favours quadratic unconstrained binary optimization or low-degree HUBO Hamiltonians, high-cardinality CFNs therefore incur substantial overhead in the form of circuit depth, or ancilla qubits when degree-reduction techniques are employed. To ameliorate these issues, we propose \textit{truncated-binary encoding} (TBE): a modification of exact-binary encoding in which Ising-basis monomials exceeding a chosen cutoff $k_\text{max}$ are dropped from the encoded cost. We establish a tight $L^\infty$ bound on the truncation error in terms of the omitted couplings, derive sufficient conditions on the energy gap and on the single bit-flip basin barrier under which TBE preserves the global minimum and its local-minimum structure, and characterize a noise floor condition on the spectral profile under which the truncation residual acts as a perturbative correction to the underlying landscape. We then express the encoded coefficients directly as Walsh transforms of the underlying CFN cost tables, and prove a bound under which smoothness of each cost table implies rapid decay of its high-degree Walsh mass. Together these results yield a principled \textit{a priori} criterion for selecting $k_\text{max}$ and for judging whether a given CFN admits a small-$k_\text{max}$ TBE.

quant-pharXiv:2605.17143May 19, 20260 citations

Improved row-by-row method for binary quadratic optimization problems

Rupaj Kumar Nayak, Nirmalya Kumar Mohanty

Annals of Operations ResearchJul 27, 20183 citations

Hierarchical divide and conquer quantum approach to combinatorial optimization problems with tunable reduction

Mathias Schmid, Naeimeh Mohseni, Michael J. Hartmann

Combinatorial optimization is considered a promising class of problems in which quantum computers can show significant advantages. However, problems of practical relevance typically have more variables than current or foreseeable quantum computers have qubits. Here we introduce a divide and conquer approach that partitions the optimization problem into subgraphs that can be represented on smaller quantum processors. We then find all states of the subgraphs that can possibly be part of the solution to the entire problem by determining the cost or energy ranges in which the local subgraph energies of these states must be contained. This allows us to reduce the problem by only considering the subspace spanned by these states. We then recombine the system using a binary encoding for each subgraph with a local energy ordering. This process can be iterated until no further reduction is possible. We also find that the number of necessary qubits can be reduced further when only retaining states in a fraction of the relevant energy range at very little expense in terms of approximation ratio to the global ground state. In numerical simulations, we find that our approach allows us to solve combinatorial optimization problems on weighted random 3-regular graphs with $|\mathcal{V}|=40$ discrete variables on $\sim |\mathcal{V}| / 4$ qubits while retaining a possible approximation ratio of $\sim99.9\%$ . We also observe an increasing reduction with larger system sizes.Combinatorial optimization is considered a promising class of problems in which quantum computers can show significant advantages. However, problems of practical relevance typically have more variables than current or foreseeable quantum computers have qubits. Here we introduce a divide and conquer approach that partitions the optimization problem into subgraphs that can be represented on smaller quantum processors. We then find all states of the subgraphs that can possibly be part of the solution to the entire problem by determining the cost or energy ranges in which the local subgraph energies of these states must be contained. This allows us to reduce the problem by only considering the subspace spanned by these states. We then recombine the system using a binary encoding for each subgraph with a local energy ordering. This process can be iterated until no further reduction is possible. We also find that the number of necessary qubits can be reduced further when only retaining states in a fraction of the relevant energy range at very little expense in terms of approximation ratio to the global ground state. In numerical simulations, we find that our approach allows us to solve combinatorial optimization problems on weighted random 3-regular graphs with $|\mathcal{V}|=40$ discrete variables on $\sim |\mathcal{V}| / 4$ qubits while retaining a possible approximation ratio of $\sim99.9\%$. We also observe an increasing reduction with larger system sizes.

quant-pharXiv:2512.18464Dec 23, 20250 citations

k_\text{max}

are dropped from the encoded cost. We establish a tight

L^\infty

bound on the truncation error in terms of the omitted couplings, derive sufficient conditions on the energy gap and on the single bit-flip basin barrier under which TBE preserves the global minimum and its local-minimum structure, and characterize a noise floor condition on the spectral profile under which the truncation residual acts as a perturbative correction to the underlying landscape. We then express the encoded coefficients directly as Walsh transforms of the underlying CFN cost tables, and prove a bound under which smoothness of each cost table implies rapid decay of its high-degree Walsh mass. Together these results yield a principled \textit{a priori} criterion for selecting

k_\text{max}

and for judging whether a given CFN admits a small-

k_\text{max}

TBE.

|\mathcal{V}|=40

discrete variables on

\sim |\mathcal{V}| / 4

qubits while retaining a possible approximation ratio of

\sim99.9\%

. We also observe an increasing reduction with larger system sizes.