On the probability of finding marked connected components using quantum walks

DOI10.1134/S1995080218070144MaRDI QIDQ1992115zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 2 November 2018

Published in Lobachevskii Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.04046

zbMATH Keywords

exceptional configurationsquantum computingquantum walksstationary states

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Abstract: Finding a marked vertex in a graph can be a complicated task when using quantum walks. Recent results show that for two or more adjacent marked vertices search by quantum walk with Grover's coin may have no speed-up over classical exhaustive search. In this paper, we analyze the probability of finding a marked vertex for a set of connected components of marked vertices. We prove two upper bounds on the probability of finding a marked vertex and sketch further research directions.

Recommendations

• Upperbounds on the probability of finding marked connected components using quantum walks
• Quantum walks can find a marked element on any graph
• Adjacent vertices can be hard to find by quantum walks
• Adjacent vertices can be hard to find by quantum walks
• Finding Is as Easy as Detecting for Quantum Walks

Cites work

• Adjacent vertices can be hard to find by quantum walks
• Doubling the success of quantum walk search using internal-state measurements
• Efficient quantum walk on the grid with multiple marked elements
• Exceptional quantum walk search on the cycle
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• On the hitting times of quantum versus random walks
• Quantum walks can find a marked element on any graph
• Quantum Walks with Multiple or Moving Marked Locations

Cited in

(5)

• Adjacent vertices can be hard to find by quantum walks
• Impact of the malicious input data modification on the efficiency of quantum spatial search
• Upperbounds on the probability of finding marked connected components using quantum walks
• Adjacent vertices can be hard to find by quantum walks
• Finding more than one path through a simple maze with a quantum walk

This page was built for publication: On the probability of finding marked connected components using quantum walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1992115)