Skip to content

How to solve Max-Cut with a quantum-inspired solver

Map a Max-Cut graph problem to an Ising model and solve it with Simulated Bifurcation, a classical algorithm modelled on the dynamics of a quantum bifurcation machine. Uses pqblocks-bifurcation.

Not cryptography

Quantum-inspired classical optimisation: not cryptography, no security claim.

The problem

Max-Cut splits the nodes of a graph into two groups so that the total weight of edges between the groups is as large as possible. It is NP-hard and appears in circuit layout, clustering and portfolio problems. Many such problems can be written as an Ising model or a QUBO, and quantum-inspired heuristics find good solutions quickly on an ordinary CPU.

Install

pip install git+https://github.com/PQBlocks/simulated-bifurcation

Complete working code

qubo_maxcut.py
"""Solve a small Max-Cut problem with Simulated Bifurcation (pqblocks-bifurcation).

Quantum-inspired classical optimisation: not cryptography, no security claim.
Max-Cut maps to an Ising model with J_ij = w_ij; the cut value of spins s is sum w_ij (1 - s_i s_j) / 2.
"""
import itertools

import numpy as np
from pqblocks_bifurcation.solver import SimulatedBifurcationSampler

# A 6-node ring with one chord; every edge has weight 1.
edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0), (0, 3)]
n = 6
W = np.zeros((n, n))
for i, j in edges:
    W[i, j] = W[j, i] = 1.0


def cut_value(spins):
    return sum(W[i, j] * (1 - spins[i] * spins[j]) / 2 for i, j in edges)


# A heuristic: take the best of several independent reads.
best_spins = max((SimulatedBifurcationSampler(seed=s, mode="dSB").sample_ising(W, np.zeros(n))[0]
                  for s in range(8)), key=cut_value)
found = cut_value(best_spins)

# The graph is tiny, so brute force tells us whether the heuristic reached the optimum.
optimum = max(cut_value(np.array(b)) for b in itertools.product((-1, 1), repeat=n))
print("partition:", best_spins.tolist(), "| cut:", found, "| optimum:", optimum)
assert found <= optimum

Output:

partition: [-1, 1, -1, 1, -1, 1] | cut: 7.0 | optimum: 7.0

How it works

  1. Each node gets a spin s_i = ±1, which says which side of the cut it is on.
  2. With couplings J_ij = w_ij, minimising the Ising energy Σ J_ij s_i s_j maximises the cut Σ w_ij (1 − s_i s_j) / 2.
  3. Simulated Bifurcation (Goto et al., Science Advances 2019 and 2021) evolves continuous oscillators that bifurcate into ±1 states. The discrete variant (mode="dSB") is used here.
  4. It is a heuristic: take the best of several independent reads (different seeds). On this small graph, brute force confirms the optimum was reached.

Things to know

  • For graphs beyond a few dozen nodes brute force is impossible. Compare solvers with pqblocks-qubo-bench (time-to-solution).
  • Build and convert QUBO / Ising models with pqblocks-qubo.