Hvordan en ny kvantetilgang kan udvikle hurtigere algoritmer til at udlede komplekse netværk

Vores verden mangler ikke komplekse netværk – fra cellulære netværk inden for biologi til indviklede webnetværk inden for teknologi. Disse netværk danner også grundlag for forskellige anvendelser inden for stort set alle videnskabsområder, og at analysere og manipulere disse netværk, specifikke "søge"-algoritmer er påkrævet. Men, konventionelle søgealgoritmer er langsomme og, når man har at gøre med store netværk, kræver lang regnetid. For nylig, Søgealgoritmer baseret på kvantemekanikkens principper har vist sig at overgå klassiske tilgange.

Et sådant eksempel er "quantum walk"-algoritmen, som kan bruges til at finde et bestemt punkt eller et "vertex" på en given N-site graf. I stedet for blot at gå gennem tilstødende hjørner, kvantevandringstilgangen anvender sandsynlighedsvurderinger baseret på den kvantemekaniske teori, hvilket drastisk reducerer antallet af trin, der kræves for at finde målet. For at opnå dette, før du flytter fra et punkt til et andet, en operation kaldet "oracle call" skal udføres gentagne gange for at justere sandsynlighedsværdierne i kvantesystemrepræsentationen. Et hovedspørgsmål er at forstå forholdet mellem den optimale beregningstid for orakelopkaldet og netværkets struktur, da dette forhold er velkendt for standardformer og -kroppe, men det er stadig uklart for komplekse netværk.

I en ny undersøgelse offentliggjort i Fysisk gennemgang A , et team af videnskabsmænd ved Tokyo University of Science, ledet af prof Tetsuro Nikuni, gravet dybere ned i disse netværks forviklinger i et forsøg på at udvikle mere effektive kvantealgoritmer. Prof Nikuni forklarer, "Mange systemer i den virkelige verden, såsom World Wide Web og sociale/biologiske netværk, udviser komplekse strukturer. For fuldt ud at udforske potentialet i disse netværkssystemer, at udvikle en effektiv søgealgoritme er afgørende."

Til at starte med, forskerne undersøgte netværks "fraktale egenskaber" (geometriske egenskaber af figurer, der ser ud til at gentage deres overordnede form uendeligt). Forskerne fokuserede på nogle grundlæggende fraktale gittere (strukturer med et fraktalt netværk), såsom "Sierpinski pakning, " "Sierpinski tetraeder, " og "Sierpinski tæppe, " at forsøge at finde ud af forholdet mellem antallet af knudepunkter (netværkets knudepunkter) og den optimale beregningstid i en kvantevandringssøgning. Til dette formål, de udførte numeriske simuleringer med over en million hjørner og kontrollerede, om resultaterne var i overensstemmelse med tidligere undersøgelser, som foreslog en matematisk lov eller en "skaleringslov" for at forklare dette forhold.

Forskerne fandt ud af, at skaleringsloven for nogle fraktale gittere varierede alt efter deres spektrale dimension, bekræfter den tidligere formodning for andre gitter. Overraskende nok, de fandt endda ud af, at skaleringsloven for en anden type fraktalgitter afhænger af en kombination af dets iboende egenskaber, igen viser, at den tidligere formodning om det optimale antal orakelopkald kan være nøjagtig. Prof Nikuni siger, "Det kan faktisk være en kendsgerning, at den rumlige kvantesøgning på fraktale gitter overraskende er underlagt kombinationer af fraktalgeometriens karakteristiske størrelser. Det er fortsat et åbent spørgsmål, hvorfor skaleringsloven for antallet af orakelkald er givet ved f.eks. kombinationer." Med denne forståelse, holdet foreslog endda en ny skaleringshypotese, som afviger lidt fra de tidligere foreslåede, for at få mere indsigt i forskellige fraktale geometrier af netværk.

Forskerholdet håber, at med deres resultater, kvantesøgninger bliver nemmere at analysere eksperimentelt - især med nyere eksperimenter, der udfører kvantevandringer på fysiske systemer som optiske gitter. Den brede anvendelighed af kvantealgoritmer på fraktale gitre fremhæver vigtigheden af ​​denne undersøgelse. På grund af dets spændende resultater, denne undersøgelse blev endda valgt som "Redaktørens forslag" i februar 2020-udgaven af Fysisk gennemgang A . Optimistisk med hensyn til resultaterne og med fremtidige forskningsretninger fastlagt, Prof Nikuni konkluderer, "Vi håber, at vores undersøgelse yderligere fremmer den tværfaglige undersøgelse af komplekse netværk, matematik, og kvantemekanik på fraktale geometrier."