Faster quantum algorithm for evaluating game trees

Understand

We give an O(sqrt 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.