An HHL-Based Algorithm for Computing Hitting Probabilities of Quantum Random Walks
arXiv:2009.03618 · doi:10.26421/QIC21.5-6-4
Abstract
We present a novel application of the HHL (Harrow-Hassidim-Lloyd) algorithm -- a quantum algorithm solving systems of linear equations -- in solving an open problem about quantum random walks, namely computing hitting (or absorption) probabilities of a general (not only Hadamard) one-dimensional quantum random walks with two absorbing boundaries. This is achieved by a simple observation that the problem of computing hitting probabilities of quantum random walks can be reduced to inverting a matrix. Then a quantum algorithm with the HHL algorithm as a subroutine is developed for solving the problem, which is faster than the known classical algorithms by numerical experiments.
References in corpus (23)
- Quantum algorithm for solving linear systems of equations
- Quantum fingerprinting
- Exponential algorithmic speedup by quantum walk
- Quantum algorithms for supervised and unsupervised machine learning
- Quantum Data Fitting
- Realization of a quantum walk with one and two trapped ions
- A 2D Quantum Walk Simulation of Two-Particle Dynamics
- Implementing the quantum random walk
- Preconditioned quantum linear system algorithm
- Quantum random walks in optical lattices
- Quantum quincunx in cavity quantum electrodynamics
- Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
- Quantum-inspired algorithms in practice
- Implementing Quantum Walks Using Orbital Angular Momentum of Classical Light
- A quantum algorithm to solve nonlinear differential equations
- Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
- Analysis of Absorbing Times of Quantum Walks
- Asymptotics of quantum channels: conserved quantities, an adiabatic limit, and matrix product states
- Conditional Probability Distributions of Finite Absorbing Quantum Walks
- Minimal noise subsystems
- Absorption Probabilities for the Two-Barrier Quantum Walk
- The Structure of Decoherence-free Subsystems
- Efficient Quantum Algorithms for Analyzing Large Sparse Electrical Networks