Faster quantum algorithm for evaluating game trees

We give an O (√ n log n )-query quantum algorithm for evaluating size- n AND-OR formulas. Its running time is poly-logarithmically greater after efficient preprocessing. Unlike previous approaches, the algorithm is based on a quantum walk on a graph that is not a tree. Instead, the algorithm is based on a hybrid of direct-sum span program composition, which generates tree-like graphs, and a novel tensor-product span program composition method, which generates graphs with vertices corresponding to minimal zero-certificates.

Authors

• Ben Reichardt

Keywords

No keywords are indexed for this paper.