Finding structural anomalies in graphs by means of quantum walks

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F10%3A00045669" target="_blank" >RIV/00216224:14330/10:00045669 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Finding structural anomalies in graphs by means of quantum walks

Popis výsledku v původním jazyce

We explore the possibility of using quantum walks on graphs to find structural anomalies, such as extra edges or loops, on a graph. We focus our attention on star graphs, whose edges are like spokes coming out of a central hub. If there are N spokes, weshow that a quantum walk can find an extra edge connecting two of the spokes or a spoke with a loop on it in O(sqrt(N)) steps. We initially find that if all of the spokes have loops except one, the walk will not find the spoke without a loop, but this can be fixed if we choose the phase with which the particle is reflected from the vertex without the loop. Consequently, quantum walks can, under some circumstances, be used to find structural anomalies in graphs.

Název v anglickém jazyce

Finding structural anomalies in graphs by means of quantum walks

Popis výsledku anglicky

We explore the possibility of using quantum walks on graphs to find structural anomalies, such as extra edges or loops, on a graph. We focus our attention on star graphs, whose edges are like spokes coming out of a central hub. If there are N spokes, weshow that a quantum walk can find an extra edge connecting two of the spokes or a spoke with a loop on it in O(sqrt(N)) steps. We initially find that if all of the spokes have loops except one, the walk will not find the spoke without a loop, but this can be fixed if we choose the phase with which the particle is reflected from the vertex without the loop. Consequently, quantum walks can, under some circumstances, be used to find structural anomalies in graphs.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2010

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Physical Review A

ISSN

1050-2947

e-ISSN

—

Svazek periodika

82

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

4

Strana od-do

—

Kód UT WoS článku

000282568300001

EID výsledku v databázi Scopus

—