Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2108.09818 · Quantum Information Processing

The average search probabilities of discrete-time quantum walks

Hanmeng Zhan

Published Sep 29, 2022• 1 citation
arXivHTMLPDF
DOI
10.1007/s11128-022-03681-9

Related papers

Discrete-time quantum walk search on Johnson graphs

Xiling Xue, Yue Ruan, Zhihao Liu

Quantum Information Processing•Jan 2, 2019•15 citations

Time averaged distribution of a discrete-time quantum walk on the path

Yusuke Ide, Norio Konno, Etsuo Segawa

arXiv:1112.4036•Quantum Information Processing•May 28, 2012•17 citations

Discrete Randomness in Discrete Time Quantum Walk: Study Via Stochastic Averaging

Demosthenes Ellinas, Anthony J. Bracken, I. Smyrnakis

arXiv:1207.5257•Reports on Mathematical Physics•Oct 1, 2012•1 citation

Spatial search using the discrete time quantum walk

Neil B. Lovett, Matthew Everitt, Matt Trevers +3 more

Natural Computing•Sep 30, 2011•23 citations

Doubling the success of quantum walk search using internal-state measurements

Krišjānis Prūsis, Jevgēnijs Vihrovs, Thomas G Wong

Abstract In typical discrete-time quantum walk algorithms, one measures the position of the walker while ignoring its internal spin/coin state. Rather than neglecting the information in this internal state, we show that additionally measuring it doubles the success probability of many quantum spatial search algorithms. For example, this allows Grover's unstructured search problem to be solved with certainty, rather than with probability 1/2 if only the walker's position is measured, so the additional measurement yields a search algorithm that is twice as fast as without it, on average. Thus the internal state of discrete-time quantum walks holds valuable information that can be utilized to improve algorithms. Furthermore, we determine conditions for which spatial search problems on regular graphs are amenable to this doubling of the success probability, and this involves diagrammatically analyzing search using degenerate perturbation theory and deriving a useful formula for how the quantum walk acts in its reduced subspace.

arXiv:1511.03865•Journal of Physics A Mathematical and Theoretical•Oct 19, 2016•10 citations

Deterministic discrete-time quantum walk search on complete bipartite graphs

Fangjie Peng, Meng Li, Xiaoming Sun

Searching via quantum walk is a topic that has been extensively studied. Most previous results provide approximate solutions, while in this paper we prove an algorithm that can find a marked vertex certainly. We adopt the coined discrete-time quantum walk (DTQW) model with adjusted operators and prove that, on complete bipartite graphs, when parameters are set properly, coined DTQW can deterministically find a marked vertex, i.e., the success probability is exactly 1. Before this paper there have been results of an alternating continuous-time quantum walk method that achieve deterministic spatial search, but this paper provides a deterministic quantum spatial search result via DTQW, while maintaining a quadratic speedup compared to classical algorithms. We also provide the quantum circuit implementation. Published by the American Physical Society 2024

Physical Review Research•Jul 9, 2024•5 citations
Abstract In typical discrete-time quantum walk algorithms, one measures the position of the walker while ignoring its internal spin/coin state. Rather than neglecting the information in this internal state, we show that additionally measuring it doubles the success probability of many quantum spatial search algorithms. For example, this allows Grover's unstructured search problem to be solved with certainty, rather than with probability 1/2 if only the walker's position is measured, so the additional measurement yields a search algorithm that is twice as fast as without it, on average. Thus the internal state of discrete-time quantum walks holds valuable information that can be utilized to improve algorithms. Furthermore, we determine conditions for which spatial search problems on regular graphs are amenable to this doubling of the success probability, and this involves diagrammatically analyzing search using degenerate perturbation theory and deriving a useful formula for how the quantum walk acts in its reduced subspace.
Searching via quantum walk is a topic that has been extensively studied. Most previous results provide approximate solutions, while in this paper we prove an algorithm that can find a marked vertex certainly. We adopt the coined discrete-time quantum walk (DTQW) model with adjusted operators and prove that, on complete bipartite graphs, when parameters are set properly, coined DTQW can deterministically find a marked vertex, i.e., the success probability is exactly 1. Before this paper there have been results of an alternating continuous-time quantum walk method that achieve deterministic spatial search, but this paper provides a deterministic quantum spatial search result via DTQW, while maintaining a quadratic speedup compared to classical algorithms. We also provide the quantum circuit implementation. Published by the American Physical Society 2024