Efﬁcient circuit implementation for coined quantum walks on binary trees and application to reinforcement learning Thomas Mullor

2025-04-24 1 0 568.72KB 8 页 10玖币

侵权投诉

Efﬁcient 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 ﬂaws 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 ﬁelds. For some

kinds of walks on very speciﬁcs graphs (cycles, hypercubes,

welded trees, highly symmetric graphs...), efﬁcient 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

Quantum NAND formula evaluation algorithm is

presented as a quantum phase estimation performed on a

quantum walk operator using an input oracle. The operator

performs a quantum walk on a rooted binary tree, i.e. a

binary tree on which we added two-vertices tail attached

to the root of the tree. The input oracle gives values of the

leaves of the tree and is incorporated to the walk by turning

the leaves evaluating to 1 to probability sinks.

Fig. 1. The rooted binary tree for the simple boolean formula ϕ=

((x1˜

∧x2)˜

∧(x3˜

∧x4)) ˜

∧((x5˜

∧x6)˜

∧(x7˜

∧x8)) where internal vertices is

result of NAND evaluation of their children. Vertices are ﬁlled if they

evaluate to 1. A root made of two vertices (r0and r00 ) has been added to

the tree. Leaves evaluating to 1 are turned to probability sinks as presented

in [8]

Let us remind from [8] that evaluating a binary NAND

tree allows us to evaluate any AND/OR tree after an efﬁcient

classical preprocessing of the formula taking poly(N)time.

Contributions

In this paper, we propose an efﬁcient circuit based im-

plementation of quantum walks on a binary tree and we

propose, as an application, a full implementation of the main

components of NAND formula evaluation algorithm where

the number of qubits and gates grows linearly with the depth

of the tree.

In a second part, we illustrate the usage of NAND formula

evaluation, using it in a reinforcement learning case by

proposing a way to learn the input oracle.

III. QUANTUM CIRCUITS FOR COINED QUANTUM WALK

ON AN ARBITRARY BINARY TREE

We can describe a coined quantum walk on a graph

G= (V, E)as a process deﬁned by two operators acting

on their associated qubits registers :

- Coin : a ﬂip operator Facts on a coin register C.

Superposition of states of Cwill indicate which paths the

walker must take.

- Walker : a shift operator Sacts on a walker register W.

Depending on the state of C, the state of Wwill change to

go through the different vertices vof G.

The two operators deﬁne a walk step operator U=SF . For

a given superposition of vertices vtheld in a register Wand

an action atheld in a register C:

U|vti|ati=|vt+1i|at+1i.

To facilitate execution of such a process on a quantum

computer, it is preferable that the shift operator can be easily

expressed as a quantum circuit of limited size. We therefore

propose a vertex labelling that allows us to express shift

operator with elementary mathematical operations and show

how we can implement quantum algorithm based speciﬁcally

on walks on binary trees.

A. Labeling of the nodes of the tree and shift operator

As we store the label of the vertices we go through in the

Wqubits register, the way we label the vertices of our tree

will have a huge inﬂuence on the difﬁculty to implement the

shift operator. Finding a labeling of the vertices that allows

us to express easily the transition between any states as a

simple operation and thus express easily the shift operator is

a key step. We thus propose to label the vertices of the tree

by following labelling, which have such property.

We will consider here an arbitrary binary tree Twe want

to perform quantum walk on. We perform labeling of the

vertices of the tree Tconsidering the following rules:

1) root of Tis vertex 1

2) left child of a vertex vis labeled 2v

3) right child of a vertex vis labeled 2v+ 1

For the case of perfectly balanced binary trees, this cor-

responds to a breadth ﬁrst labelling and is the canonical

labelling. It allows to implement easily all the operations

used to build the shift operator with a basic set of quantum

gates.

Fig. 2. Example of labelling on a balanced binary tree

With this labeling, we can deﬁne the shift application S:

|vti|ai 7→ |vt+1i|f(vt, at)iallowing us to perform steps

through the vertices of the tree starting from any vertex v:

S|vi|lefti=|2vi|f(v, left)i

S|vi|righti=|2v+ 1i|f(v, right)i

S|vi|upi=|v/2i|f(v, up)iif vis even,

|(v−1)/2i|f(v, up)iif vis odd.

(1)

For now, we are only interested in the transformation

performed on the value held in the register Wby an

application of S. The transformation performed on the coin

C(here represented by f(vt, at)) can be any transformation

as long as Sis a valid (unitary) application and depends on

the algorithm we are implementing. Example of Soperator

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

EfcientcircuitimplementationforcoinedquantumwalksonbinarytreesandapplicationtoreinforcementlearningThomasMullorIRTSaintExuperyToulousethomas.mullor@irt-saintexupery.comDavidVigourouxIRTSaintExuperyToulousedavid.vigouroux@irt-saintexupery.comLouisBethuneUniversit´ePaulSabatier,IRITToulouselouis.beth...

展开>> 收起<<

Efﬁcient circuit implementation for coined quantum walks on binary trees and application to reinforcement learning Thomas Mullor.pdf

共8页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Efﬁcient circuit implementation for coined quantum walks on binary trees and application to reinforcement learning Thomas Mullor

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: