Quest 5: Virstuoso van algoritmes

Een van de belangrijkste redenen om quantumcomputers te onderzoeken is omdat quantumcomputers sommige vraagstukken veel sneller kunnen oplossen dan de computers die we nu hebben. Om quantumcomputers te onderscheiden van gewone computers, zullen we de term klassieke computer gebruiken om te verwijzen naar elk rekenapparaat dat op dit moment bestaat. Hieronder vallen je laptop en desktopcomputer, maar ook hele kleine computers zoals in je smartphone of smartwatch en hele grote en krachtige supercomputers die misschien wel een hele kamer in beslag nemen. Wat al deze computers onderscheidt van quantumcomputers is niet hoe groot, klein, langzaam of snel ze zijn, maar dat hun interne werking beschreven kan worden door klassieke fysica (elektromagnetisme om precies te zijn). Met andere woorden, hun hardware werkt op een manier die beschreven kan worden door de oude natuurkundige theorieën van voor de quantummechanica. Dit is een beetje te vergelijken met hoe de muziek van Mozart en Bach klassieke muziek wordt genoemd. Net als klassieke computers, maakt klassieke muziek ook niet optimaal gebruik van meer geavanceerde muziekinstrumenten, zoals de elektrische gitaar of synthesizers.

Als gevolg van het type hardware van klassieke computers wordt alle informatie die ze opslaan - of het nu een foto, een geluidsbestand, een video of een webpagina is - gepresenteerd door bitstrings, oftewel lange reeksen van nullen en enen. Deze informatie wordt verwerkt door een aantal regels te volgen die beschrijven hoe deze nullen en enen moeten worden aangepast om een bruikbaar antwoord te krijgen. We noemen deze reeks instructies een algoritme. Je kunt een algoritme zien als een recept – het is een reeks instructies die, als je ze zorgvuldig opvolgt, je het gewenste resultaat geeft, zoals een brownie! Een algoritme kan bijvoorbeeld twee binaire strings als invoer nemen en als uitvoer een andere binaire string produceren die bestaat uit de som van de twee oorspronkelijke strings (als je ze interpreteert als getallen). Net als recepten werden algoritmes oorspronkelijk uitgevoerd door mensen. Het woord ’computer’ verwees zelfs naar een persoon die berekeningen maakt. Maar tegenwoordig worden algoritmes uitgevoerd op echte computers. Omdat computers over het algemeen niet erg slim zijn, moeten het algoritme op een extreem precieze manier beschreven worden. Deze beschrijving, een programma, is een tastbare uitvoering van het abstracte algoritme op een manier dat de computer het kan begrijpen. Hiervoor gebruiken we een programmeertaal die de computer zelf kan omzetten in basisbewerkingen op de nullen en enen, om deze vervolgens uit te voeren in de hardware.

Als je een algoritme bedenkt, in je computer programmeert en dan uitvoert, wil je het resultaat binnen een redelijke tijdsduur krijgen. De werkelijke tijd die nodig is om je antwoord te krijgen hangt echter af van veel factoren:

1. 1.
   ​

   hoe snel je computer verschillende basisinstructies kan uitvoeren,

2. 2.
   ​

   of de invoer van je programma wordt gelezen van een harde schijf, een netwerkverbinding of rechtstreeks uit het geheugen,

3. 3.
   ​

   welke programmeertaal je gebruikt om je programma mee te maken (en de versie van de compiler of interpreter die het programma uitvoert),

enzovoort. Dit maakt het erg moeilijk om verschillende algoritmen met elkaar te vergelijken.

Om de vergelijking van verschillende algoritmen makkelijker en eerlijker te maken, kijken computerwetenschappers niet naar hoe lang het duurt om het algoritme uit te voeren op een specifieke computer die op een bepaalde manier is ingesteld. In plaats daarvan tellen ze het aantal elementaire bewerkingen dat het algoritme uitvoert. Op deze manier weten ze zeker dat ze de algoritmes zelf vergelijken en niet de computers waarop de algoritmen worden uitgevoerd (een goed algoritme dat op een hele langzame computer wordt uitgevoerd kan namelijk slechter lijken dan een slecht algoritme dat op een hele snelle computer wordt uitgevoerd). Om precies te zijn, wat computerwetenschappers willen weten is hoe het aantal bewerkingen groeit met de grootte van het probleem dat het algoritme moet oplossen. Hoe groter de hoeveelheid gegevens die je moet verwerken, hoe langer het duurt, ongeacht hoe goed het algoritme is. Wat je dus wilt weten is of je algoritme nog steeds geschikt is als de gegevens extreem groot worden. Het onderdeel van de computerwetenschap dat dit bestudeert, heet computationele complexiteit.

Bij quantumcomputing zijn we geïnteresseerd in het ontwerpen van quantumalgoritmes die problemen oplossen door quantumtoestanden te manipuleren in plaats van bitstrings. De elementaire instructies die we zullen gebruiken zijn gates, zoals de Hadamard-gate, de controlled-NOT-gate of een meting. We zullen onze quantumalgoritmes grafisch beschrijven aan de hand van een quantumcircuit, waarmee je al veel ervaring hebt opgedaan in Quirky. Maar we kunnen ook een schriftelijke weergave gebruiken, zoals je zou verwachten van een gewoon computerprogramma. Het linker circuit zou bijvoorbeeld kunnen worden weergegeven door de tekst van het rechter programma:

CNOT q1 -> q2;
H q1;

waarbij q1 en q2 verwijzen naar de twee qubits (denk eraan dat de onderste draad overeenkomt met het eerste qubit). Gegeven een rekenprobleem kunnen we dan het aantal elementaire instructies vergelijken die de best bekende quantum- en klassieke algoritmen gebruiken om het op te lossen. Op deze manier kunnen we een duidelijk beeld krijgen van het voordeel van toekomstige quantumcomputers.