Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games

M. Davis and H. Putnam. A computing procedure for quantification theory. Journal of the ACM

1960

Earlier work this paper cites.

M. Davis, G. Logemann, and D. Loveland. A machine program for theorem proving. Communications of the ACM

1962

Earlier work this paper cites.

Uniform random spanning trees

R. Pemantle · 1995

Earlier work this paper cites.

L. K. Grover. A fast quantum mechanical algorithm for database search. Proceedings of the ACM Symposium on the Theory of Computing (STOC’1996)

1996

Earlier work this paper cites.

Random walks on graphs: A survey

L. Lovász · 1996

Earlier work this paper cites.

Lectures on contemporary probability

G. F. Lawler, L. N. Coyle · 1999

Cited alongside, same era.

M. Szegedy. Quantum speed-up of Markov chain based algorithms. Proceedings of FOCS’2004

2004

Cited alongside, same era.

E. Farhi, J. Goldstone, S. Gutman, A quantum algorithm for the Hamiltonian NAND tree. Theory of Computing

2008

Cited alongside, same era.

Matrix mathematics. Theory, facts, and formulas

D. S. Bernstein · 2009

Cited alongside, same era.

Markov chains and mixing times. With a chapter by James G. Propp and David B. Wilson

D. A. Levin, Y. Peres, E. L. Wilmer · 2009

Cited alongside, same era.

Quantum walk speedup of backtracking algorithms

Original

A. Montanaro

Cited in the paper.

A. Ambainis, A. Childs, B. Reichardt, R. Špalek, S. Zhang. Any AND-OR formula of size N N can be evaluated in time N 1 / 2 + o ⁡ ( 1 ) N^{1/2+o(1)} on a quantum computer. SIAM Journal on Computing

2010

Later among the works it cites.

B. Reichardt. Faster quantum algorithm for evaluating game trees. Proceedings of SODA’2011

Original

2011

Later among the works it cites.

Matrix analysis

R. A. Horn, C. R. Johnson · 2012

Later among the works it cites.

Probability on trees and networks

R. Lyons, Y. Peres · 2016

Later among the works it cites.