NAND-Trees, Average Choice Complexity, and Effective Resistance

Random Walks and Electrical Networks

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

Earlier work this paper cites.

Probabilistic boolean decision trees and the complexity of evaluating game trees

M. Saks and A. Wigderson · 1986

Earlier work this paper cites.

On span programs

M. Karchmer and A. Wigderson · 1993

Earlier work this paper cites.

A quantum algorithm for the Hamiltonian NAND tree, 2007

E. Farhi, J. Goldstone, and S. Gutmann · 2007

Earlier work this paper cites.

Discrete-query quantum algorithm for NAND trees

A. M. Childs, R. Cleve, S. P. Jordan, and D. Yonge-Mallo · 2009

Earlier work this paper cites.

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

B. W. Reichardt · 2009

Cited alongside, same era.

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

A. Ambainis, A. M. Childs, B. W. Reichardt, R. Špalek, and S. Zhang · 2010

Cited alongside, same era.

Quantum adversary (upper) bound

S. Kimmel · 2011

Cited alongside, same era.

Reflections for quantum query algorithms

B. W. Reichardt · 2011

Cited alongside, same era.

Span-program-based quantum algorithm for evaluating unbalanced formulas

B. W. Reichardt · 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 s ​ t st -connectivity and claw detection

A. Belovs and B. W. Reichardt · 2012

Later among the works it cites.

Span-program-based quantum algorithm for evaluating formulas

B. W. Reichardt and R. Špalek · 2012

Later among the works it cites.

Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure

B. Zhan, S. Kimmel, and A. Hassidim · 2012

Later among the works it cites.

Approximate span programs, 2015

Original

T. Ito and S. Jeffery · 2015

Closest in time.