MaxCut with Fewer Qubits

Choose a qubit count, try a measurement, and see how often you recover the best split of a graph.

Split the vertices into two groups so that as many edges as possible join different groups. Each of those edges scores one point. The highest-scoring split is a MaxCut solution.

Start with 12 qubits, then try fewer. Press Try once to see one result, or Try 100 times to see how often a best result appears.

This demonstration was built with generative AI.

Preparing the demo…

What to look for

The blue and orange vertices are the two groups. The highlighted edges score points. The score beside the graph shows the latest result; the best possible score stays fixed for each graph.

The large percentage is the calculated chance that one measurement returns a best result. The trial counter shows what happened in your samples. Those two numbers can differ, especially after only a few trials.

Fewer qubits save resources, but can make a best result less likely. The exact chance depends on the graph and encoding. This demo calculates an ideal quantum state first, then samples its measurement outcomes.

Each of the 12 vertices is represented by one classical bit. The four choices use (1,1), (2,1), (3,1), or (3,2) quantum random access codes (QRACs):

Qubits Encoding Packing
12 (1,1) One vertex per qubit
6 (2,1) Two vertices per qubit
4 (3,1) Three vertices per qubit
8 (3,2) Three vertices per two qubits

The app groups vertices automatically, trying to keep connected vertices in different code blocks. The grouping stays fixed while you repeat measurements. Other groupings can give different probabilities.

For an assignment s, \operatorname{Cut}(s) counts the edges between the two groups. With simultaneous measurement effects \{M_s\}, the model uses

H_{\mathcal D}=\sum_s \operatorname{Cut}(s)M_s.

This Hamiltonian measures the expected score after decoding. The ideal state maximizes that expected score. When several states share the maximum, the app uses the equal mixture on their common maximum-eigenvalue subspace:

\rho_\star=\frac{\Pi_{\max}}{\operatorname{Tr}\Pi_{\max}}.

The probability displayed above is

p_{\mathrm{opt}} =\sum_{s:\,\operatorname{Cut}(s)=\mathrm{OPT}} \operatorname{Tr}(M_s\rho_\star).

It counts every optimal split, including swapping the names of the two groups. The app checks all 2^{12}=4096 classical assignments to find the best score.

The 12-qubit reference gives 100% because it assumes that an ideal optimal state has already been prepared. Preparing that state is a separate task; this demo models the resulting readout. Trials are independent samples from the same calculated distribution, with no hardware noise.

The model follows Decoder-Consistent Hamiltonians for POVM-Based Quantum Relaxations. The one-qubit encodings follow Approximate Solutions of Combinatorial Problems via Quantum Relaxations, and the (3,2) code follows Quantum-Relaxation Based Optimization Algorithms: Theoretical Extensions.