Last year, I gave a talk at TQC on “Quantum Algorithms for Evaluating Min-Max Trees”[1], co-authored by Dr. Richard Cleve, Dr. Dmitry Gavinsky, and myself.
In the talk, I presented an algorithm which combines the Nand tree evaluation quantum algorithm of Farhi, Goldstone, and Gutmann[2] with Grover’s search in a clever way (if I do say so myself) to evaluate Min-Max trees, with the same asymptotic cost in queries as for Nand trees.
I’ve uploaded the slides to SlideShare, and also embedded them in this post below… » [Expand post] [Permalink]