A Variational Qubit-Efficient MaxCut Heuristic Algorithm

Why tiny quantum chips matter for big puzzles

Many real-world tasks—from laying out computer circuits to modeling materials—boil down to separating a network into two groups while cutting as many connections between them as possible. This challenge, known as MaxCut, is notoriously hard for ordinary computers. The article introduces a new quantum-inspired method that can handle surprisingly large networks using only a handful of quantum bits (qubits), offering a fresh way to test and improve both quantum and classical optimization tools.

Cutting a network into two useful halves

MaxCut asks a simple-sounding question: if you have a set of points (nodes) connected by lines (edges), how should you color each node, say blue or white, so that as many lines as possible link nodes of different colors? That best possible split is valuable in areas like circuit design and statistical physics but is very hard to find exactly when the network is large. A widely used classical approach, the Goemans–Williamson (GW) algorithm, does a clever relaxation of the problem and is guaranteed to find a cut that is at least about 88% as good as the true best. Quantum computing promises new ways to attack such problems, but current devices are noisy and limited in size, making it difficult to run large, deep circuits.

Solving big graphs with only a few qubits

Standard quantum approaches such as the Quantum Approximate Optimization Algorithm (QAOA) need one qubit per network node, so a 1,000-node graph would require 1,000 qubits—far beyond today’s machines. The new method, called Qubit-Efficient MaxCut (QEMC), flips this scaling on its head: it uses only about the logarithm of the number of nodes, meaning 11 qubits can encode information about more than 2,000 nodes. Instead of tying each qubit to a single node, QEMC uses the entire quantum state as a compact address space and lets different nodes correspond to different basis states of this small register. This qubit thrift keeps circuits shallow and easier to run on noisy hardware, while still representing very large graphs.

Coloring nodes by probability instead of fixed states

The key innovation is how QEMC encodes the “color” of each node. Rather than forcing every node to be exactly blue or white in a single quantum state, the method lets each node’s color be inferred from how likely it is to be observed in measurement. A node whose basis state appears with low probability is treated as one color; a node with higher probability is treated as the other. A threshold value separates the two regimes. This means that many different quantum states correspond to essentially the same graph partition. The cost function that QEMC minimizes is built so that connected nodes are encouraged to fall on opposite sides of this probability threshold, which tends to increase the number of edges crossing between the two color groups and therefore improves the cut.

Testing performance on real and simulated machines

The authors test QEMC on two fronts: actual quantum processors and classical simulations of the quantum circuits. On small regular graphs with up to 32 nodes (using only 2 to 5 qubits), QEMC run on IBM superconducting hardware finds cuts that match or nearly match the best possible answers found by exhaustive search, clearly outperforming random guessing and earlier quantum studies based on QAOA. In noiseless simulations, QEMC consistently reaches over 97% of the optimal cut for these small graphs. The power of the encoding becomes even more apparent for larger graphs: for 9-regular graphs with up to 2,048 nodes, classical simulations of QEMC still beat GW on both average and best cuts by a few percent, and similar advantages are seen on random graphs of 128 nodes with different densities.

Speed, limits, and quantum-inspired promise

Despite its success, QEMC does not yet deliver a formal quantum speedup. Because it uses only about log N qubits, classically simulating its circuits also scales roughly linearly with the number of nodes, and the time needed to evaluate the cost function grows with the number of edges. Empirical studies suggest the total time to reach GW-level performance grows about quadratically with graph size, which is still within practical reach for many problems. This means that QEMC, in its current form, serves more as a powerful quantum-inspired heuristic than as a proof of quantum advantage.

What this work means for the future

To a non-specialist, the main message is that small, noisy quantum devices can still be scientifically useful if we design algorithms that match their strengths. By encoding node colors in flexible probability ranges rather than rigid bit values, QEMC uses very few qubits to tackle very large network problems and naturally tolerates hardware noise. The method sets a new benchmark for testing quantum optimization algorithms and also yields a practical classical algorithm based on the same ideas. More broadly, it showcases how rethinking how information is encoded—rather than just making bigger machines—can open promising paths for solving hard computational problems.

Citation: Tene-Cohen, Y., Kelman, T., Lev, O. et al. A Variational Qubit-Efficient MaxCut Heuristic Algorithm. npj Quantum Inf 12, 50 (2026). https://doi.org/10.1038/s41534-026-01186-2

Keywords: MaxCut, quantum optimization, variational algorithms, graph partitioning, quantum-inspired computation