Wonderrecept

De eerste fatsoenlijke quantumcomputer zal nog vele jaren op zich laten wachten, maar dat weerhoudt informatici er niet van listige rekenvoorschriften te ontwerpen die de voordelen van zo'n machine ten volle uitbuiten. Deze week publiceert Edward Farhi van het Massachusetts Institute of Technology in Cambridge (VS) samen met collega's in Science een nieuwe klasse van quantumalgoritmes die notoir lastige problemen fundamenteel sneller oplossen dan gewone computers voor elkaar krijgen. Dat wil zeggen: als een simulatie van beperkte omvang niet bedriegt.

Werkt een gewone (klassieke) computer met bits die óf op 0 óf op 1 staan, een quantumcomputer is uitgerust met qubits die ook nog eens `mengtoestanden' van 0 én 1 kunnen aannemen. Dat geeft een quantumcomputer extra mogelijkheden om informatie te verwerken die zijn klassieke tegenpool moet missen. Zo kan een quantumcomputer veel sneller een reuzengetal in priemfactoren ontbinden dan een gewone computer, en leidt een quantumzoektocht in een database in veel minder stappen tot het gewenste resultaat.

De Mount Everest van de informatica is een klasse van problemen die luistert naar de naam `NP-compleet'. Algoritmes die deze krakers te lijf gaan kampen stuk voor stuk met het nadeel dat het aantal benodigde stappen om het probleem op te lossen exponentieel stijgt met het gestaag toenemen van de input. Het bekendste voorbeeld is het handelsreizigerprobleem: vind de kortste route langs een aantal steden met als voorwaarde dat ze alle eenmaal worden aangedaan. Bij tien steden is het aantal mogelijke routes al opgelopen tot 362.880 en bij een nog hoger aantal loopt de rekentijd om tot de oplossing te komen dan ook gierend uit de hand. Het wereldrecord voor dit probleem staat op dit moment op 3038 steden.

Vele jaren hebben wiskundigen zich het hoofd gebroken over de vraag of er een algoritme valt te bedenken dat bij het kraken van een NP-compleet probleem het aantal benodigde stappen niet exponentieel ziet oplopen, maar bijvoorbeeld kwadratisch. Het is ze nog altijd niet gelukt. De gangbare opvatting is — een keihard bewijs ontbreekt — dat kwadratische (of vergelijkbare) oplossingen niet bestaan. Wel is bewezen dat als er onverhoeds voor één probleem uit de serie NP-compleet, zoals dat van de handelsreiziger, alsnog een snel algoritme opduikt, dit direct te gebruiken is om ook alle andere NP-complete problemen te lijf te gaan.

Het algoritme dat Farhi en zijn collega's bedachten maakt gebruik van een specifiek quantumgedrag (adiabatische evolutie) waarbij het systeem in de buurt van de laagste energietoestand blijft. Ze pasten het toe op het zogeheten Exact Cover-probleem, lid van de klasse NP-compleet. Uitgangspunt is een aantal bits, waarvan allerlei trio's aan specifieke eisen moeten voldoen. Bijvoorbeeld: van de bitnummers 2, 7 en 16 moet er een op één staan en beide andere op nul. De vraag is dan of er een serie nullen en enen te bedenken valt die aan alle eisen voldoet. Bij een klassiek algoritme groeit het aantal stappen om een en ander uit te zoeken exponentieel bij toenemende aantallen bits.

Het quantumalgoritme van Farhi levert gegarandeerd de oplossing van een Exact Cover-probleem, mits de rekentijd lang genoeg mag zijn. Dat is weinig bijzonder. Om uit te zoeken of `lang genoeg' in de praktijk werkbaar is, heeft het team van Farhi, bij gebrek aan een quantumcomputer, het algoritme getest via een serie simulaties op een partij gewone computers. Men liet eenvoudig een gewone computer na elkaar alle stappen uitvoeren die een quantumcomputer in een klap zou hebben gefikst. Bij een Exact Cover met 20 bits komt dat neer op het oplossen van een serie vergelijkingen met maar liefst 2.097.152 variabelen. De computers van Farhi hadden een paar maanden nodig om die monsterklus te klaren. Ter controle werd het probleem ook opgelost door alle mogelijke bitseries uit te schrijven en die naast de partij eisen te leggen. Bij 20 bits is een standaardcomputer met die opdracht in een handomdraai klaar.

Vervolgens gingen Farhi en zijn medewerkers na hoe lang het in de praktijk duurde eer de `quantumcomputer' de oplossing gevonden had. Verder dan 20 bits kon Farhi niet gaan: dan liep de rekentijd uit de hand. Aan welk eisenpakket Exact Cover moest voldoen, werd bepaald door het toeval. Alleen de `moeilijke' gevallen telden mee voor het eindresultaat. Voor ieder aantal bits tussen 10 en 20 werden 75 rekentijden voor het vinden van een Exact Cover-oplossing verzameld. Die rekentijden bleken (binnen de statistische marge) kwadratisch op te lopen met het aantal bits.

Betekent dit resultaat dat voor een NP-compleet probleem een kwadratisch algoritme is gevonden, zij het dat het moet draaien op een quantumcomputer? Dat zou een sensatie zijn. Zo'n vèrgaande conclusie is echter voorbarig en Farhi is de eerste om dat toe te geven. Het doorrekenen en akkoord bevinden van een beperkt aantal situaties is iets totaal anders dan het leveren van een sluitend wiskundig bewijs. Ter vergelijking: wie wil bewijzen dat vier kleuren volstaan om een landkaart te maken waarbij geen landen van gelijke kleur aan elkaar mogen grenzen, moet veel meer doen dan een willekeurige bladzijde uit de Bosatlas opslaan en nagaan of het klopt. Misschien is er een `gekke' kaart, zo vreemd dat geen atlas hem heeft, over het hoofd gezien. Evenzo bestaat bij Exact Cover in geval van grotere aantallen bits altijd het risico dat er complicaties op de loer liggen die het quantumalgoritme alsnog degraderen van spectaculair kwadratisch tot doodgewoon exponentieel. Maar houdt het resultaat van Farhi stand, en komen er inderdaad quantumcomputers, dan zijn de baten enorm.