In deze thesis worden quantum walks op grafen bestudeerd, de quantummechanische tegenhanger van klassieke walks of Markov ketens op grafen. Deze quantum walks vormen een fundamenteel bouwblok van de quantummechanica en de opkomende quantumcomputer, net zoals klassieke walks dit zijn voor klassieke fysica en computers. Specifiek wordt de wederkerige relatie tussen quantum walks en klassieke walks beschreven en versterkt: onderzocht wordt of klassieke walks toelaten om quantum walks te simuleren, en omgekeerd, in welke mate quantum walks toelaten om klassieke walks na te bootsen. Zo raakt dit werk aan twee zijden van eenzelfde medaille, één deels onbegrepen, en één deels onverkend.
In het eerste deel van de thesis wordt bewezen hoe klassieke walks toelaten om het versneld menggedrag van quantum walks te simuleren. Hiertoe wordt er gebouwd op resultaten uit de studie van verborgen variabelen binnen de quantummechanica. Dit nuanceert de winst van quantumalgoritmes die bouwen op dit versneld gedrag, en toont aan dat de snelheidsgrenzen op klassieke walks ook gelden voor quantum walks. Het tweede deel van de thesis beschrijft een nieuw quantum walk algoritme om een ruime klasse van klassieke walks sneller te simuleren. Dit leidt naar versnelde quantumalgoritmes voor een reeks graaf-, zoek- en classificatieproblemen. | |