Nieuwe hoop op quantumrekenen

Adepten van de quantumcomputer hebben een fikse opsteker aan een artikel dat deze week in het Amerikaanse weekblad Science verscheen (20 april)....

Quantumcomputers maken gebruik van de ingebouwde schimmigheid van de quantumwereld, waarin systemen tegelijk in verschillende toestanden kunnen verkeren. Daardoor zouden ze, met de juiste rekenprocedures (algoritmes), veel sneller kunnen rekenen dan gewone computers, die stap voor stap werken.

Theoretisch fysicus Adward Farhi en collega's ontwierpen een quantumalgoritme voor het oplossen van de ernstigst onkraakbare vraagstukken uit de wiskunde, zogenoemde NP-complete problemen, zoals het handelsreizigersprobleem. Om uit te rekenen wat de kortste route langs een groot aantal steden is, is een aantal rekenstappen nodig dat zeer snel - exponentieel - uit de hand loopt. Voor meer dan een paar duizend steden is geen oplossing bekend.

De onderzoekers bootsten het quantum-algoritme na op een gewone computer. De rekentijd nam minder dan exponentieel toe en bleef daarmee ruim binnen praktisch haalbare grenzen, schrijven ze in Science.

Vorig jaar loofde het Clay-instituut voor wiskunde in Cambridge Massachussetts een miljoen dollar uit voor een algoritme dat een NP-compleet probleem in polynomiale tijd oplost. Farhi's werk komt daarvoor niet in aanmerking, heeft hij direct aangegeven. Daarvoor is eerst een echte quantumcomputer nodig.

Meer over