Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1906.10036 · Physical Review Research

Analysis of the relation between quadratic unconstrained binary optimization and the spin-glass ground-state problem

Stefan Boettcher

Published Dec 3, 2019• 18 citations
arXivHTMLPDF

Abstract

An inherent weakness in a widely used formulation of the Quadratic Unconstrained Binary Optimization problem is revealed when transformed into an Ising spin glass. In the ground state, spins in the glass experience external magnetic fields, many of which are of a sizable magnitude to entirely coerce their spins into alignment, irrespective of any coupling; only a small fraction of spins can resist. Thus, the effective size of this NP-hard combinatorial problem is much smaller than is apparent from the number of variables involved.

DOI
10.1103/physrevresearch.1.033142

Related papers

On some features of quadratic unconstrained binary optimization with random coefficients

Marco Isopi, Benedetto Scoppola, Alessio Troiani

Abstract Quadratic Unconstrained Binary Optimization (QUBO or UBQP) is concerned with maximizing/minimizing the quadratic form $$H(J, \eta ) = W \sum _{i,j} J_{i,j} \eta _{i} \eta _{j}$$ H ( J , η ) = W ∑ i , j J i , j η i η j with J a matrix of coefficients, $$\eta \in \{0, 1\}^N$$ η ∈ { 0 , 1 } N and W a normalizing constant. In the statistical mechanics literature, QUBO is a lattice gas counterpart to the (generalized) Sherrington–Kirkpatrick spin glass model. Finding the optima of H is an NP-hard problem. Several problems in combinatorial optimization and data analysis can be mapped to QUBO in a straightforward manner. In the combinatorial optimization literature, random instances of QUBO are often used to test the effectiveness of heuristic algorithms. Here we consider QUBO with random independent coefficients and show that if the $$J_{i,j}$$ J i , j ’s have zero mean and finite variance then, after proper normalization, the minimum and maximum per particle of H do not depend on the details of the distribution of the couplings and are concentrated around their expected values. Further, with the help of numerical simulations, we study the minimum and maximum of the objective function and provide some insight into the structure of the minimizer and the maximizer of H. We argue that also this structure is rather robust. Our findings hold also in the diluted case where each of the $$J_{i,j}$$ J i , j ’s is allowed to be zero with probability going to 1 as $$N \rightarrow \infty $$ N → ∞ in a suitable way.

arXiv:2402.17059•Bollettino Della Unione Matematica Italiana•Aug 22, 2024•7 citations

Ground-state magnetization of Ising spin glasses

Francisco Barahona

We study the magnetization of the ground states of Ising spin glasses as a function of the magnetic field. The grids are two-dimensional with Gaussian bond distribution. Finding a ground state in this case is a difficult combinatorial problem. We present a method that guarantees finding a true ground state. Although it is unlikely that one can have an algorithm with a polynomial bound for the running time, in all cases we tried, our method found a solution in a reasonable amount of time. We used this to obtain estimations of the critical exponents.

Physical review. B, Condensed matter•May 1, 1994•20 citations

Extremal Optimization for Quadratic Unconstrained Binary Problems

Stefan Boettcher

We present an implementation of τ-EO for quadratic unconstrained binary optimization (QUBO) problems. To this end, we transform modify QUBO from its conventional Boolean presentation into a spin glass with a random external field on each site. These fields tend to be rather large compared to the typical coupling, presenting EO with a challenging two-scale problem, exploring smaller differences in couplings effectively while sufficiently aligning with those strong external fields. However, we also find a simple solution to that problem that indicates that those external fields apparently tilt the energy landscape to a such a degree such that global minima become more easy to find than those of spin glasses without (or very small) fields. We explore the impact of the weight distribution of the QUBO formulation in the operations research literature and analyze their meaning in a spin-glass language. This is significant because QUBO problems are considered among the main contenders for NP-hard problems that could be solved efficiently on a quantum computer such as D-Wave.

Physics Procedia•Jan 1, 2015•3 citations

Effect of the frustration to the ground state energy and entropy of the spin-glass in the random bond Ising model on the square lattice

Shigetoshi Katsura, Izuru Nagahara

Physica A Statistical Mechanics and its Applications•Dec 1, 1980•6 citations

Grover Adaptive Search for the Higher-Order Formulation of Quadratic Assignment Problems

Taku Mikuriya, Shintaro Fujiwara, Kein Yukiyoshi +2 more

We demonstrate that the search space of the quadratic assignment problem (QAP), known as an NP-hard combinatorial optimization problem, can be reduced using Grover adaptive search (GAS) with permutation preparation operator (PPO). To that end, we first revise the traditional quadratic unconstrained binary optimization (QUBO) formulation of the QAP into a higher-order unconstrained binary optimization (HUBO) formulation, introducing a binary encoding method. Algebraic analyses in terms of the number of qubits, quantum gates, circuit depth, and query complexity are performed, which indicate that our proposed approach significantly reduces the search space size, improving convergence performance to the optimal solution compared to the conventional one. Furthermore, although the PPO for HUBO has a greater circuit depth than the PPO for QUBO, when the analysis is extended to the entire state preparation operator, both HUBO and QUBO exhibit comparable depths. Therefore, owing to its smaller number of variables, HUBO can be concluded to be more effective.

arXiv:2410.12181•Oct 16, 2024•0 citations

Solved: Exact Ground State of Frustrated Quantum Spin Glasses (NP-Hard) Solved

Jesse Daniel Brown

•Oct 22, 2026•0 citations
An inherent weakness in a widely used formulation of the Quadratic Unconstrained Binary Optimization problem is revealed when transformed into an Ising spin glass. In the ground state, spins in the glass experience external magnetic fields, many of which are of a sizable magnitude to entirely coerce their spins into alignment, irrespective of any coupling; only a small fraction of spins can resist. Thus, the effective size of this NP-hard combinatorial problem is much smaller than is apparent from the number of variables involved.
Abstract Quadratic Unconstrained Binary Optimization (QUBO or UBQP) is concerned with maximizing/minimizing the quadratic form H(J,η)=W∑i,jJi,jηiηjH(J, \eta ) = W \sum _{i,j} J_{i,j} \eta _{i} \eta _{j}H(J,η)=W∑i,j​Ji,j​ηi​ηj​ H ( J , η ) = W ∑ i , j J i , j η i η j with J a matrix of coefficients, η∈{0,1}N\eta \in \{0, 1\}^Nη∈{0,1}N η ∈ { 0 , 1 } N and W a normalizing constant. In the statistical mechanics literature, QUBO is a lattice gas counterpart to the (generalized) Sherrington–Kirkpatrick spin glass model. Finding the optima of H is an NP-hard problem. Several problems in combinatorial optimization and data analysis can be mapped to QUBO in a straightforward manner. In the combinatorial optimization literature, random instances of QUBO are often used to test the effectiveness of heuristic algorithms. Here we consider QUBO with random independent coefficients and show that if the Ji,jJ_{i,j}Ji,j​ J i , j ’s have zero mean and finite variance then, after proper normalization, the minimum and maximum per particle of H do not depend on the details of the distribution of the couplings and are concentrated around their expected values. Further, with the help of numerical simulations, we study the minimum and maximum of the objective function and provide some insight into the structure of the minimizer and the maximizer of H. We argue that also this structure is rather robust. Our findings hold also in the diluted case where each of the Ji,jJ_{i,j}Ji,j​ J i , j ’s is allowed to be zero with probability going to 1 as N→∞N \rightarrow \infty N→∞ N → ∞ in a suitable way.
We study the magnetization of the ground states of Ising spin glasses as a function of the magnetic field. The grids are two-dimensional with Gaussian bond distribution. Finding a ground state in this case is a difficult combinatorial problem. We present a method that guarantees finding a true ground state. Although it is unlikely that one can have an algorithm with a polynomial bound for the running time, in all cases we tried, our method found a solution in a reasonable amount of time. We used this to obtain estimations of the critical exponents.
We present an implementation of τ-EO for quadratic unconstrained binary optimization (QUBO) problems. To this end, we transform modify QUBO from its conventional Boolean presentation into a spin glass with a random external field on each site. These fields tend to be rather large compared to the typical coupling, presenting EO with a challenging two-scale problem, exploring smaller differences in couplings effectively while sufficiently aligning with those strong external fields. However, we also find a simple solution to that problem that indicates that those external fields apparently tilt the energy landscape to a such a degree such that global minima become more easy to find than those of spin glasses without (or very small) fields. We explore the impact of the weight distribution of the QUBO formulation in the operations research literature and analyze their meaning in a spin-glass language. This is significant because QUBO problems are considered among the main contenders for NP-hard problems that could be solved efficiently on a quantum computer such as D-Wave.
We demonstrate that the search space of the quadratic assignment problem (QAP), known as an NP-hard combinatorial optimization problem, can be reduced using Grover adaptive search (GAS) with permutation preparation operator (PPO). To that end, we first revise the traditional quadratic unconstrained binary optimization (QUBO) formulation of the QAP into a higher-order unconstrained binary optimization (HUBO) formulation, introducing a binary encoding method. Algebraic analyses in terms of the number of qubits, quantum gates, circuit depth, and query complexity are performed, which indicate that our proposed approach significantly reduces the search space size, improving convergence performance to the optimal solution compared to the conventional one. Furthermore, although the PPO for HUBO has a greater circuit depth than the PPO for QUBO, when the analysis is extended to the entire state preparation operator, both HUBO and QUBO exhibit comparable depths. Therefore, owing to its smaller number of variables, HUBO can be concluded to be more effective.