  Quantum walks on binary trees are used in many quantum algorithms to achieve
important speedup over classical algorithms. The formulation of this kind of
algorithms as quantum circuit presents the advantage of being easily readable,
executable on circuit based quantum computers and simulators and optimal on the
usage of resources. We propose a strategy to compose quantum circuit that
performs quantum walk on binary trees following universal gate model quantum
computation principles. We give a particular attention to NAND formula
evaluation algorithm as it could have many applications in game theory and
reinforcement learning. We therefore propose an application of this algorithm
and show how it can be used to train a quantum reinforcement learning agent in
a two player game environment.
