Efficient circuit implementation for coined quantum walks on binary
trees and application to reinforcement learning
Thomas Mullor
IRT Saint Exupery
Toulouse
thomas.mullor@irt-saintexupery.com
David Vigouroux
IRT Saint Exupery
Toulouse
david.vigouroux@irt-saintexupery.com
Louis Bethune
Universit´
e Paul Sabatier, IRIT
Toulouse
louis.bethune@univ-toulouse.fr
Abstract— 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 computa-
tion 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.
I. INTRODUCTION
Quantum computing is a computation paradigm using
properties of quantum mechanics to perform information
processing. Many famous quantum algorithms have been
shown to outperform their equivalent classical algorithm[1],
[2]. Quantum walk is a way to compose many promising
quantum algorithms. It can be viewed as the quantum
analogues of classical random walks [3]. In several studies,
it has been shown that it could provide some algorithmic
speedup on many problems [4], [5], [6] and possible
applications to tree search problems [7], [8].
To consider a quantum algorithm as implementable
on universal quantum computers, we describe them as a
quantum circuit using native quantum gates. For particular
cases of quantum walks, circuit implementation has been
proposed allowing us to execute them easily with an optimal
usage of resources [9]. To the best of our knowledge,
no circuit based implementation has been presented for
quantum walks on binary trees even if existing algorithms
uses such processes. In this work, we propose a strategy
to perform implementation of such a quantum walk using
quantum gate model where the number of gates used for
a walk step scales linearly with the depth of the tree.
We will give a particular interest to quantum walk based
algorithm performing boolean NAND tree evaluation[8] as
it has potential applications to game tree resolution and
reinforcement learning.
Reinforcement learning is an area of machine learning
where an agent learn to take the best actions in a given
environment to maximize a reward. Many classical
reinforcement learning algorithms showed impressive results
in two player games like chess or go [10], [11]. Most of the
algorithms who try to master a game relies on tree search
algorithms like Monte Carlo Tree Search (MCTS) to explore
game tree and choose best move [10], [11]. This technique
is very powerful but sometimes has flaws as it performs a
partial exploration of the game tree. In this article, we are
interested in the performances of quantum computing for
exploring game tree. Improving tree search algorithm could
improve training and results of a reinforcement learning
agent.
As NAND formula algorithm allow us to evaluate quality
of a position in a two-player game tree, we illustrate its
potential application by using it as a training tool for a
quantum agent in a simple two-player game. With the
speed-up proposed by this algorithm, we are able to perform
evaluation of deeper trees in equivalent time (twice deeper
exploration for a binary tree). By using quantum algorithm
to perform such explorations, we expect agents to achieve
better performances in their learning process.
II. RELATED WORKS
Many quantum algorithms based on quantum walks have
been presented with various application fields. For some
kinds of walks on very specifics graphs (cycles, hypercubes,
welded trees, highly symmetric graphs...), efficient quantum
circuit designs have been presented[9] and allows us to
easily implement quantum walks algorithms using circuit-
based quantum computers.
One of the main quantum algorithm based on quantum
walks on binary trees allows us to evaluate a boolean formula
of Nvariables taking the form of a NAND tree using only
N1/2+o(1) calls to a black box oracle[8]. By extension, this
allows us to evaluate any AND/OR tree (i.e. a tree where
vertices correspond alternately to AND and OR evaluations),
which is the boolean version of a MIN/MAX tree. As
MIN/MAX trees represents optimal decision makings in
a two-player game, its computation constitutes an useful
knowledge to learn to play a game. The work presented in
this paper is motivated by the potential applications of this
algorithm in game theory and reinforcement learning.
arXiv:2210.06784v2 [cs.ET] 14 Oct 2022