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

DOI10.1088/1751-8121/ACF174arXiv2209.04162OpenAlexW4385911360MaRDI QIDQ6096899FDOQ6096899

Authors: Xinying Li, Yun Shang 

Publication date: 15 September 2023

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

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.

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

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

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)

Cites Work

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

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)