Spatial search by continuous-time quantum walks on complex networks

Abstract

Spatial search by continuous-time quantum walks on complex networks is focused on using a quantum walk in continuous time in order to find a single or multiple marked vertices within the complex network. The specific formalism used here is to consider a coupling constant that shifts the state of the quantum walker from the initial state to the target state, which is the marked vertex. The thesis begins with establishing the mathematical framework of network theory, quantum walks and numerical methods that will be used in the remainder of the thesis. Then spatial search by continuous-time quantum walk is studied on regular and semi-regular graphs, where most analytical results can be found. This will get us acquainted with spatial search by quantum walk. The complex networks studied are Barabasi-Albert graphs and the Internet network on the level of autonomous systems. Different renormalized and pruned versions of the Internet network are studied. The parameters of the quantum walk that are focused on are the optimal values for the coupling constant, success probability, time and search time.

Kvanttikulkujen spatiaalinen etsintä jatkuvassa ajassa kompleksisissa verkoissa keskittyy yhden tai useamman merkityn solmukohdan löytämiseen kompleksisesta verkosta käyttämällä kvanttikulkua jatkuvassa ajassa. Tässä työssä käytetty formalismi käsittelee kytkentävakiota, mikä siirtää kvanttikulkijan tilan alkutilasta tavoitetilaan, eli merkittyyn solmukohtaan. Tämä Pro Gradu alkaa matemaattisen viitekehyksen käsittelemisellä, jota tarvitaan lopputyössä. Tämä viitekehys sisältää verkkoteorian, kvanttikulut ja käytetyt numeeriset menetelmät. Tämän jälkeen kvanttikulun spatiaalista etsintää jatkuvassa ajassa tutkitaan säännöllisissä ja miltei säännöllisissä verkoissa, missä analyyttiset ratkaisut on löydettävissä. Tämän tarkoituksena on tutustua spatiaaliseen etsintään kvanttikululla. Barabasi-Albert -graafit ja Internet-verkko autonomisten järjestelmien tasolla ovat tässä työssä tutkittavat kompleksiset verkot. Tässä tutkitaan eri renormalisoituja ja karsittuja versioita Internet-verkosta. Kvanttikulun parametrit, joihin keskitytään, ovat optimaaliset arvot kytkentävakiolle, onnistumistodennäköisyydelle, ajalle ja etsintäajalle.