Een variationale qubit-efficiënte MaxCut-heuristieke algoritme

Waarom kleine quantumchips ertoe doen voor grote puzzels

Veel taken uit de echte wereld — van het ontwerpen van schakelingen tot het modelleren van materialen — komen neer op het verdelen van een netwerk in twee groepen terwijl je zoveel mogelijk verbindingen tussen die groepen doorsnijdt. Deze uitdaging, bekend als MaxCut, is berucht moeilijk voor klassieke computers. Het artikel introduceert een nieuwe quantum-geïnspireerde methode die verrassend grote netwerken aankan met slechts een handvol quantumbits (qubits), en biedt een frisse manier om zowel quantum- als klassieke optimalisatietools te testen en te verbeteren.

Een netwerk in twee nuttige helften snijden

MaxCut stelt een ogenschijnlijk eenvoudige vraag: als je een verzameling punten (knooppunten) hebt verbonden door lijnen (edges), hoe moet je elk knooppunt kleuren, bijvoorbeeld blauw of wit, zodat zoveel mogelijk lijnen knooppunten van verschillende kleuren verbinden? Die best mogelijke splitsing is waardevol in gebieden als schakelingontwerp en statistische fysica, maar is erg moeilijk precies te vinden wanneer het netwerk groot is. Een veelgebruikte klassieke benadering, het Goemans–Williamson (GW) algoritme, maakt een slimme relaxatie van het probleem en garandeert een snede die minstens ongeveer 88% zo goed is als de echte optimale. Quantumcomputing belooft nieuwe manieren om zulke problemen aan te pakken, maar huidige apparaten zijn lawaaierig en beperkt in omvang, waardoor het moeilijk is om grote, diepe circuits uit te voeren.

Grote grafen oplossen met slechts een paar qubits

Standaard quantumbenaderingen zoals het Quantum Approximate Optimization Algorithm (QAOA) vereisen één qubit per knooppunt, dus een graf met 1.000 knooppunten zou 1.000 qubits nodig hebben — ver buiten de mogelijkheden van huidige machines. De nieuwe methode, Qubit-Efficient MaxCut (QEMC) genoemd, keert deze schaal om: ze gebruikt slechts ongeveer de logaritme van het aantal knooppunten, wat betekent dat 11 qubits informatie over meer dan 2.000 knooppunten kunnen coderen. In plaats van elke qubit aan één knooppunt te koppelen, gebruikt QEMC de volledige quantumtoestand als een compacte adresruimte en laat verschillende knooppunten overeenkomen met verschillende basisstaten van dit kleine register. Deze qubitzuinigheid houdt circuits ondiep en makkelijker uitvoerbaar op lawaaierige hardware, terwijl nog steeds zeer grote grafen worden weergegeven.

Knooppunten kleuren via waarschijnlijkheid in plaats van vaste staten

De belangrijkste innovatie is hoe QEMC de "kleur" van elk knooppunt codeert. In plaats van elk knooppunt in één quantumtoestand precies blauw of wit te dwingen, laat de methode de kleur van elk knooppunt afleiden uit hoe waarschijnlijk het is dat die staat bij meting verschijnt. Een knooppunt waarvan de bijbehorende basisstaat met lage waarschijnlijkheid voorkomt, wordt als de ene kleur behandeld; een knooppunt met hogere waarschijnlijkheid als de andere. Een drempel waarde scheidt de twee regimes. Dit betekent dat veel verschillende quantumtoestanden in wezen overeenkomen met dezelfde grafverdeling. De kostenfunctie die QEMC minimaliseert is zo opgebouwd dat verbonden knooppunten worden aangemoedigd aan verschillende zijden van deze waarschijnlijkheidsdrempel te vallen, wat de neiging heeft het aantal kruisingen tussen de kleurgroepen te vergroten en daarmee de snede te verbeteren.

Prestatie testen op echte en gesimuleerde machines

De auteurs testen QEMC op twee fronten: daadwerkelijke quantumprocessors en klassieke simulaties van de quantumcircuits. Op kleine reguliere grafen tot 32 knooppunten (met slechts 2 tot 5 qubits) vindt QEMC op IBM-supergeleiderhardware sneden die overeenkomen met of bijna overeenkomen met de beste mogelijke antwoorden gevonden door uitputtend zoeken, en presteert duidelijk beter dan willekeurige gissingen en eerdere quantumstudies gebaseerd op QAOA. In foutloze simulaties bereikt QEMC consequent meer dan 97% van de optimale snede voor deze kleine grafen. De kracht van de codering wordt nog duidelijker voor grotere grafen: voor 9-reguliere grafen tot 2.048 knooppunten verslaan klassieke simulaties van QEMC GW nog steeds zowel in gemiddelde als in beste sneden met enkele procentpunten, en vergelijkbare voordelen worden gezien op willekeurige grafen van 128 knooppunten met verschillende dichtheden.

Snelheid, beperkingen en quantum-geïnspireerde belofte

Ondanks het succes levert QEMC nog geen formele quantumversnelling op. Omdat het slechts ongeveer log N qubits gebruikt, schaalt het klassiek simuleren van de circuits ook ruwweg lineair met het aantal knooppunten, en neemt de tijd die nodig is om de kostenfunctie te evalueren toe met het aantal edges. Empirische studies suggereren dat de totale tijd om GW-niveau prestaties te bereiken ongeveer kwadratisch groeit met de graafgrootte, wat nog steeds praktisch haalbaar is voor veel problemen. Dit betekent dat QEMC in zijn huidige vorm meer fungeert als een krachtig quantum-geïnspireerd heuristisch algoritme dan als een bewijs van quantumvoordeel.

Wat dit werk betekent voor de toekomst

Voor de niet-specialist is de belangrijkste boodschap dat kleine, lawaaierige quantumapparaten nog steeds wetenschappelijk nuttig kunnen zijn als we algoritmen ontwerpen die aansluiten bij hun sterke punten. Door knooppuntkleuren te coderen in flexibele waarschijnlijkheidsbereiken in plaats van starre bitwaarden, gebruikt QEMC zeer weinig qubits om zeer grote netwerkproblemen aan te pakken en tolereert het van nature hardwarelawaai. De methode zet een nieuwe norm voor het testen van quantumoptimalisatie-algoritmen en levert ook een praktisch klassiek algoritme gebaseerd op dezelfde ideeën. Breder gezien laat het zien hoe het heroverwegen van informatieschema's — in plaats van alleen grotere machines te bouwen — veelbelovende wegen kan openen voor het oplossen van moeilijke computationele problemen.

Bronvermelding: 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

Trefwoorden: MaxCut, quantumoptimalisatie, variationale algoritmen, grafverdeling, quantum-geïnspireerde berekening