QED

Shors algoritme is het bekendste voorbeeld van een algoritme voor een kwantumcomputer. Het laat toe om getallen te factoriseren, en dat veel efficiënter dan op een klassieke computer kan. Net zoals bij de vierkleurenstelling gebeurt, overschaduwt dit algoritme alle andere kwantumalgoritmes. Vaak wordt Shors algoritme ten onrechte het eerste algoritme voor een kwantumcomputer genoemd. Zo schrijf Jacob West in zijn introductie The Quantum Computer:

Peter Shor, a research and computer scientist at AT&T’s Bell Laboratories in New Jersey, provided such an application by devising the first quantum computer algorithm.

Joe Pappalardo schrijf in het artikel Researchers Cast Wary Eye On Atomic-Level Computing in National Defense Magazine:

Peter Shor, a researcher at AT&T’s Bell Laboratories and now at MIT, devised the first quantum computer algorithm in the 1990s.

Net zoals bij het vierkleurenprobleem dat ten onrechte als eerste door een computer bewezen stelling gezien wordt, is de mythe dat Shors algoritme het eerste algoritme voor kwantumcomputers is, wijdverspreid. Ok, Shors algoritme is het eerste belangrijke algoritme dat voor kwantumcomputers ontwikkeld is. Getallen efficiënt factoriseren is de heilige graal van heel wat wiskundigen, maar ook van de NSA: een kwantumcomputer die grote getallen kan factoriseren, kan alle publieke encryptiemethodes kraken, die net gebaseerd zijn op het feit dat grote getallen met twee priemfactoren heel moeilijk te factoriseren zijn. Peter Shors uitvinding van het algoritme is ook een heel inventief staaltje wiskunde.

Dat neemt echter niet weg dat het niet het eerste kwantumalgoritme was. Die eer lijkt mij te moeten gaan naar het Deutsch-Jozsa algoritme, dat uit 1992 dateert. Het probleem dat het kan oplossen is dit: f is een Booleaanse functie van {1, …, N} naar {0, 1} met N=2ⁿ . We weten dat f(i) ofwel altijd gelijk is aan 0 (constant), ofwel dat de helft van de functiewaarden 0 is en de andere helft 1 (evenwichtig). Gevraagd is te weten te komen of f constant of evenwichtig is. Een klassiek deterministisch algoritme heeft in het slechtste geval 2^n-1 + 1 evaluaties van de functie nodig om het antwoord te geven. Het kwantumalgoritme van Deutsch en Jozsa lost het met één vraag exact op. Het lijkt een toy problem, maar het was de inspiratie tot meer algoritmes, zoals Simons algoritme (1993), een probabilistisch algoritme waarop Shor voortbouwde. De publicatie: David Deutsch en Richard Jozsa, “Rapid solutions of problems by quantum computation”, Proceedings of the Royal Society of London, Series A, Vol. 439, pp. 553-558 (1992).

Addendum: het eerste kwantumalgoritme dateert eigenlijk van nòg eerder: 1989. Het Deutsch-Jozsa algoritme uit 1992 generaliseert het algoritme van Deutsch, gepubliceerd in David Deutsch, “Quantum computational networks”, Proceedings of the Royal Society of London, Series A, Vol. 425, pp. 73-90 (1989).