⚛️ quantum physics

Constrained Quantum Optimization at Utility Scale: Application to the Knapsack Problem

Deze studie presenteert de grootste succesvolle demonstratie van het oplossen van het knapsack-probleem met beperkingen op IBM Quantum-hardware (tot 150 qubits) door copula-QAOA te gebruiken, een methode die vaak betere resultaten oplevert dan klassieke benaderingen zoals Gurobi.

Oorspronkelijke auteurs: Naeimeh Mohseni, Julien-Pierre Houle, Ibrahim Shehzad, Giorgio Cortiana, Corey O'Meara, Adam Bene Watts

Gepubliceerd 2026-03-03

📖 4 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Naeimeh Mohseni, Julien-Pierre Houle, Ibrahim Shehzad, Giorgio Cortiana, Corey O'Meara, Adam Bene Watts

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

De Kern: Een Quantum-pakketjesservice voor de Energiekrant

Stel je voor dat je een gigantisch pakketje moet vullen met waardevolle spullen (zoals stroomopwekkende eenheden) voor een vrachtwagen (het elektriciteitsnet). Je hebt een strikte gewichtslimiet (de vraag van de stad) en elke spullen heeft een eigen prijs en gewicht. Je wilt de vrachtwagen zo vol mogelijk maken met de goedkoopste en beste spullen, zonder dat hij over zijn gewichtslimiet heen gaat.

Dit is in de echte wereld het "Unit Commitment" probleem: welke energiecentrales moeten aan en hoeveel stroom moeten ze leveren?

Het probleem is dat dit voor computers heel lastig is om perfect op te lossen, vooral als er duizenden opties zijn. Traditionele computers (zoals de superkrachtige "Gurobi") zijn goed, maar soms blijven ze steken of duren ze te lang.

De auteurs van dit artikel proberen iets nieuws: ze gebruiken een kwantumcomputer om dit pakketje te vullen. Maar kwantumcomputers zijn nu nog klein, onstabiel en hebben moeite met strikte regels (zoals "je mag niet zwaarder zijn dan 100 kg").

De Oplossing: De "Slimme Pakketjesservice" (Cop-QAOA)

De onderzoekers gebruiken een nieuwe methode genaamd Cop-QAOA. Hier is hoe dat werkt, vertaald naar een simpele analogie:

Het Probleem met de "Normale" Kwantumcomputer:
Stel je een kwantumcomputer voor als een groepje mensen die blindelings in een donkere kamer proberen een perfecte stoelindeling te vinden. De meeste combinaties zijn echter onmogelijk (bijvoorbeeld: te zwaar, of een stoel staat op de deur). Een normale kwantumcomputer probeert alles te proberen, waardoor hij veel tijd verspilt aan onmogelijke oplossingen.
De Slimme Start (Warm Start):
In plaats van blind te beginnen, geven de onderzoekers de kwantumcomputer een voorspelling van een slimme mens (een "lazy greedy" algoritme). Het is alsof je de mensen in de kamer zegt: "Begin niet bij de deur, maar begin bij de hoek waar de meeste stoelen al staan." Dit noemen ze een "warm start". De computer begint dus al dicht bij een goede oplossing.
De "Gordijn" (Bias):
Normaal gesproken zouden ze de mensen dwingen om alleen op de juiste stoelen te staan. Maar dat is te moeilijk voor de huidige kwantumcomputers. In plaats daarvan gebruiken ze een gordijn (de "copula mixer"). Dit gordijn zorgt ervoor dat de mensen waarschijnlijk op de goede stoelen gaan zitten, zonder ze fysiek te dwingen. Als ze toch per ongeluk op een verkeerde stoel zitten, wordt die optie genegeerd. Het is alsof je de mensen zegt: "Probeer vooral in de buurt van de goede stoelen te blijven, maar als je even dwalen, is dat oké, zolang je maar niet de hele kamer plat legt."

Wat hebben ze ontdekt?

De onderzoekers hebben dit getest op IBM's echte kwantumcomputers (met tot 150 "qubits", oftewel 150 kwantum-deeltjes die als schakelaars fungeren).

Grootte: Dit is de grootste proef ooit gedaan met dit soort problemen op echte hardware (150 items).
Resultaat: De kwantumcomputer vond oplossingen die beter waren dan de slimme menselijke voorspelling (de "lazy greedy" methode).
De strijd met de Supercomputer: In sommige gevallen vond de kwantumcomputer zelfs een oplossing die net iets beter was dan die van de superkrachtige klassieke computer (Gurobi), die normaal gesproken de koning is in dit soort rekensommen.
Snelheid: De kwantumcomputer deed dit in minder dan 3 minuten (inclusief voorbereiding), terwijl de supercomputer urenlang kon rekenen zonder een betere oplossing te vinden.

De Uitdagingen (De "Ruis" in de Kamer)

Het is niet allemaal perfect. De kwantumcomputer is nog kwetsbaar voor "ruis" (foutjes door trillingen of warmte).

Op de simulator (virtuele computer): Alles werkte perfect.
Op de echte hardware: De computer maakte soms fouten. De "gordijnen" werden soms lek, waardoor de computer oplossingen vond die niet aan de regels voldeden (bijvoorbeeld: te zwaar). Hoe meer stappen ze deden (meer "diepte"), hoe meer fouten er optraden door de ruis.

Toch was het resultaat indrukwekkend: zelfs met die fouten kon de kwantumcomputer nog steeds betere oplossingen vinden dan de traditionele methoden, mits ze slim met de instellingen omgingen.

Conclusie in Eén Zin

Dit artikel laat zien dat we, zelfs met de huidige, nog niet-perfecte kwantumcomputers, al kunnen beginnen met het oplossen van complexe, reële problemen (zoals het regelen van stroomnetten) door slimme trucs te gebruiken om de computer te helpen de juiste kant op te kijken, zonder hem te dwingen tot onmogelijke taken. Het is de eerste keer dat dit op zo'n grote schaal (utility-scale) succesvol is getest.

Kortom: Ze hebben een kwantumcomputer leren "slim te gokken" in plaats van "blind te raden", en dat werkt zelfs beter dan de beste klassieke computers voor bepaalde lastige puzzels.

Titel: Constrained Quantum Optimization at Utility Scale: Toepassing op het Knapsack-probleem

Auteurs: Naeimeh Mohseni et al. (E.ON, Universiteit van Calgary, IBM Quantum)
Publicatiedatum: Februari 2026 (voorgesteld)

1. Het Probleem

De kern van dit onderzoek ligt in het oplossen van beperkte combinatorische optimalisatieproblemen op kwantumcomputers, specifiek op schaal die relevant is voor nutsbedrijven (utility scale).

Context: Het Unit Commitment (UC)-probleem in energiesystemen is cruciaal voor het bepalen welke generatoren aan- of uit moeten gaan om vraag te dekken binnen operationele beperkingen. Dit is een complex, beperkt probleem met zowel binaire (aan/uit) als continue variabelen.
Uitdagingen:
1. Beperkingen: Standaard variatiele kwantumalgoritmen (zoals QAOA) verkennen de volledige Hilbertruimte, terwijl de geldige oplossingen slechts een klein deel daarvan innemen. Het handhaven van deze beperkingen vereist vaak diepe circuits die niet haalbaar zijn op huidige "near-term" hardware.
2. Schaal: Bestaande kwantumtoepassingen voor UC zijn beperkt tot kleine probleemgroottes.
3. Classificatie: Hoewel het UC-probleem NP-hard is, kunnen moderne klassieke solvers (zoals Gurobi) veel praktische instanties snel oplossen. Het is daarom moeilijk om "harde" instanties te vinden die kwantumvoordeel tonen.

2. Methodologie

De auteurs hanteren een hybride aanpak die het UC-probleem reduceert tot een 1D-Knapsack-probleem en dit oplost met een aangepaste versie van QAOA.

A. Probleemreductie (UC naar Knapsack)

In plaats van het volledige UC-probleem met continue variabelen direct op de kwantumcomputer te lossen, gebruiken de auteurs de eerste-orde optimaliteitsvoorwaarden (KKT-voorwaarden).

Ze analyseren de marginaal kosten ( $D$ ) en elimineren analytisch de meeste continue variabelen ( $p_i$ ).
Hierdoor wordt het probleem gereduceerd tot een zuiver binaire optimalisatie (welke eenheden aan te zetten) voor een vaste $D$ .
Dit gereduceerde probleem is wiskundig equivalent aan het 1D-Knapsack-probleem, waarbij de "gewicht" de productiecapaciteit is en de "waarde" de kostenreductie.
De continue parameter $D$ wordt geoptimaliseerd via een klassieke zoektocht (bijv. bisectie), terwijl de kwantumcomputer het binaire deel oplost.

B. Copula-QAOA (cop-QAOA)

Voor het oplossen van het Knapsack-probleem gebruiken ze cop-QAOA, een hardware-efficiënte variant van QAOA die beperkingen handhaaft zonder de circuitdiepte te vergroten:

Gevoelige Initiële Toestand: In plaats van een uniforme superpositie, wordt de initiële toestand "vooringenomen" (biased) naar veelbelovende oplossingen. Dit wordt gedaan met een "warm-start" gebaseerd op een lazy greedy-heuristiek. Elke qubit heeft een specifieke waarschijnlijkheid om in staat $|1\rangle$ te zijn.
Copula-mixers: In plaats van een standaard transversale veldmixer, gebruiken ze een familie van copula-mixers. Deze zijn ontworpen om correlaties tussen qubits in te bouwen (specifiek anti-correlatie, $\theta = -1$ ) om de toestand dicht bij de geldige deelruimte te houden, zonder de complexiteit van diepe circuits.
Doel: De kwantumtoestand wordt naar geldige oplossingen getrokken, maar de beperkingen worden niet strikt afgedwongen (wat diepe circuits zou vereisen), maar via structuur in de initiële toestand en de mixer.

C. Experimenteel Opzet

Hardware: Experimenten uitgevoerd op de IBM Quantum hardware (processor ibm_kingston, Heron r2) met tot 150 qubits.
Foutreductie: Gebruik gemaakt van de Q-CTRL Performance Management Qiskit-functie (layout-optimalisatie, dynamische koppeling, AI-gedreven transpilatie) om ruis te onderdrukken.
Benchmarking: Vergelijking met:
- Lazy Greedy: Een klassieke heuristiek.
- Gurobi: Een state-of-the-art klassieke solver.
- Random Sampler: Om te tonen dat willekeurige sampling faalt voor deze instanties.
Instanties: Specifiek geselecteerde "harde" instanties (o.a. "Inversely Strongly Correlated") waar Gurobi moeite heeft om een optimaliteitsgap van nul te bereiken binnen redelijke tijd.

3. Belangrijkste Resultaten

Schaal: Dit is de grootste succesvolle demonstratie van het Knapsack-probleem op IBM Quantum hardware, met 150 qubits.
Kwaliteit van Oplossing:
- cop-QAOA vindt systematisch betere oplossingen dan de lazy greedy-baseline.
- Op specifieke, moeilijke instanties (waar Gurobi moeite heeft), presteert cop-QAOA vergelijkbaar met of zelfs iets beter dan Gurobi (bijv. een betere best-found waarde op een 100-item instantie).
- De benaderingsratio (approximation ratio) verbetert met het aantal QAOA-rondes ( $p$ ).
Validiteit:
- Op de simulator neemt het percentage geldige oplossingen toe met $p$ .
- Op echte hardware daalt het percentage geldige oplossingen echter bij hogere $p$ (vanwege ruis), maar zelfs met een lager percentage geldige samples, blijft de beste gevonden oplossing concurrerend.
Training: De auteurs tonen aan dat het optimaliseren van variatiele parameters uitdagend is (plateaus in de kostenfunctie), maar dat een slimme initialisatie (grid search op $p=1$ ) leidt tot betere resultaten. Er is een opmerkelijke gelijkenis in parameterlandschappen tussen verschillende instanties, wat suggereert dat parameters mogelijk overdraagbaar zijn.

4. Bijdragen en Significantie

Utility-Schaal: Het artikel bewijst dat beperkte combinatorische optimalisatie op schaal die relevant is voor de industrie (tot 150 eenheden/qubits) haalbaar is op huidige kwantumhardware.
Efficiëntie: Het toont aan dat het gebruik van biased initial states en constant-depth mixers (cop-QAOA) een praktische oplossing biedt voor beperkte problemen, zonder de circuitdiepte te laten exploderen.
Klassieke Concurrentie: Het is een van de eerste werken dat aantoont dat een variatiele kwantumalgoritme op echte hardware oplossingen kan vinden die concurreren met of zelfs superieur zijn aan de beste klassieke solvers (Gurobi) voor specifieke, zorgvuldig geselecteerde "harde" instanties.
Praktische Toepassing: De reductie van het Unit Commitment-probleem naar een Knapsack-probleem biedt een blauwdruk voor het toepassen van kwantumcomputing op complexe energievraagstukken in de toekomst.

Conclusie

De auteurs demonstreren dat cop-QAOA een veelbelovende route is voor constrained optimization op near-term hardware. Hoewel ruis nog steeds een beperkende factor is voor de consistentie van geldige samples, is de kwaliteit van de beste gevonden oplossingen indrukwekkend. Dit werk markeert een belangrijke stap in de richting van praktische kwantumvoordeel voor industriële optimalisatieproblemen.