Finding structural anomalies in graphs by means of quantum walks
The result's identifiers
Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Finding structural anomalies in graphs by means of quantum walks
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2010
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Physical Review A
ISSN
1050-2947
e-ISSN
—
Volume of the periodical
82
Issue of the periodical within the volume
4
Country of publishing house
US - UNITED STATES
Number of pages
4
Pages from-to
—
UT code for WoS article
000282568300001
EID of the result in the Scopus database
—