Mapping MaxCut to QUBO QUBO (Quadratic Unconstrained…
0 reactions
Mapping MaxCut to QUBO
QUBO (Quadratic Unconstrained Binary Optimization) shows up a lot in quantum optimization, but the core idea is actually pretty simple once you map it from a familiar problem.
Take MaxCut on a weighted graph:
You assign each node a binary variable (0 or 1)
The goal is to maximize the weight of edges that cross between the two partitions
You can rewrite this as a quadratic objective over binary variables:
Each edge contributes a term depending on whether its endpoints differ
Expanding this gives you a quadratic form: xᵀQx
The interesting part is:
The graph structure gets encoded directly into the Q matrix
Optimization becomes minimizing (or maximizing) a quadratic function over {0,1} variables
Example (2-node edge with weight w):
Contribution becomes something like: w(x₁ + x₂ - 2x₁x₂)
Scaling this up builds the full QUBO matrix.
What I find useful is thinking of QUBO as: → “just a way to turn combinatorial structure into a quadratic energy function”
This perspective makes it much less “quantum” and more like classical optimization with a different representation.
If anyone’s worked with QUBO in practice (classical or quantum solvers), I’d be curious:
Do you think in terms of matrices, or constraints first?
(There’s also a full walkthrough with a notebook demo here if you want more detail: https://youtu.be/P9sM2M-ahvs )
#technology #dev #programming
QUBO (Quadratic Unconstrained Binary Optimization) shows up a lot in quantum optimization, but the core idea is actually pretty simple once you map it from a familiar problem.
Take MaxCut on a weighted graph:
You assign each node a binary variable (0 or 1)
The goal is to maximize the weight of edges that cross between the two partitions
You can rewrite this as a quadratic objective over binary variables:
Each edge contributes a term depending on whether its endpoints differ
Expanding this gives you a quadratic form: xᵀQx
The interesting part is:
The graph structure gets encoded directly into the Q matrix
Optimization becomes minimizing (or maximizing) a quadratic function over {0,1} variables
Example (2-node edge with weight w):
Contribution becomes something like: w(x₁ + x₂ - 2x₁x₂)
Scaling this up builds the full QUBO matrix.
What I find useful is thinking of QUBO as: → “just a way to turn combinatorial structure into a quadratic energy function”
This perspective makes it much less “quantum” and more like classical optimization with a different representation.
If anyone’s worked with QUBO in practice (classical or quantum solvers), I’d be curious:
Do you think in terms of matrices, or constraints first?
(There’s also a full walkthrough with a notebook demo here if you want more detail: https://youtu.be/P9sM2M-ahvs )
#technology #dev #programming
| 3,000 mlx | |
| 3 | |
| 0 |