Computers zijn fysieke objecten en dus onderhevig aan de wetten van de natuur. Hoewel de meeste computers tegenwoordig zijn opgebouwd uit halfgeleiders die onderhevig zijn aan quantummechanische effecten, zijn hun berekeningen volledig klassiek—op elk moment is de computer in een specifieke klassieke toestand en de stappen van de berekening zijn volledig deterministisch. Quantum computers daarentegen zijn computers die juist quantumeffecten proberen te gebruiken voor hun berekeningen. In tegenstelling tot klassieke computers kan een quantum computer op elk moment in een superpositie van verschillende klassieke toestanden tegelijk zijn, en verschillende berekeningen in parallel uitvoeren.
In 1994 vond Peter Shor een efficiënt quantum algoritme voor het factoriseren van grote getallen, een probleem waarvoor geen efficiënt klassiek algoritme bekend is. In 1996 vond Lov Grover een ander belangrijk quantum algoritme, dat een ongeordende database kwadratisch sneller kan doorzoeken dan het best mogelijke klassieke algoritme. Daarna is het vakgebied van de quantum computing sterk gegroeid. Andere belangrijke ontdekkingen zijn ook gedaan in aanverwante gebieden zoals quantum cryptografie, informatietheorie, error-correcting codes, en communicatie complexiteit.
In dit proefschrift onderzoeken we de kracht van quantum computers. We presenteren enkele nieuwe quantum algoritmes, verbeteren technieken om ondergrenzen te bewijzen, en bewijzen de eerste time-space tradeoffs voor quantum computers.
Het quantum zoekalgoritme van Grover is breed toepasbaar en kan als subroutine worden gebruikt in vele klassieke algoritmes. Wij passen het toe op de volgende graafproblemen: het vinden van een maximale matching en het vinden van een maximale stroom (flow) in een integer netwerk. In beide gevallen is ons quantum algoritme polynomiaal sneller dan het beste bekende klassieke algoritme.
We houden ons ook bezig met de vraag of het product van twee gegeven n*n matrices gelijk is aan een derde gegeven matrix. Dit is een makkelijker probleem dan het berekenen van het product van de twee matrices zelf, aangezien er een klassiek algoritme bestaat voor het verificatie probleem in tijd O(n^2), terwijl het beste bekende algoritme voor het vermenigvuldigen van twee matrices O(n^{2.376}) tijd gebruikt. Ons quantum algoritme voor de verificatie loopt in tijd O(n^{5/3}) en is dus polynomiaal sneller dan het beste klassieke algoritme.
Een ondergrens is een bewijs dat een bepaald probleem niet sneller kan worden opgelost dan een bepaalde waarde. Er zijn twee globale technieken om ondergrenzen te bewijzen voor quantum computers. De adversary methode is gebaseerd op de complexiteit van het onderscheiden van inputs die verschillende outputs moeten geven. Deze methode is redelijk eenvoudig te gebruiken en geeft vaak optimale ondergrenzen, bijvoorbeeld voor Grovers zoekprobleem. De polynomiale methode drukt de kans dat een quantum algoritme een bepaalde output geeft uit als een polynoom van lage graad; ondergrenzen op de graad van bepaalde approximerende polynomen impliceren dan ondergrenzen voor quantum algoritmes. Deze methode is over het algemeen moeilijker toepasbaar dan de eerste, maar geeft voor sommige problemen sterkere ondergrenzen.
Vele varianten van de adversary methode waren bekend. Wij ruimen dit woud aan varianten op, en bewijzen dat er in feite één adversary methode is, en dat alle bestaande varianten daarvan slechts verschillende equivalente formuleringen zijn. We bewijzen ook een beperking op de ondergrens die met de adversary methode bewezen kan worden voor een functie, in termen van de certificaat-complexiteit van die functie. Dit laat zien dat de meeste van de bekende quantum ondergrenzen die niet optimaal zijn, niet verder verbeterd kunnen worden met de adversary methode. We geven ook precieze formules voor de adversary ondergrens voor functies die de compositie zijn van andere functies.
We bewijzen optimale direct product stellingen voor verschillende functies. Een DPS zegt dat de complexiteit van het berekenen van k onafhankelijke instanties van een probleem k maal zo hoog is als de complexiteit van één instantie, zelfs als de succeskans van het algoritme voor de k instanties slechts exponentieel klein hoeft te zijn. Stellingen van dit type klinken meestal wel plausibel, maar zijn vaak moeilijk te bewijzen.
Naast het beantwoorden van een fundamentele vraag over complexiteit, hebben DPS ook toepassingen voor time-space tradeoffs. Een time-space tradeoff geeft de relatie die er bestaat tussen de tijd en de geheugenruimte die nodig zijn om een probleem op te lossen. We gebruiken de polynomiale methode om om een DPS te bewijzen voor de OR functie, en passen dit toe om een optimale time-space tradeoff te bewijzen voor het probleem van het sorteren van n getallen (T^2 S=Theta(n^3) voor quantum computers, versus T S=Theta(n^2) voor klassieke computers) en voor het probleem van het vermenigvuldigen van twee Booleaanse matrices. We bewijzen ook enkele communicatie-geheugenruimte tradeoffs. Dit zijn de eerste tradeoffs die ontdekt zijn voor quantum computers. Verder ontwikkelen we een nieuwe generalisering van de adversary methode in termen van de analyse van de deelruimtes van density matrices, en gebruiken dit om een nieuwe DPS te bewijzen voor alle symmetrische functies (dit zijn functies die alleen afhangen van het aantal enen in de input). Deze DPS impliceert een optimale time-space tradeoff voor het evalueren van een gegeven oplossing voor een stelsel van lineaire vergelijkingen, die polynomiaal beter is dan de klassieke tradeoff in het geval er weinig geheugenruimte is.
Het onderzoek is uitgevoerd op het Centrum voor Wiskunde en Informatica (CWI) in Amsterdam.