En variational kvantbitt-effektiv MaxCut-heuristik

Varför små kvantchip spelar roll för stora pussel

Många verkliga uppgifter — från att lägga ut kretskort till att modellera material — handlar i grunden om att dela upp ett nätverk i två grupper samtidigt som man skär så många förbindelser mellan dem som möjligt. Denna utmaning, känd som MaxCut, är ökänd för att vara svår för vanliga datorer. Artikeln introducerar en ny kvantinspirerad metod som kan hantera förvånansvärt stora nätverk med bara ett fåtal kvantbitar (qubits), vilket erbjuder ett nytt sätt att testa och förbättra både kvant- och klassiska optimeringsverktyg.

Att dela ett nätverk i två användbara halvor

MaxCut ställer en enkelt formulerad fråga: om du har en uppsättning punkter (noder) förbundna med linjer (kanter), hur ska du färglägga varje nod, till exempel blå eller vit, så att så många linjer som möjligt förbinder noder av olika färg? Den bästa möjliga uppdelningen är värdefull inom områden som kretsdesign och statistisk fysik men är mycket svår att hitta exakt när nätverket är stort. En ofta använd klassisk metod, Goemans–Williamson (GW)-algoritmen, gör en smart relaksering av problemet och garanterar att den hittar ett snitt som är åtminstone omkring 88 % så bra som det sanna optimala. Kvantberäkning lovar nya angreppssätt för sådana problem, men dagens enheter är brusiga och begränsade i storlek, vilket gör det svårt att köra stora, djupa kretsar.

Lösa stora grafer med bara några få qubits

Standardkvantmetoder som Quantum Approximate Optimization Algorithm (QAOA) kräver en qubit per nätverksnod, så en graf med 1 000 noder skulle kräva 1 000 qubits — långt bortom dagens maskiner. Den nya metoden, kallad Qubit-Efficient MaxCut (QEMC), vänder på denna skalning: den använder bara ungefär logaritmen av antalet noder, vilket innebär att 11 qubits kan koda information om mer än 2 000 noder. Istället för att knyta varje qubit till en enskild nod använder QEMC hela det kvantmekaniska tillståndet som ett kompakt adressutrymme och låter olika noder motsvara olika basstånd i detta lilla register. Denna kvbitbesparande strategi håller kretsarna grunda och lättare att köra på brusig hårdvara, samtidigt som mycket stora grafer fortfarande kan representeras.

Färglägga noder efter sannolikhet istället för fasta tillstånd

Den viktigaste nyheten är hur QEMC kodar varje nods ”färg”. Istället för att tvinga varje nod att vara exakt blå eller vit i ett enskilt kvanttillstånd låter metoden varje nods färg härledas från hur sannolikt det är att den observeras vid mätning. En nod vars basstånd förekommer med låg sannolikhet behandlas som en färg; en nod med högre sannolikhet behandlas som den andra. En tröskelvärde skiljer de två lägena åt. Det innebär att många olika kvanttillstånd motsvarar i praktiken samma grafuppdelning. Kostnadsfunktionen som QEMC minimerar är uppbyggd så att förbundna noder uppmuntras att hamna på motsatta sidor om denna sannolikhetströskel, vilket tenderar att öka antalet kanter som korsar mellan de två färggrupperna och därmed förbättrar snittet.

Testa prestanda på verkliga och simulerade maskiner

Författarna testar QEMC på två fronter: faktiska kvantprocessorer och klassiska simuleringar av de kvantkretsar som används. På små reguljära grafer med upp till 32 noder (med bara 2 till 5 qubits) hittar QEMC som körs på IBM:s supraledande hårdvara snitt som matchar eller nästan matchar de bästa möjliga svaren funna genom uttömmande sökningar, och överträffar tydligt slumpmässiga gissningar och tidigare kvantstudier baserade på QAOA. I brusfria simuleringar når QEMC konsekvent över 97 % av det optimala snittet för dessa små grafer. Kodningens styrka blir ännu tydligare för större grafer: för 9-reguljära grafer med upp till 2 048 noder slår klassiska simuleringar av QEMC fortfarande GW både i genomsnitt och i bästa snitt med några procent, och liknande fördelar ses för slumpgrafer med 128 noder och olika densiteter.

Hastighet, begränsningar och kvantinspirerat löfte

Trots sina framgångar levererar QEMC ännu ingen formell kvantövertag. Eftersom den använder bara ungefär log N qubits skalar även klassiska simuleringar av dess kretsar ungefär linjärt med antalet noder, och tiden som krävs för att utvärdera kostnadsfunktionen växer med antalet kanter. Empiriska studier tyder på att total tid för att nå GW-nivå prestanda växer ungefär kvadratiskt med grafens storlek, vilket fortfarande är praktiskt hanterbart för många problem. Det innebär att QEMC i sin nuvarande form snarare fungerar som en kraftfull kvantinspirerad heuristik än som ett bevis på kvantmässig fördel.

Vad detta arbete betyder för framtiden

För en icke-specialist är huvudbudskapet att små, brusiga kvantenheter fortfarande kan vara vetenskapligt användbara om vi utformar algoritmer som matchar deras styrkor. Genom att koda nodfärger i flexibla sannolikhetsintervall snarare än i rigida bitvärden använder QEMC mycket få qubits för att angripa mycket stora nätverksproblem och tolererar naturligt hårdvarubrus. Metoden sätter en ny referenspunkt för att testa kvantoptimeringsalgoritmer och ger också en praktisk klassisk algoritm baserad på samma idéer. Mer allmänt visar den hur omprövning av hur information kodas — snarare än att bara bygga större maskiner — kan öppna lovande vägar för att lösa svåra beräkningsproblem.

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

Nyckelord: MaxCut, kvantoptimering, variationsalgoritmer, grafuppdelning, kvantinspirerad beräkning