Approximate Span Programs

Random Walks and Electrical Networks

P. G. Doyle and J. L. Snell · 1984

Earlier work this paper cites.

On span programs

M. Karchmer and A. Wigderson · 1993

Earlier work this paper cites.

Quantum measurements and the Abelian stabilizer problem, 1995

A. Kitaev · 1995

Earlier work this paper cites.

The electrical resistance of a graph captures its commute and cover times

A. K. Chandra, P. Raghavan, W. L. Ruzzo, R. Smolensky, and P. Tiwari · 1996

Earlier work this paper cites.

A fast quantum mechanical algorithm for database search

L. K. Grover · 1996

Earlier work this paper cites.

Strengths and weaknesses of quantum computing

C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani · 1997

Earlier work this paper cites.

Quantum algorithms revisited

R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca · 1998

Earlier work this paper cites.

Quantum lower bounds by polynomials

R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf · 2001

Earlier work this paper cites.

Quantum amplitude amplification and estimation

G. Brassard, P. Høyer, M. Mosca, and A. Tapp · 2002

Cited alongside, same era.

Quantum speed-up of Markov chain based algorithms

M. Szegedy · 2004

Cited alongside, same era.

Quantum algorithm for linear systems of equations

A. W. Harrow, A. Hassidim, and S. Lloyd · 2009

Cited alongside, same era.

Markov Chains and Mixing Times

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

Cited alongside, same era.

Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function

B. Reichardt · 2009

Cited alongside, same era.

Quantum query complexity of state conversion

T. Lee, R. Mittal, B. Reichardt, R. Špalek, and M. Szegedy · 2011

Cited alongside, same era.

Span programs for functions with constant-sized 1-certificates

A. Belovs · 2012

Later among the works it cites.

Span programs and quantum algorithms for

A. Belovs and B. Reichardt · 2012

Later among the works it cites.

Span-program-based quantum algorithm for evaluating formulas

B. Reichardt and R. Špalek · 2012

Later among the works it cites.

Time efficient quantum walks for 3-distinctness

A. Belovs, A. M. Childs, S. Jeffery, R. Kothari, and F. Magniez · 2013

Later among the works it cites.

Quantum algorithms for approximating the effective resistances in electrical networks, 2013

Original

G. Wang · 2013

Later among the works it cites.

Frameworks for Quantum Algorithms

S. Jeffery · 2014

Later among the works it cites.