Can a normal computer solve QUBO?

Yes. Many classical methods can search or exactly solve instances, depending on size and structure.

Are all QUBO problems easy?

No. The general problem includes computationally difficult instances.

Can restrictions be included?

Often through penalties and sometimes extra variables, but the encoding must preserve the intended decisions and be checked carefully.

AI Glossary / AI and machine learning / Advanced

Quadratic unconstrained binary optimization

Definition

Quadratic unconstrained binary optimization, usually abbreviated QUBO, is a problem formulation that minimizes a quadratic objective over variables restricted to zero or one. The objective contains individual-variable costs and pairwise interactions. Constraints other than the binary domains can be represented through penalty terms rather than separate constraint expressions.

What it means

Each variable represents a yes-or-no choice, such as whether to include an item or select an assignment. The objective records how desirable each choice is and how pairs of choices interact. “Unconstrained” describes the mathematical form, not the absence of real-world restrictions. A restriction such as choosing exactly one option can be translated into a penalty for violating it. QUBO is a way to express a problem; it does not specify one solver or require a quantum computer.

How it works

Define binary variables and construct an objective from linear and quadratic terms. Because x² equals x for binary x, diagonal quadratic terms can represent linear costs. Encode relevant restrictions with penalties when possible, then select a suitable solver. D-Wave's documentation describes the QUBO form and its relation to Ising models. Classical exact algorithms, heuristics and some quantum approaches can address such formulations. After solving, decode the binary result and check feasibility against the original problem. A low objective value alone does not establish that all intended business requirements were represented correctly.

Three practical examples

A hypothetical scheduling model uses binary variables for assignment choices and pairwise penalties to discourage incompatible assignments occurring together.
A research prototype selects a subset of candidate features, balancing individual selection costs with interactions between selected features.
A teaching exercise encodes a small choice problem as QUBO, enumerates every possible binary assignment and checks that the best mathematical solution matches the stated requirements.

Think of it this way

Think of a control panel of on-off switches. Each switch changes the score, and some pairs of switches change it further when both are on. The task is to find the best configuration. The analogy captures binary choices and interactions, but real formulations can require many switches and carefully weighted penalties that make search difficult.

Worked example

Choose exactly one of two options. Let x1 and x2 indicate selection, with costs 3 and 2. Add a penalty of 10 for violating x1 + x2 = 1. The objective is 3x1 + 2x2 + 10(x1 + x2 − 1)². Using binary identities, this becomes 10 − 7x1 − 8x2 + 20x1x2. The four assignments have scores: neither selected, 10; first only, 3; second only, 2; both, 15. Selecting the second option is optimal and satisfies the requirement. The constant 10 can be dropped for optimization without changing the best assignment. This small example does not establish a suitable penalty size for larger problems.

Illustrative case study

A fictional event-planning team investigates QUBO for assigning sessions to limited rooms. Analysts first build a tiny version with known answers, separating preferences from mandatory restrictions. They test several penalty weights and inspect every proposed result for scheduling conflicts. The team compares the complete process with an established classical scheduling solver, including formulation and repair time. If the QUBO approach returns an infeasible schedule, staff do not treat a favorable score as success. The pilot evaluates a particular model and solver combination; it does not assume that adopting the formulation brings a computational advantage.

Common misconceptions and mistakes

QUBO is not synonymous with quantum optimization. “Unconstrained” does not mean invalid schedules or impossible selections are acceptable. Penalties that are too weak can let the optimizer prefer violations, while extremely large penalties can create numerical or hardware-resolution difficulties. A heuristic result need not be globally optimal. Also check matrix conventions: storing pairwise coefficients in an upper-triangular matrix differs from splitting them across a symmetric matrix. Confusing these conventions can double interactions and silently change the problem being solved.

Business use

QUBO offers a common language for certain discrete decisions and can make alternative solvers easier to compare. Its usefulness depends on formulation quality and solution performance on the actual workload. Record which restrictions are mandatory, how penalty weights were chosen and how results are verified. Compare total elapsed time, feasibility and objective quality with relevant alternatives. Where optimality matters, ask for a certificate or a valid bound rather than accepting the best sample as proof. Keep the original business objective understandable outside its encoded mathematical form.

Check your understanding

In the two-option example, why does choosing neither receive a score of ten?

Answer: It avoids selection costs but incurs the exact-one penalty.

Why can the constant term be removed?

Answer: It changes all assignment scores equally.

What should you do before accepting a solver's output?

Answer: Decode the choices, verify original restrictions and evaluate the original objective, including any claimed optimality evidence.

Related terms

Ising model
Penalty method
Binary quadratic model
combinatorial optimization
quantum annealing
integer programming

Learn next

Write out all assignments for a small QUBO and compare the encoded and original objectives. Then study penalty construction and matrix conventions. Explore exact and heuristic solvers with explicit feasibility checks before attempting a large operational problem.

Sources

D-Wave, QUBOs and Ising Models: https://docs.dwavequantum.com/en/latest/quantum_research/qubo_ising.html D-Wave, model concepts: https://docs.dwavequantum.com/en/latest/concepts/models.html The two-option calculation and event-planning scenario are original illustrations. They make no claim of quantum advantage or measured commercial performance. Independent review consulted D-Wave's QUBO definition, upper-triangular coefficient convention and penalty-formulation example. Independently expanding and enumerating the original two-option objective confirms both its coefficients and all four scores.

Previous: Quadratic programming Next: Quadrature mirror filter