Upperbounds on the probability of finding marked connected components using quantum walks

Adam Glos; Nikolajs Nahimovs; Konstantin Balakirev; Kamil Khadiev

doi:10.1007/s11128-020-02939-4

Upperbounds on the probability of finding marked connected components using quantum walks

Adam Glos
, Nikolajs Nahimovs^*
, Konstantin Balakirev
, Kamil Khadiev

^*Corresponding author for this work

Department of Computer Science

Institute of Theoretical and Applied Informatics of the Polish Academy of Sciences
Silesian University of Technology
Higher School of Economics
Kazan Volga Region Federal University
Smart Quantum Technologies Ltd.

Research output: Contribution to journal › Article › peer-review

9 Citations (Scopus)

Abstract

Quantum walk search may exhibit phenomena beyond the intuition from a conventional random walk theory. One of such examples is exceptional configuration phenomenon—it appears that it may be much harder to find any of two or more marked vertices, that if only one of them is marked. In this paper, we analyze the probability of finding any of marked vertices in such scenarios and prove upperbounds for various sets of marked vertices. We apply the upperbounds to large collection of graphs and show that the quantum search may be slow even when taking real-world networks.

Original language	English
Article number	6
Journal	Quantum Information Processing
Volume	20
Issue number	1
DOIs	https://doi.org/10.1007/s11128-020-02939-4
Publication status	Published - Jan 2021

OECD Field of Science

1.2 Computer and Information Sciences

Keywords

Exceptional configurations
General graph
Lower bound
Quantum walks
Stationary state
Upper bound

Access to Document

10.1007/s11128-020-02939-4

Cite this

@article{6b7e4ad6f75d46a18969042c899774ec,

title = "Upperbounds on the probability of finding marked connected components using quantum walks",

abstract = "Quantum walk search may exhibit phenomena beyond the intuition from a conventional random walk theory. One of such examples is exceptional configuration phenomenon—it appears that it may be much harder to find any of two or more marked vertices, that if only one of them is marked. In this paper, we analyze the probability of finding any of marked vertices in such scenarios and prove upperbounds for various sets of marked vertices. We apply the upperbounds to large collection of graphs and show that the quantum search may be slow even when taking real-world networks.",

keywords = "Exceptional configurations, General graph, Lower bound, Quantum walks, Stationary state, Upper bound",

author = "Adam Glos and Nikolajs Nahimovs and Konstantin Balakirev and Kamil Khadiev",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2021",

month = jan,

doi = "10.1007/s11128-020-02939-4",

language = "English",

volume = "20",

journal = "Quantum Information Processing",

issn = "1570-0755",

publisher = "Springer",

number = "1",

}

TY - JOUR

T1 - Upperbounds on the probability of finding marked connected components using quantum walks

AU - Glos, Adam

AU - Nahimovs, Nikolajs

AU - Balakirev, Konstantin

AU - Khadiev, Kamil

PY - 2021/1

Y1 - 2021/1

N2 - Quantum walk search may exhibit phenomena beyond the intuition from a conventional random walk theory. One of such examples is exceptional configuration phenomenon—it appears that it may be much harder to find any of two or more marked vertices, that if only one of them is marked. In this paper, we analyze the probability of finding any of marked vertices in such scenarios and prove upperbounds for various sets of marked vertices. We apply the upperbounds to large collection of graphs and show that the quantum search may be slow even when taking real-world networks.

AB - Quantum walk search may exhibit phenomena beyond the intuition from a conventional random walk theory. One of such examples is exceptional configuration phenomenon—it appears that it may be much harder to find any of two or more marked vertices, that if only one of them is marked. In this paper, we analyze the probability of finding any of marked vertices in such scenarios and prove upperbounds for various sets of marked vertices. We apply the upperbounds to large collection of graphs and show that the quantum search may be slow even when taking real-world networks.

KW - Exceptional configurations

KW - General graph

KW - Lower bound

KW - Quantum walks

KW - Stationary state

KW - Upper bound

UR - https://link.springer.com/article/10.1007/s11128-020-02939-4?utm_source=getftr&utm_medium=getftr&utm_campaign=getftr_pilot

UR - https://www.scopus.com/pages/publications/85098787024

U2 - 10.1007/s11128-020-02939-4

DO - 10.1007/s11128-020-02939-4

M3 - Article

SN - 1570-0755

VL - 20

JO - Quantum Information Processing

JF - Quantum Information Processing

IS - 1

M1 - 6

ER -

Upperbounds on the probability of finding marked connected components using quantum walks

Abstract

OECD Field of Science

Keywords

Access to Document

Other files and links

Fingerprint

Cite this