Quantum speed-up of Markov chain based algorithms

By Mario Szegedy. 45th Annual IEEE Symposium on Foundations of Computer Science, 2004

337 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Quantum algorithms: an overview (2015, positive): “There are analogous algorithms based on quantum walks which improve the dependence on (cid:14) quadratically, from 1 =(cid:14) to 1 = p (cid:14) [6, 92, 66].”
Variational Quantum Linear Solver (2019, methodology): “[69] M.”
Quantum Walk Based Search Algorithms (2008, methodology): “Inspired by the work of Ambainis, Szegedy [35] designed a general method to quantize classical Markov chains, and developed a theory of quantum walk based search algorithms.”
Generalized Quantum Signal Processing (2023, background): “…insight: the majority of prominent quantum algorithms, such as Hamiltonian simulation [1–4], quantum search [5–7], factoring [8], and quantum walks [7, 9], can be fundamentally reduced to the central task of implementing a matrix function of a Hamiltonian, f ( H ), this was shown in [10, 11].”
Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity (2018, methodology): “While aspects of this approach were introduced recently in [26, 27], the techniques involved emerged from a history of advances in Hamiltonian simulation prominently involving Szegedy quantum walks [53], the “linear combination of unitaries” (LCU) query model [54], and the method of Hamiltonian simu”