• Voor sommige moeilijke problemen, zoals het ontbinden van natuurlijke getallen in priemfactoren, het opstellen van een collegerooster of het handelsreizigersprobleem, hebben de huidige algoritmes een exponentieel aantal bewerkingen nodig, maar kwantumcomputers kunnen dit veel sneller omdat ze alle mogelijkheden tegelijk kunnen beschouwen.
   
• Een klassieke chip bevat logische circuits opgebouwd uit logische schakelingen zoals OR, AND en NOT. Een kwantumpoort heeft qubits als ingangen en uitgangen. Bijvoorbeeld, bovengenoemde beam-splitter realiseert de zogenaamde Hadamardpoort, die geen tegenpool heeft met een klassieke poort. Deze poort heeft één qubit-ingang en één qubit-uitgang. Een andere belangrijk voorbeeld is de cNOT-poort, een 2-qubit-poort die samen met de Hadamardpoort voldoende is om de universele Turing-kwantummachine te simuleren, zoals beschreven door David Deutsch, en dus in principe voldoende om alles te berekenen in onze macro- en micro-wereld.
   
• In de wiskundige beschrijving worden de kwantumtoestanden voorgesteld als vectoren in een Hilbertruimte, en de kwantumpoorten als unitaire operatoren binnen deze ruimte. Maar voordat je je tijdens de koffiepauze op het werk bezondigt aan name-dropping in deze materie, zou ik eerst een en ander bestuderen.  
   
• Het prepareren van qubits mag dan een technologisch huzarenstukje zijn, de echte uitdaging bij de bouw van een kwantumcomputer is het geïsoleerd houden van de kwantumcircuits zodat er geen interactie is met de omgeving. Want zodra er tijdens de berekenen ook maar iets kan gemeten worden, zodra er vroegtijdig informatie lekt, dreigen kwantumtoestanden in te storten met onnauwkeurigheden tot gevolg. Dit wordt het decoherentieprobleem genoemd. Om deze reden zijn de circuits van de huidige kwantumprocessoren gemaakt met supergeleiders, en functioneren ze meestal bij temperaturen dicht bij het absolute nulpunt, wat uiteraard een beperking geeft op het praktische gebruik.
   
• In dit verband is het principe van Landauer uit 1961 erg belangrijk. Telkens als tijdens een computerberekening een bit aan informatie verloren gaat, dan komt er een beetje energie vrij. Vergeten doet opwarmen. Dit is bijvoorbeeld het geval bij een AND-poort, die twee ingangen heeft maar slechts één uitgang. Maar kwantumberekeningen gebruiken gelukkig poorten die voorgesteld worden door unitaire operatoren en zijn per definitie altijd omkeerbaar.
   
• Behalve het principe van superpositie, verantwoordelijk voor het parallellisme bij kwantumcomputers, is er nog een ander kwantumfenomeen dat een rol speelt in deze futuristische machines: kwantumverstrengeling. Dit betekent dat de kwantumtoestand van twee elementaire deeltjes met elkaar verbonden blijven, ook al worden ze uit elkaar getrokken. Dit is bijvoorbeeld nodig als we een berekening willen controleren, al is het maar om te kijken of deze afgelopen is. Wegens het decoherentieprobleem van kwantumcomputers (zie hierboven) moeten we kwantumcomputers hun werk laten doen in perfecte geïsoleerde omstandigheden, maar ooit willen we wel een uitlomst weten natuurlijk. Een theoretische oplossing stelt voor om de qubits op een onrechtstreeks manier te controleren, door observaties op andere maar hiermee verstrengelde deeltjes, zodat de kwantumtoestand van de qubits binnenin de kwantumcomputer niet in elkaar stort.  

Toegift 

Als extraatje, net buiten deze spoedcursus voor kwantumcomputers, nog een kort lesje in kwantummechanica. Hoe weten de kwantumspecialisten dat elementaire deeltjes zich, na een gebeurtenis met alternatieve uitkomsten, in een parallelle kwantumtoestand bevinden. Immers, vanaf het moment dat iemand dit wil testen, vanaf het ogenblik dat iemand er nog maar naar kijkt, stort de kwantumtoestand in om kleur te bekennen tot juist één van de uitkomsten. Gelukkig is een mens slim genoeg om zijn eigen klassiek-logisch redenerende brein buiten spel te zetten. Hieronder laten we een foton ongemoeid twee beam-splitters passeren en detecteren we pas daarna in welke toestand het zich bevindt.

De halfdoorlatende spiegels komen overeen met de stippellijntjes, en de twee volle lijntjes stellen volledig reflecterende spiegels voor. Een lichtdeeltje dat zoals in de figuur initieel naar beneden gericht is, kan “kiezen” tussen vier mogelijke trajecten: RR, RT, TR en TT, waarbij R staat voor reflectie en T voor transmissie bij de opeenvolgende beam-splitters . Merk op dat de trajecten RR en TT in het laatste trajectdeel opwaarts gaan en in de bovenste detector arriveren. Anderzijds resulteren trajecten RT en TR in een neerwaartse beweging die tegen de onderste fotondetector zal tikken. Als een foton voor iedere passage bij een halfspiegel effectief de knoop zou doorhakken, met 50% kans voor elk van de beide mogelijkheden, dan zouden de vier trajecten (RR, RT, TR, TT) even waarschijnlijk zijn (elk 25% kans). Als we dit experiment de hele dag zouden herhalen dan verwachten we dat tegen de avond de beide detectoren ongeveer evenveel fotonen geturfd hebben. Maar dat is niet zo: het blijkt dat alle fotonen bovenaan gedetecteerd worden (in een opwaartse beweging), geen enkel onderaan! Dit wordt foutloos voorspeld door de kwantummechanica. We tonen dit voor de neerwaarts invallende foton (zoals in de figuur), geassocieerd met basistoestand $\left| 1\right\rangle$:

Eerste halfspiegel:
$$\left| 1\right\rangle \mapsto \frac{1}{\sqrt{2}}\left| 0\right\rangle + \frac{1}{\sqrt{2}}\left| 1\right\rangle$$
Spiegel:
$$\mapsto \frac{1}{\sqrt{2}}\left| 1\right\rangle + \frac{1}{\sqrt{2}}\left| 0\right\rangle$$
Tweede halfspiegel:
$$\mapsto \frac{1}{\sqrt{2}}(\frac{1}{\sqrt{2}}\left| 0\right\rangle + \frac{1}{\sqrt{2}}\left| 1\right\rangle) + \frac{1}{\sqrt{2}}(\frac{1}{\sqrt{2}}\left| 0\right\rangle -\frac{1}{\sqrt{2}}\left| 1\right\rangle)$$ $$=\left| 0\right\rangle$$

Leestip 

Na vijftien jaar nog steeds overeind (en nog altijd een plezier om te herlezen):

The Feynman Processor, door Gerard J. Milburn, Perseus Books, 1998. 

Sinds het begin van deze maand weten we dankzij Edward Snowden dat de Amerikaanse nationale veiligheidsdienst NSA een budget van ongeveer $80 miljoen begroot heeft voor haar project Penetrating hard targets. Een belangrijke doelstelling van dit project is het kraken van de gangbare encryptie bij internetverkeer (RSA-codes) en omvat basisonderzoek naar kwantumcomputers.

Misschien klinken we nu verwend, maar we zijn de laatste tijd spectaculairdere lekken gewoon. Over heel de wereld proberen onderzoekers moeilijke codes te kraken om te testen hoe veilig ze zijn. En de kwantumcomputer is nu eenmaal een hot research item, je zou zelfs kunnen spreken van een academische race om als eerste zo’n effectief werkende machine te fabriceren. Voor zover we weten is de NSA verre van koploper in deze race en staat minder ver dan bijvoorbeeld  DARPA, de onderzoeksafdeling van de Amerikaanse defensie, maar ook minder ver dan instellingen in Canada, Rusland, China en Europa, met het onlangs opgerichte QuTech-centrum in Delft als een van de belangrijkste spelers.

Anderzijds veroorzaakte dit nieuwtje de echo’s van het woord “kwantumcomputer” op nieuwjaarsrecepties, tijdens koffiepauzes, in krantenartikelen en aandachtzoekende weblogs. Hoog tijd om ons jargon desaangaande te upgraden, om collega’s te imponeren of fondsaanvragen op te smukken.

Een spoedcursus in kwantumcomputers

• Insiders beweren dat de horizon voor de productie van de eerste kwantumcomputer die praktisch bruikbaar is, ligt op ongeveer vijftien tot twintig jaar. We zijn dus ruim op tijd met deze blog. Anderzijds zijn computerwetenschappers al twee decennia druk in de weer met het ontwerpen van algoritmes voor deze toekomstmachines. Juist hier ligt de verklaring voor de belangstelling van NSA en andere geldschieters in kwantumcomputers. Onthoud in deze kwestie vooral:  
   
  1. Het algoritme van Grover: kan gebruikt worden om veel sneller gegevensbanken te doorzoeken dan de bestaande software voor gewone computers. De huidig grootste implementatie van Grover’s algoritme op een kwantumprototype kan slechts databanken met acht gegevens doorlopen. Voorlopig is onze privacy dus niet in gevaar, maar weet wel dat Google in zijn laboratoria al langer dan zeven jaar experimenteert met dit kwantumzoekalgoritme. 
  2. Het algoritme van Shor: Peter Shor, een Amerikaanse wiskundeprofessor op MIT, ontwikkelde in 1994, als werknemer van Bell Laboratories, een sensationeel factorisatie-algoritme voor kwantumcomputers. Dit algoritme werkt veel sneller dan de exponentiële methodes voor de klassieke computers. Dit zal ons in de toekomst dwingen om het huidige digitale beveiligingssysteem volledig te herzien. Inderdaad, het leeuwenaandeel van onze bankverrichtingen en van internetverkeer wordt versleuteld door RSA-codes die er van uitgaan dat het onmogelijk is om binnen redelijke tijd een groot getal (van pakweg 1024 bitlengte) te ontbinden in priemfactoren. Bovendien was dit algoritme het juist antwoord op de Physics Bowl competition in de episode "The Bat Jar Conjecture" van de televisieserie The Big Bang Theory (zie afbeelding).
     In 2010 hebben onderzoekers een eenvoudige kwantumcomputer gemaakt die met fotonen werkt en ze zijn er in geslaagd hierop het algoritme van Shor te laten draaien. Met succes hebben ze 21 kunnen ontbinden als 7 $\times $ 3. Het grootste getal, naar ons weten, met kwantumsoftware ontbonden is $143 = 11\times 13$ (in 2012, weliswaar met het adiabatische factorisatiealgoritme). We wensen de NSA veel succes toe om met deze middelen RSA-1024 te kraken.
  3. Wie meer wil weten over kwantumalgoritmes, wie zelfs wil bijbenen, bevelen we graag de homepage van Stephen Jordan aan: Quantum Algorithm Zoo.

• In moeilijke tijden worden we al te dikwijls gesust met de gemeenplaats dat iedere crisis een opportuniteit is. Maar in dit verhaal is het zelfs zo dat de hindernis die de crisis veroorzaakte, tegelijkertijd de hefboom bleek voor de nieuwe opportuniteit. Zo worden we bijvoorbeeld geconfronteerd met de terminale diagnose voor de wet van Moore. Deze ingenieur bij Intel stelde in de jaren 60 dat het aantal transistors in een geïntegreerde schakeling om de twee jaar verdubbelt.  Maar de dichtheid van transistors op een chip stuit op een fysische beperking. Op het moment dat de steeds kleiner wordende schakelingen op atomair niveau gerealiseerd worden, moet met de spelregels van de kwantummechanica rekening gehouden worden. Het onzekerheidsprincipe van Heisenberg maakt transistors op microschaal onbetrouwbaar. Richard Feynman suggereerde in zijn voordracht op de First Conference on the Physics of Computation (1981) om deze onzekerheid nu net te gebruiken als principe voor een nieuw type computer. Feynman wordt dikwijls de vader van de kwantumcomputer genoemd (al beschreef de Russische wiskundige Yu Manin in 1980 reeds een principe van kwantumrekenen, en soms wordt Paul Benioff als de eerste theoretische grondlegger genoemd).
   
• Maar nog voordat hij zijn entree gemaakt heeft, veroorzaakt de kwantumcomputer nu dus al de volgende crisis als potentieel gevaar voor onze privacy en veiligheid (algoritmes van Grover en Shor). Maar ook hier speelt de kwantummechanica de dubbelrol van probleem en oplossing. Ze vormt namelijk de basis voor een nieuwe klasse van codes, kwantumcryptografie, waarvan Quantum Key Distribution (QKD) de bekendste is. Volgens dit principe worden boodschappen gecodeerd in kwantumtoestanden van lichtdeeltjes, en vanaf het moment dat ook maar iemand probeert de boodschap te onderscheppen en te lezen, worden deze kwantumtoestanden vernietigd. Deze ultra-veilige cryptografie is al commercieel beschikbaar en werd zelfs gebruikt om de Zwitserse verkiezingen in 2007 te beveiligen. In connectie met QKD staat de fameuze No-Cloning Theorem in kwantummechanica. Volgens deze stelling is het onmogelijk om een ongekende kwantumtoestand te kopiëren. Dit biedt ongeziene opportuniteiten voor het veilig bewaren van gegevens en het beschermen van auteursrechten.
   
• Klassieke computers opereren op bits, die elke juist één van twee waarden kunnen aannemen (uit/aan of 0/1). De eenheid van informatie in een kwantumcomputer is een qubit, een term bedacht door Benjamin Schumaker. Een qubit is de toestand van een elementair deeltje waarvoor twee waarneembare toestanden kunnen waargenomen worden. Bijvoorbeeld, de spinrichting van een elektron of de polarisatie van een lichtdeeltje. Je zou dus denken dat een qubit dezelfde binaire informatie bevat als een gewone bit. Maar het punt van de kwantummechanica is dat zolang we geen waarneming of meting uitvoeren op een elementair deeltje, het zich in een kwantumtoestand bevindt die de superpositie is van twee alternatieven.
   
• Een populaire illustratie in tekstboeken over kwantummechanica is een halfdoorlatende spiegel (beam-splitter), hieronder aangeduid met een onderbroken lijntje. Juist de helft van het invallende licht gaat door, de andere helft wordt weerkaatst. De twee bundels van de gesplitste lichtstraal vertonen dan ook de helft van de oorspronkelijke intensiteit. Tot hier de verteerbare kost, op het niveau van de dagelijkse waarnemingen.  

• Maar stel nu dat we de intensiteit van het invallende licht zodanig dimmen dat er slechts één elementair lichtdeeltje overblijft. We hebben de technologie om dit te realiseren, en bovendien ook om dit foton te detecteren (bijvoorbeeld met een fotomultiplicator). Indien we voorbij de “halfspiegel” twee zulke detectoren plaatsen, kunnen we de knoop doorhakken over het gedrag van dit foton: transmissie of reflectie. Als we dit experiment veelvuldig herhalen dan zullen de fotondetectoren elk ongeveer in de helft van de gevallen aantikken, zoals verwacht bij een halfdoorlatende spiegel. Maar mensen bewegen zich als lompe olifanten tussen de porseleinen deeltjes waaruit de wereld is opgebouwd. Indien er twee (elkaar uitsluitende) mogelijkheden zijn, bijvoorbeeld transmissie (T) of reflectie (R), wil ons beperkte brein de knoop doorhakken, maar stiekem gedraagt een foton zich subtieler, namelijk in een mengtoestand van T en R nadat het de beam-splitter gepasseerd is.

• De kwantumlogica verschilt dus drastisch van de vertrouwde binaire logica waarmee wij doorgaans de wereld willen begrijpen en waarop de klassieke computers gebaseerd zijn. Stel dat we twee mogelijk toestanden beschouwen voor een lichtdeeltje, naargelang het zich beweegt: neerwaarts (1) of opwaarts (0). Volgens de logica van de menselijke waarneming krijgen we na de ontmoeting met de beam-splitter, terug een binaire toestand (0 of 1). Bijvoorbeeld, als een neerwaarts invallende foton reflecteert dan krijgen we een opwaartse beweging, de 0 werd omgezet in een 1. Maar zonder menselijke metingen gehoorzaamt het foton de kwantumwetten, die voor de beam-splitter er als volgt uitzien:           
  $$\left| 0\right\rangle  \mapsto \frac{1}{\sqrt{2}}\left| 0\right\rangle -\frac{1}{\sqrt{2}}\left| 1\right\rangle$$ $$ \left| 1\right\rangle  \mapsto \frac{1}{\sqrt{2}}\left| 0\right\rangle + \frac{1}{\sqrt{2}}\left| 1\right\rangle$$
• De notatie $\left| 0\right\rangle$ of $\left| 1\right\rangle$ verwijst naar kwantumtoestanden die simultaan optreden, elk met een eigen gewicht $\pm 1/ \sqrt{2}$ (de waarschijnlijkheidsamplitudes), in tegenstelling tot de (waarneembare) binaire toestanden 0 en 1, die exclusief optreden. (Terzijde: deze rare notatie voor een kwantumtoestand wordt in het jargon een ket genoemd, en is de rechterhelft van de Diracnotatie of braketnotatie). We leggen niet uit hoe de juiste waarden voor de waarschijnlijkheidsamplitudes berekend worden, die soms zelfs complexe getallen zijn, dat zijn dingen die je leert in een cursus kwantummechanica. Per definitie moeten de kwadraten van de waarschijnlijkheidsamplitudes de kansen geven voor het detecteren van de bijbehorende toestand, en dit kunnen we wel controleren (conform het principe van een halfdoorlatende spiegel):
  $$\left({\pm 1/ \sqrt{2}}\right)^2 = \frac{1}{2}$$
• Tijdens de recente uitreiking van de Gouden Pipet droeg Lieven Scheire de volgende T-shirt. We begrijpen nu net genoeg van kwantummechanica om zijn nerdy grapje te smaken: “Vraag me niet hoe ik me voel, of ik zou kunnen instorten.”

• Sinds 2009 bestaan de eerste echte kwantumchips, met weliswaar een nog bescheiden functionaliteit. Sinds 2011 startte de Canadese firma D-Wave zelfs met de commerciële productie van een 128-qubit processor (de slogan op hun website: We have a problem with impossible). In mei 2013 werd de nieuwe 512-qubit kwantumcomputer geïnstalleerd in het prestigieuze Quantum Artificial Intelligence Lab, een samenwerking tussen NASA, Google en USRA.
   
• De input voor een klassieke computer kan voorgesteld worden door een rij van $n$ bits, $011\ldots 01$, wat een keuze is uit $2^n$ mogelijkheden. Maar een rij van $n$ qubits stelt een superpositie voor van al deze $2^n$ mogelijkheden! Een kwantumcomputer (met kwantumpoorten) is dus in staat om super-parallelle berekeningen uit te voeren, simultaan op alle mogelijke inputs van $n$ bits.