Improvement of quantum walks search algorithm in single-marked vertex graph

DOI10.1088/1751-8121/ACF174MaRDI QIDQ6096899zbMATH OpenOpenAlexFDO

Authors Xinying Li, Yun Shang

Publication date 15 September 2023

Published in Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Markov chainsquantum walkssearch algorithms

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Searching and sorting (68P10) Quantum computation (81P68) Random walks on graphs (05C81) Quantum measurement theory, state operations, state preparations (81P15) Adiabatic invariants for problems in Hamiltonian and Lagrangian mechanics (70H11) Interpolation, preservation, definability (03C40)

Abstract: Quantum walks are powerful tools for building quantum search algorithms or quantum sampling algorithms named the construction of quantum stationary state. However, the success probability of those algorithms are all far away from 1. Amplitude amplification is usually used to amplify success probability, but the souffl'e problems follow. Only stop at the right step can we achieve a maximum success probability. Otherwise, as the number of steps increases, the success probability may decrease, which will cause troubles in practical application of the algorithm when the optimal number of steps is not known. In this work, we define generalized interpolated quantum walks, which can both improve the success probability of search algorithms and avoid the souffl'e problems. Then we combine generalized interpolation quantum walks with quantum fast-forwarding. The combination both reduce the times of calling walk operator of searching algorithm from $Theta((varepsilo{n}^{-1})sqrtHeg)$ to $Theta(log(varepsilo{n}^{-1})sqrtHeg)$ and reduces the number of ancilla qubits required from $Theta(log(varepsilo{n}^{-1})+logsqrtHeg)$ to $Theta(loglog(varepsilo{n}^{-1})+logsqrtHeg)$, and the souffle problem is avoided while the success probability is improved, where $varepsilon$ denotes the precision and $Heg$ denotes the classical hitting time. Besides, we show that our generalized interpolated quantum walks can be used to improve the construction of quantum states corresponding to stationary distributions as well. Finally, we give an application that can be used to construct a slowly evolving Markov chain sequence by applying generalized interpolated quantum walks, which is the necessary premise in adiabatic stationary state preparation.

Recommendations

• Adjacent vertices can be hard to find by quantum walks
• Faster search by lackadaisical quantum walk
• Quantum walks can find a marked element on any graph
• Search via Quantum Walk
• Doubling the success of quantum walk search using internal-state measurements

Cites work

• Adiabatic quantum state generation and statistical zero knowledge
• Faster quantum-walk algorithm for the two-dimensional spatial search
• Low-Mean Hitting Time for Random Walks on Heterogeneous Networks
• On the hitting times of quantum versus random walks
• Quadratic speedup for finding marked vertices by Quantum walks
• Quantum Algorithms for the Triangle Problem
• Quantum Walk Algorithm for Element Distinctness
• Quantum algorithm design: techniques and applications
• Quantum algorithms revisited
• Quantum mixing of Markov chains for special distributions
• Quantum verification of matrix products
• Quantum walks can find a marked element on any graph
• Search via Quantum Walk
• Some Inequalities for Reversible Markov Chains

This page was built for publication: Improvement of quantum walks search algorithm in single-marked vertex graph

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