Super-polynomial and exponential improvements for quantum-enhanced reinforcement
learning
Vedran Dunjko,1, ∗ Yi-Kai Liu,2, † Xingyao Wu,2, ‡ and Jacob M. Taylor2, 3, 4, §
1

arXiv:1710.11160v2 [quant-ph] 12 Dec 2017

Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-Str. 1, D-85748 Garching, Germany
2
Joint Center for Quantum Information and Computer Science,
University of Maryland, College Park, MD 20742 USA
3
Joint Quantum Institute, National Institute of Standards and Technology, Gaithersburg, MD 20899 USA
4
Research Center for Advanced Science and Technology,
University of Tokyo, Meguro-ku, Tokyo 153-8904, Japan
Recent work on quantum machine learning has demonstrated that quantum computers can offer
dramatic improvements over classical devices for data mining, prediction and classification. However,
less is known about the advantages using quantum computers may bring in the more general setting
of reinforcement learning, where learning is achieved via interaction with a task environment that
provides occasional rewards. Reinforcement learning can incorporate data-analysis-oriented learning
settings as special cases, but also includes more complex situations where, e.g., reinforcing feedback
is delayed. In a few recent works, Grover-type amplification has been utilized to construct quantum
agents that achieve up-to-quadratic improvements in learning efficiency. These encouraging results
have left open the key question of whether super-polynomial improvements in learning times are
possible for genuine reinforcement learning problems, that is problems that go beyond the other
more restricted learning paradigms. In this work, we provide a family of such genuine reinforcement
learning tasks. We construct quantum-enhanced learners which learn super-polynomially, and even
exponentially faster than any classical reinforcement learning model, and we discuss the potential
impact our results may have on future technologies.

I.

INTRODUCTION

Quantum machine learning (QML) is a relatively new
discipline that investigates the interplay between quantum information processing and machine learning (ML)
[1]. A particularly prominent research line in QML investigates the potential of utilizing quantum computers to
solve ML tasks faster. Thus far, most of the attention in
QML has focused on data analysis settings, corresponding to supervised learning (e.g., classification) and unsupervised learning (e.g., classification), which are two, out
of three, canonical modes of ML.
The quantum algorithms showing the potential for
polynomial and even exponential speed-ups for related algorithmic tasks are already numerous. Notable examples
include algorithms for k-median [2] or k-nearest neighbour classification [3] (polynomial speed-up) or support
vector machines [4], topological analysis [5] and Gaussian process regression [6] (up to exponential speed-up).
Quantum methods may in fact yield the best long-term
solutions to mitigate the computational intractability of
the analysis the already massive databases which grow at
an exponential rate.
Beyond the pragmatic topics investigated in modern
machine learning, aspects of learning, and learnability
have also been studied from a more foundational perspective, most often by distinct scientific communities.
Specifically, computational learning theory (COLT) studies the mathematical foundations of learning, combining
aspects of supervised learning with computational complexity theory. In COLT, one deals with the problem
of learning concepts, which are n−bit boolean functions
f : {0, 1}n → {0, 1}, in various scenarios. Two examples of typical tasks are to well-approximate the behavior

∗
†
‡
§

vedran.dunjko@mpq.mpg.de
yi-kai.liu@nist.gov
wu.x.yao@gmail.com
jmtaylor@umd.edu

of an unknown concept, based on a collection of examples (x, f (x)), and to exactly guess f (·) given black box
access to f (·) itself, all the while using as few samples
(or queries) as possible. These two settings are studied
in probably approximately correct learning, and learning
from membership queries, respectively. Many models of
COLT have also been studied in the quantum setting, and
various bounds on the possible classical-quantum separations are known. See [7] for a recent review of the topic.
Beyond supervised and unsupervised learning settings,
which essentially deal with data analysis, reinforcement
learning (RL) [8], deals with interactive learning settings,
and constitutes an effective bridge between data-analysis
oriented ML and full-blown artificial intelligence (AI) [9].
In RL we deal with a learning agent, which learns by
interacting with its task environment. In RL, the agent
perceives (aspects of) the states of a task environment,
and influences subsequent states by performing actions.
Certain state-action-state transitions are rewarding, and
successful learning agents learn optimal behavior (see Fig
1 for an illustration).
RL is traditionally closely linked to robotics and feedback control tasks, and is thus also a pragmatically wellmotivated flavour of learning. For instance, RL plays a
pivotal role in modern learning technologies – from artificial personal assistants and self-driving cars, to the
celebrated AlphaGo system which, startlingly, surpassed
human-level gameplay in Go [10]. While this initial exciting result relied on various flavours of learning to achieve
superior game-play, the most recent, and strongest variants (which now beat also best humans and software in
chess), no longer utilize supervised learning from human
examples and rely on RL and self-play [11, 12]. Consequently, RL has been receiving an increasing amount of
attention in recent times.
However, possible quantum enhancements in this more
general learning setting have been explored only in few
works. For instance, in [13], a quantum algorithm that
quadratically speeds up a variant of the Projective Simulation [14] model was proposed. In [15] it was investigated whether quantum annealers could offer compu-

2
Agent
Agent

s
a

Learning
model

Environment
Environment

Reward
p=0.9

2

FIG. 1: Illustration of the the basic agent-environment paradigm: an
agent navigates a task environment (e.g. a maze) by taking actions
and by receiving percepts (signals s, e.g. labels of possible positions in
the maze). In RL, percepts can be rewarding. Basic environments are
characterized by Markov decision processes (inset in environment), in
which case the percepts are the states of the environment.

tational speed-ups for Boltzman machine-based RL engines. In these proposals the internal computation of
the agent was quantized, while the interaction with the
environment remained classical. In [16, 17], the agentenvironment interaction (see Fig. 1) was also quantized,
essentially as a conventional two-party quantum communication setting. In this framework, certain conditions
were identified, which allow quadratic improvements in
learning efficiency (an analog of query complexity) for
a class of RL scenarios, by utilizing amplitude amplification. Certain criteria prohibiting improvements have
been identified as well.
In this work we focus on the question of the limits of
speed-ups in learning efficiency, and address the question
of whether “genuine” RL settings allow super-polynomial
or exponential speed-ups.
This question has an obvious practical relevance, as
larger quantum speed-ups are more likely to produce a
real advantage in the real world, as they can more easily counteract the costs of implementing a fully quantum scenario. At the same time, this question is of fundamental importance, because it is known that superpolynomial quantum speed-ups are only possible under
special circumstances. For instance it is known that
super-polynomial quantum speed-ups in query complexity are only possible for promise problems [21]. Further,
there is evidence that super-polynomial speed-ups in general require substantial combinatorial or algebraic structure [22] in the underlying problem.
As our main result, we present classes of task environments where quantum-enhanced agents achieve optimal
behaviours in polynomial time (in the size of the task
environment), but where any classical learner requires
super-polynomial or even exponential time to achieve
equal levels of efficiency.
To achieve such a speed-up, the environment must allow a rather controlled interaction with the agent (e.g.
superpositions must be maintained), which is not typically possible in “real-world” macroscopic environments.
Nonetheless, our results can be significant, other than for
fundamental reasons, e.g., in the context of quantum laboratories (where the environments are genuine quantum
systems), in model-based learning [9], but also in any
setting where the RL steps serve as a pre-training before
encountering the real world. Here one can consider simulated environments, but perhaps the best example is the
case of self-play utilized in AlphaGo [10] and AlphaGo
Zero [11, 12], which is internal to the agent and thus can
(at least in principle) be fully quantized.
In our approach, we establish a connection between the

quantum query model, quantum COLT and quantum RL.
We point out the fact that, technically, the RL paradigm
subsumes standard COLT and oracular setting, and in
this sense, any quantum separation in those models could
yield a trivial separation for the RL analog. However,
we go beyond this, and show that quantum oracle identification techniques can also be useful in more general
RL settings, which satisfy arguably natural criteria – the
desiderata for generic RL settings – designed to separate
RL, from the more restricted learning models.
The basic idea can be summarized as follows. The
learning of the the quantum-enhanced agent is split into
two phases. In the first phase, it will utilize quantum interaction (via so-called oraculization discussed presently)
with the task environment, to effectively simulate access
to a quantum oracle, which conceals critical information
about the environment. In the second phase, it will use
this information to quickly find optimal behavior in the
given task environment.
Here, we will utilize the ideas from oracle identification theory to construct the task environments, and to
prove the quantum-classical separation: the hardness of
the learning task for the classical agent, and the existence
of quantum agents who solve the problem rapidly. While
in the classical theory, aspects of COLT have been employed in the context of RL theory previously 1 , in this
work (quantum) COLT results directly enable improvements of the performance of RL agents. It should be
pointed out that such a positive influence only works in
the quantum setting: in the classical case, splitting the
learning problem into first identifying the hidden features
via the effectuated oracle, followed by standard RL, is not
as beneficial 2 .
From a pure theoretical perspective, the connection we
establish may also be interesting as the setting of quantum RL we establish strictly generalizes standard oracular settings (as we detail presently, the oracles are “constructed” by the agent using many interaction steps) and
may thus give rise to new insights into the question of
quantum speedups.
The environments we present will be constructed as to
match chosen and well-understood oracular identification
problems – specifically Recursive Fourier Sampling (RFS)
[18, 19] and Simon’s problem [20] – while at the same time
satisfying the criteria of generic RL settings. There are
multiple motivations for considering these two examples.

1

2

One example of such a connection pertains to the approaches of
identifying bounds (and a robust definition) of sample complexity
for reinforcement learning. This topic has has also attracted significant attention [24–26] in both infinite and finite horizon cases,
from the theoretical community. Especially in early works [24],
insights from COLT are used to provide the bounds, also establishing connections between RL and COLT settings, in a manner
not dissimilar to our own approach. Furthermore, in establishing the bounds in [24], the authors utilize intermediary models of
RL, which are e.g. strictly episodic, or allow environmental resets
by the agent, which are analogous to the approaches suggested in
[16, 17] and this work. The proximal motivation for considering
such models is however a bit different – in the work [24], it is used
to establish lower and upper bounds. In [16, 17], it is central in the
quantum oraculization process, which in the end ensures quantum
improvements.
More precisely the time the agent would spend for classical oracle identification would be better spent on RL from the very
beginning. In the quantum case, the quantum speed-up of oracle identification dramatically off-sets this balance, and an agent
utilizing this split will outperform any classical agent.

3
The choice of Simon’s problem lies in the rather straightforward encoding of the problem in an MDP, which still
yields a provable exponential separation. On the other
hand, the RFS problem has a more modest separation,
but has a more intricate structure, which is interesting to
explore from a RL perspective. In particular, although
both Simon’s problem and RFS are typically considered
“unnatural” 3 , at least from the perspective of the theory of algorithms, the RFS problem has a recursive, selfsimilarity structure, which one could envision in natural
learning problems.
Finally, both Fourier sampling and Simon’s problem
play a role in the early results of quantum COLT: in the
seminal work of [29] the quantum Fourier sampling algorithm is used to efficiently learn DNF formulas just from
examples under the uniform distribution, and in [35], Simon’s algorithm is used to prove that if one-way functions
exist, then there is a superpolynomial gap between classical and quantum exact learnability. In this work, the
use of oracular separations for RFS and Simon’s problem
are, however, simpler and less subtle than in these quantum COLT works. To ensure that we have a formally
provable improvement over best classical agents, the environments will still have quite a rigid structure. We will
discuss how this rigid structure can be significantly relaxed, while maintaining the same level of performance
of the quantum agent. However, in this case we give up
on strictly proving that classical agents cannot perform
as well. While the results with pure provable separation
are certainly more elegant, the more general settings are
likely to be of a larger pragmatic value.
The remainder of the paper is split into the section
II which covers the basic technical background, section
III which discusses the embedding of oracle identification problems into RL tasks, and presents the criteria for
“qenuine” RL problems and in sections IV and V we provide our main results. Following this, in section VI we
discuss the relevance of our results on RL in practice, and
finish off with the final discussion in section VII.
II.

TECHNICAL BACKGROUND

To precisely state the main results of our work, and to
sketch the proofs, we first introduce the basic concepts
from classical RL theory, basics of the quantum agentenvironment and quantum RL framework introduced in
[17]. At the end of the section we introduce the class of
recursive Fourier sampling (RFS) problems, which we
use to construct the task environments and prove the
classical/quantum separation.

A.

The setting of reinforcement learning

The basic elements of RL are a learning agent A and
task environment E. The agent operates in, and in-

3

While both Simon’s problem and period finding over ZN are instances of the Hidden subgroup problem for Abelian groups, the
latter is considered more natural by some authors, if for no other
reason, then because the decidedly “natural” problem of integer
factoring reduces to period finding, which is at the crux of Shor’s
factoring algorithm [28].

fluences, the environment E by executing actions, and
perceives the environment by receiving percepts. Percepts characterize part of the environmental state that
is observable for the agent. Abstractly, A and E interact by the exchange of actions, from the set A = {ai },
and percepts, from the set S = {si }. We consider finite sets of actions and percepts. Further, in RL, the
agent is driven to correct behavior by the issuing of rewards, from some ordered set Λ, e.g. Λ = {0, 1}, or
Λ ⊆ R. When the environmental state is fully observable, the percept set is the set of environmental states
(the set of states for short), and a common mathematical specification of such a task environment is a Markov
decision process (MDP). An MDP is characterized by
the action, state and reward sets, a stochastic transition
function PT (sj |si , ak ), specifying the transition probability from state si to sj under action ak , and a stochastic
reward function R(si , aj , sk ) ∈ Distr(Λ), which to each
arc (si , aj , sk ) assigns a probability distribution over the
reward set.
For convenience, we will also assume an MDP M also
specifies an initial state s0 ∈ S. A policy (of an agent)
{π(a|s)}s is the set of conditional probability distributions specifying the probability of (an agent outputting)
an action a given the state s. Given an MDP M , and a
policy π, for γ ∈ (0, 1), the γ−infinite horizon expected
Pl
reward is given with Rπ∞ = liml→∞ Eπ,M [ k=0 γ k Rkπ ,]
where Rk is the reward obtained at the k th step of interaction4 . The expected value is taken over the (stochastic) policies, transitions and rewards. N −finite horizon
expected reward RπN , is defined as the expected value of
the cumulative reward after N interaction steps. Both
finite and infinite horizon rewards can also be considered
starting after some finite step k, in which case we denote
them Rπ∞,k and RπN,k .
∗
A policy πM
is an γ−optimal (N −optimal ) infinite (finite) horizon policy, if it maximizes the expected reward
Rπ∞ (RπN ), in the MDP M . The set of optimal policies
always contains extremal policies (deterministic policies,
i.e. where each π(·|s) is Dirac-delta distributed) [31].
We will say that a learning agent A is (, δ)−efficient
after k steps if the infinite horizon rewards R of A
measured after the k th step for the agent A, satisfy
Rπ∞,k
≤ R + , except with probability δ. Analogous
∗
definition holds for the finite-horizon case. In other
words, the agent is (, δ)−efficient after N steps, if after
N steps, except with probability δ, it becomes equally
(up to ) rewarded as the optimal agent 5 .
We can summarize the goal of RL as the task of the
design of agents that can learn the optimal policy, or,

4

5

Whenever Λ is bounded, the γ k decay term ensures the series
converges as it is upper bounded by λmax /(1 − γ), where λmax is
upper bound on the reward values.
Another possibility would be to define an agent to be
(, δ)−efficient if its policy after N steps matches the optimal policy. However this may be overkill as the optimal policy may define
optimal behavior for large regions of the environment an agent is
not likely to reach, and which are unlikely to be reached under
optimal behavior. The distance measure on policies then becomes
complicated as it must take into account the fact that the behavior on certain states matters more than on others. Further, this
cannot be (straightforwardly) evaluated from the history of interaction alone. Measuring efficiency operatively, i.e. only relative
to elapsed history mitigates both issues.

on the tester register RT , for all steps t. The history,
E is described by a distribution over histories (of length
relative to a given tester, is defined to be the state of the
t), denoted by A $t E. Most figures of merit are then
register RT . A tested interaction is shown in Fig. 1.
4
extended to such distributions by convex-linearity.
To recover, e.g., supervised learning in this paradigm,
···
···
take Eover
to be
characterized
the distribution
P (x, y),RL: RA /
more generally,
time
behave as by
successfully
as optiMA
MA
t
1
RC
•
•
• ···
•
• ···
where
the
agent
is
given
an
n
sized
sample
of
(x,
y) pairs
ME
ME
ME
t
1
2
mal agents. We will require a few more specific characRE /
···
···
as the first n percepts. After this, the agent is to respond
terizations of environments. An environment (MDP) is:
T
T
T
T ···
T ···
RT /
U
U
U
U
U
with labels as actions to given percepts, now unlabeled
2t 1
2
3
4
2t
episodic, if data-points
the environment
is re-set to the initial state
x. This setting is native to RL if the percept
FIG. 1. Tested agent-environment interaction. In general,
once a rewarding
transition
hasreinforcement
occurred (ifsignal
the rewards
space also
contains the
– the reward.DL:
each map of the tester UkT acts on a fresh subsystem of the
are stochastic,
obtaining
a
reward
of
zero
value
still
causes
We denote the percept space including the reward status
register RT , which is not under the control of the agent of the
a re-set), and
η−episodic,
if thethen
environment
as S̄ strictly
(e.g., if rewards
are binary
S̄ = S ⇥ {0, is
1}).
environment. The crossed wires represent multiple systems.
for
re-set to the The
initial
state after exactly
η steps.
An envi-inter- FIG. 2: RL: Tested agent-environment interaction suitable
agent-environment
paradigm
is a two-party
reinforcement learning. In general, each map of the tester UkT acts on
active
setting, and
thus convenient
for a quantum
restriction
testers
controlled
mapsthe
relative
ronment has
immediate
rewards
if the occurrence
of anyinfor-a fresh The
subsystem
of thethat
register
RT ,are
which
is not under
control of
of QML.with
All the
nor of the
environment.
crossed
represent
to agent,
the classical
basis
guaranteesThe
that,
for wires
any choice
of
state-actionmation
(s, a) treatment
pair consistent
an existing
optimalresults
policygroup the
multiple systems. DL:
setting of standard quantum
into four categories: CC, CQ, QC and QQ, depending
the local maps UTx ,The
thesimpler
interaction
between classical A
yields the largest
(average) reward, i.e. for any other a0
machine learning, where
the environmental map is without internal
on whether the agent (first symbol) or the environment
and E remains
tester copies the
memory,unchanged.
presented in A
theclassical
same framework.
the expected immediate reward of (s, a0 ) is smaller. In the
(second symbol) are classical (C) or quantum (Q) [30].
content of RC relative to the classical basis, which has
simplest case
deterministic
binary
rewards,
thislearning.
simply The
TheofCC
scenario covers
classical
machine
essentially the same e↵ect as measuring RC and copying
means thatCQ
every
correct
move
is rewarded.
Otherwise
setting
asks how
classical
ML techniques
may aid in
outcome. In other
words, the The
interface
between
and enthe the
environment,
respectively.
agent,
andAthe
the setting quantum
has delayed
rewards
a prototypical
example
tasks,
such as–quantum
control [14,
15], quanE is then classical. It can be shown that, in the latter
are modelled as (infinite) sequences of CPTP
is a maze problem,
where[16],
rewards
arequantum
issued only
once [17]vironment
tum metrology
adaptive
computing
case, for
any quantum agent and/or environment there
{MiA }i , and {MiE }i , acting on the Hilbert spaces
the maze isand
solved,
although
there are
obvious [18].
“wrong”
the design
of quantum
experiments
Here we,maps
exist classical A and E which generate the same history
⊗ HC any
andtester
HC ⊗
HE In
, respectively.
percept
for example,
deal with
non-convex/non-linear optimiza-HA under
and “correct”
moves along
the way.
[20].
other words, The
classical
agentsand
action
sets
are
promoted
to
sets
of
orthonormal
vectors
tion problems arising in quantum experiments, tackeled
can, in QC settings and, equivalently, in classically tested
Finally, we
thecorresponds
notion of “observabil|s ∈settings,
S} andachieve
{|ai |athe∈same
A}, performance
which are also
mutually
by will
ML comment
techniques.onQC
to quantum vari-{|siQQ
as quantum
ity” in the ants
context
of RL algorithms
task environments.
A generalof learning
[7, 10, 19] facing
a classicalorthogonal.
states are referred
to as
classical
agents, in These
terms ofbasis
any history-dependent
figure
of merit.
ization of MDPs
are so-called
partially-observable
MDPs
environment.
Figuratively
speaking, this studies
the po-states.
space of the
Thus,The
the Hilbert
only improvements
canchannel
then be isin spanned
terms of by
(POMDPs),tential
which
a with
set aofwith
obserof aadditionally
learning robot,specify
enhanced
a “quan-these
computational
two sets, socomplexity.
HC = span{|xi | x ∈ S ∪ A}.
tum chip”.
In QQ than
settings,
of this work,
vations (typically
smaller
thethe
setfocus
of states),
andboth TheScope
and limits
of quantum
improvements.–
Whatthe
classical
setting
is recovered
by restricting
A function
and E arespecifying
quantum systems.
Here, the interaction
a stochastic
which observation
the
is the
ultimate
potential to
of classical
quantum maps,
improvements
agents
and
environments
see [16]in for
can bean
fully
quantum,
and even the
question
of rewhat it
learning?
In the QC
tested
settings,
agent sees given
actual
environmental
state.
Many
a formal
definition.
In and
the classically
generic RL
picture,
thewepermeans
“to
learn”
becomes
problematic
as,
for
instance,
are bound
to computational
complexity
improvements,
sults which hold for MDP settings fail in the more general
formance
of
the
agent
is
defined
with
respect
to
the histhe agent
and environment
may become
entangled.
which have been achieved in certain cases. Improvements
case, including
the convergence
properties
of standard
RL
tory
of
interaction
–
the
sequence
of
state-action-reward
Framework.– Since learning constitutes a two-player
in learning efficiency require special type of access to the
algorithms [9]. In this case, the observation of the agent
realized by the agent-environment interaction. In
interaction, standard quantum extensions can be applied:triplets
environments, which is not fully tested. Exactly this is
does not suffice
for the agent to output the optimal acquantum
thethehistory,
evaluation
is modthe action and percept sets are represented by the afore-the done
in [6,case,
8], for
purposeand
of its
improving
computation. An example
a mazespaces
whereHAthe
position
by utilizing
a tester
– a fourth
which can
mentionedis Hilbert
, HSagent’s
. The agent
and theeledtional
complexity,
with great
success, system
as the improveis not givenenvironment
to agent: the
just seescommunication
the same state,
the
communication
alone,
andofe.g.,
act agent
on a common
registerinteract
ment with
can be
exponential.
There, channel
the classical
source
for each position,
except
perhaps the
initial
room,
RC (capable
of representing
both
percepts
and and
actions).copysamples
the transcript
of
the
interaction
(classical
tester),
is substituted by a quantum RAM [23] archi- or
the exit. These
can (environment)
be solved, but
to perform
Thus,cases
the agent
is described
as aoptisequenceleave
the interaction
unmeasured.
tecture,
which allows
for the accessing of many samples
t
mally, the agent
must
keep
oftE })–
its previous
actions,
of CPTP
maps
{Mtrack
one for each
time-step – Tested
in superposition.
a substitutionincomes
naturally
interaction Such
is demonstrated
Fig. 2,
part RL.
A } ({M
which
acts on the
register
RC , but6 .also a private registerFor in
as just what
it observes
does
not suffice
(un)supervised
settings,
the basic interaction
comcomparison,
Fig.
2 alsoasdemonstrates
what convenRAus(Rto
which
constitutes
the internal memory
E ) the
prises
only two stepslearning
and is memoryless
the agent
This leads
definition
of observability:
a taskof thetional
(un)supervised
settings, –where
the reinteragent
(environment).fully
This observable
is illustrated ifin optimal
Fig. 1 above
quests
M samples,
and the environment
provides them.
environment
is (effectively)
action
is with
a (quantum)
database (denoted
qMem),

behavior is achieved by a simple policy which specifies
the subsequent action given only the current observation/percept. In our constructions of task environments
from oracles we will often “maintain observability”, which
will usually mean expanding the state space of the MDP
to include all the necessary information for the agent to
perform optimally – this is usually a (part) of the history
of interaction.

B.

Framework for quantum reinforcement learning

As mentioned, the overarching formalism of RL is that
of an agent-environment interaction. This is generalized to the quantum setting in a natural fashion as follows. The quantum agent-environment setting is defined
by three quantum registers RA , RC and RE , with associated Hilbert spaces HA , and HC and HE , specifying
the memory of the agent, the agent-environment interface (the communication channel ), and the memory of

6

It should be noted that quantum generalizations of POMDPs have
been considered previously [27]. In the context of this work, however, we deal with environments which are specified by fully classical MDPs, but which are “accessed” in a quantum fashion, as
explained shortly.

correspond to in the same quantum agent-environment
formalism.
The input-output relations of a fully observable classical task environment are fully specified by an MDP. In
this case no particular distinction need be made between
the task environment (in the sense of the set of CPTP
maps), and the MDP which describes it. In particular,
there may be many task environments for the same MDP,
but no agent can distinguish between them using the allowed interface.
However, if we allow quantum interaction, this is no
longer the case and to an MDP we may associate a set of
compatible task environments. Each such environment
we call a realization of the MDP. An easy way to think
about various realizations is in terms of quantum circuits
specifying the maps of the environment. In [16] it was
shown that for any η−episodic environment (which does
not need to be fully observable), there exists a realization
with a few properties including a well-specified “ancillary
workspace”, and a construction that is self-inverse7 .
η-episodic deterministic environments that are realized

7

For the case of deterministic environments, one can imagine the
environment to be a system with “action memory” storing the
actions given by the agent, and a register filled with fresh ancilla
systems which will be output to the environment. The map or the
environment is a classically controlled map which, conditioned on

5
self-reversibly and which have a specified ancillary
workspace are called quantum-accessible environments,
and we will denote them with Eacc . The notion of
quantum-accessible environments includes a broader set
of environments, which are not strictly episodic nor
deterministic, but for simplicity we will adhere to this
special case for now.

1.

Oraculization of quantum-accesible environments

Consider an agent facing a quantum accessible (deterministic, η−episodic) environment, where the overall setting additionally allows the agent to intermittently interfere with the ancillary workspace via processes called register scavenging and register hijacking
[16]. In our example of oracular function evaluation
|xi hx| 7→ |f (x)i hf (x)| , scavenging properties would enable the agent to e.g. effectuate access to the (more
useful) instantiation of the form |xi |bi 7→ |xi |b ⊕ f (x)i .
However, in our approach to quantum RL, we do not
just assume access to whatever type of a derived oracle
we would find useful. Rather, we attempt to identify minimal assumptions, and constructions one may employ to
simulate access to such oracles, given a natural specification of a task environment. Such issues naturally do not
exist in the fully classical case. Note, while these options
are not typically assumed in RL, they offer no advantage
in the classical case, nor do they allow direct access to
the specification of the environment.
In the case of suitably quantum accessible environments, the agent can utilize approximately 5η interaction
steps with the environment to simulate a particular type
of oracle specified with
Eq : |a1 , . . . , aη i |yi 7→ |a1 , . . . , aη i |y ⊕ RE (a1 , . . . , aη )i ,
where R(a1 , . . . , aη ) is the reward value obtained by the
agent once the agent executes the sequence of actions
a1 , . . . , aη ,8 and ⊕ denotes addition in the appropriate
group. In broad strokes, this is achieved by having the
agent utilize the first η steps to input some action sequence of length η (collecting η percept states), while
collecting the memory the environment traces out using
scavenging. Scavenging also costs η steps.
Following this, using hijacking (η steps) and the fact
the environment is self-reversible, the agent uses η steps
to “un-compute” the percept responses of the environment. Importantly, this can be done in a manner which
does not un-compute the reward value. The last scavenging round (η steps) collects the actions. Eq is referred
to as the oracular instantiation of the environment, and
each invocation of this oracle is counted as 5η interaction
steps. See [16] for details on the construction.

8

the state of the “action memory” (denote this a) applies the rotation Ua onto the fresh system, which rotates its state to the correct
response s(a). Each such rotation Ua need only non-trivially act
on the two-dimensional subspace of the correct response, and the
fiducial ancilla state, which means it can be chosen Hermitian and
hence self-reversible. Similar albeit more complicated process for
certain stochastic environments was described in [16, 17].
Note that this is a well-defined quantity only in deterministic environments, where the action sequence deterministically specifies
the corresponding state sequence, and reward values.

The access to such an effective oracle Eq was used
to obtain a quadratic quantum advantage for quantum
learning agents in [16, 17]. Note, in the case the task
environments are constructed (e.g. in model-based learning settings [9], where the agent internally constructs a
simulation of the environment), the internal construction
process can directly realize the oracular instantiation. An
environmental setting where the agent can choose to interact with the environment Ec (any from the set {Ei }
where each Ei is a sequence of CPTP maps, realizing
the same input-output specification of the task environment under classical access) or Eq (either via simulation
or construction), we call a controllable environment.

C.

Oracles and hidden secrets: recursive Fourier
sampling and Simon’s problem

The first settings in which quantum computation
yielded provable improvements over classical computation involved the use of oracles, specifically the problems of oracle identification, which can be broadly specified as follows: for a (finite) set of oracles O = {Oi }i ,
whichSis partitioned as a collection of disjoint subsets
(O = j Oj , Ok ∩Ok0 = ∅, unless k = k 0 ), given access to
an oracle O, identify which subset Oj it belongs to. First
examples here were the Deutsch and the Deutsch-Jozsa
algorithm, where the set of oracles contained all boolean
functions which are
(subset of 2 elements) or bal
 constant
anced (subset of

n
n/2

elements), basic Grover’s search

[? ] (where the subsets are singlet sets, and the oracles are promised attain value 1 for one element and zero
otherwise). Depending on the details of figures of merit
one considers, and the exact specification of what oracles
do, this framework also captures COLT as well 9 . In this
work we will in particular rely on properties of Recursive Fourier Sampling (RFS) [18], and of the well known
Simon’s problem [20], both of which are oracle identification tasks in the sense above.

1.

Recursive Fourier Sampling

RFS [18] is an oracular problem in which superpolynomial separations between classical and quantum
algorithms can be obtained. The problem owes its name
to its recursive structure, which builds on the basic, unit
depth instance. We assume a computable, binary function f : X × X → {0, 1} (inner product in the original
Bernstein-Vazirani variant of RFS, generalized to many
others in [19]). The depth-1 instances are specified as follows: given access to an oracle evaluating O(x) = f (s, x),
identify s, where s is a hidden secret string. To achieve
deeper structures, the problem is composed. This leads
to an 2n -arry symmetric tree construction, of depth l. In
what follows, we adhere to the formalization as given in

9

If the oracles are functions which can be queried, then this constitutes the standard oracular setting, or, similarly, learning from
membership queries. However, they could also be objects which
produce samples from unknown distributions, in which case we are
broaching the conventional probably approximately correct learning.

6
[19], and we choose to work with bit-strings, for concreteness.
To each vertex of the v of the 2n -arry tree we assign
the local label xv ∈ X = {0, 1}n , where the root has label
∅ (and is at level 0). Further, to each vertex we assign
the path-label specified with, for a vertex at depth k, the
Sl−1
sequence xv = (xpak (v) , . . . xv ) ∈ XΣ = k=0 X k , (where
pa(v) is the label of the parent of the vertex v, X k is the
k th Cartesian power of X with X 0 = ∅, and pak (v) =
pa ◦ pa · · · pa(v) is the k th ancestor of v.) designating the
unique path from the root to the vertex in question, using
local labels of each vertex along the path. The label ∅ is
both the path-label and the local label of the root.
To each vertex we also assign a hidden string of length
n, specified by a secret-string function defined on the
path-labels: s : XΣ → X.
We are given access to the oracle for the generalized
RFS (gRFS) problem10 OgRF S : XΣ → {0, 1, ⊥}, defined
with:
OgRF S (x1 , . . . , xk , a) =
(
f (s(x1 , . . . , xk−1 ), xk ), if a = s(x1 , . . . , xk )
⊥,
if a 6= s(x1 , . . . , xk ),

(1)

O(n2log((8/δ)ln(8/δ)) ) queries, where δ is a constant12 . To
emphasize the fact we consider the problem of returning
the entire secret, we refer to the constructions above the
recursive hidden secret problem.
The (classical) lower bound of the query complexity
is established for the problem of identifying the final
bit b. However, the problem of finding the entire sequence s(∅) is harder: if an algorithm using no(log(n)) (less
than nlog(n) ) can only guess with probability bounded
away by n−Ω(log(n)) , then no algorithm with running time
no(log(n)) can output the bit sequence s(∅) with probability above n−Ω(log(n)) (as it would cause a contradiction).
The quantum oracles for this problem are standard “bitflip” oracles. In the specification of the classical oracle
OgRF S the input size may vary, which is not standard in
the case of quantum oracles. This is resolved by either using access a family of oracles of varying input sizes which
can be called, or, alternatively we can introduce an ancillary symbol to the input space, to “void” parts of the
input in the case of smaller input sizes. Next, we give
the details of the original Simon’s problem, which is, arguably, simpler.
2.

if 0 < k < l, and
OgRF S (x1 , . . . , xl ) = f (s(x1 , . . . , xl−1 ), xl ) otherwise.
In other words, for the leaves of the tree, we can (indirectly) access the secret strings of the leaves’ parents.
Since we have chosen to work with bit-strings specifying
both labels and secrets, Eqs. (1) and (2) contain an ambiguity as identical inputs can be interpreted as instances
of a leaf-query OgRF S (x1 , . . . , xl ), or as instances of a
penultimate layer query OgRF S (x1 , . . . , xl−1 , a). There
are a few options on how to resolve this technicality, and
in the subsequent constructions, we shall use one additional bit specifying whether we are requesting a leaf or
a parent-of-leaf query.
To access the hidden values of any vertex whose children are not leaves, we, generally, need the secret strings
of O(n) of the children first.11 The oracle (or the root,
if you will), hides one bit b∅ , which is revealed given the
secret string of the root:

⊥ if a 6= s(∅)
if k = 0, OgRF S (a) =
(3)
b∅ , if a = s(∅)
Intuitively, to access the hidden value b∅ , we need the
secret string of the root, which in turn requires O(n) secret strings of its children, and each of those needs the
same, and so on recursively. The standard gRFS problem is the computation of the single bit b = OgRF S (s(∅)),
with bounded error probability. The tree depth l is chosen to be O(log(n)) to realize instances with the superpolynomial separation. While the results of [19] focus on
returning the single bit value, the quantum algorithm employed actually returns the entire bit-string s(∅) utilizing

10

11

As noted, in the original RFS problem the function f is the inner
product, and the separation is based on the Hadamard transform.
This has been since greatly generalized in [19].
This is easy to see when f is the inner product, as choosing all the
children with labels corresponding to the canonical vectors returns
exactly the secret string of the parent, bit-by-bit. Also, this is the
reason why the scaling is nlog(n) for the classical algorithm – there
are n canonical vectors, and the tree is depth log(n).

Simon’s problem

(2), an oracle encodIn Simon’s construction, we are given
ing a function f : {0, 1}n → {0, 1}n , with the promise
that there exists a secret string s ∈ {0, 1}n , such that
f (x) = f (y) if and only if x = y ⊕ s, where ⊕ is the
element-wise modulo 2 addition. The latter promise is
often referred to as the Simon’s promise, which thus guarantees that f is either a permutation (s is the all-zeroes
string) or it is a two-to-one function, assigning the same
value to two input strings if they differ by some s. In
the context of oracular identification, here we are dealing with the set of binary functions satisfying Simon’s
promise, which is partitioned into subsets specified by
the shift s. Intuitively, to identify s, one must find two
strings which attain the same value under f , which, again
intuitively, requires O(2n ) steps. A more careful analysis proves that any algorithm which finds s with nonnegligible probability needs Ω(2n/2 ) queries [20]. Access
to a quantum oracle mapping |xi |yi 7→ |xi |y ⊕ f (x)i, allows an efficient quantum algorithm for finding s, and this
can be done, e.g., by using a probabilistic algorithm [20]
using O(n) queries (which implies a zero-error algorithm
with expected polynomial running time), or a zero-error
deterministic algorithm with polynomial worst-case running time [38].
III.

GENERIC REINFORCEMENT LEARNING
PROBLEMS

The framework of reinforcement learning is very broad,
and supervised, unsupervised, COLT and even even standard algorithmic problems can be recast as a special MDP
learning task 13 . For didactic purposes, we will exemplify

12

13

This constant depends on the function f (and dispersing unitary
U which can be used to solve the corresponding problem), but for
simplicity this can be the inner product, so in nO(1) queries.
More precisely, to a family of tasks, specified by the instance size,
we can associate a family of MDPs.

7
this observation on the oracular identification problem of
Deutsch-Jozsa [32].

A.

Oracle identification as restricted RL settings

…

if O(11…

…

11) = 1

The Deutsch-Jozsa problem, as originally proposed, is
to decide whether a given binary function f : {0, 1}n →
{0, 1} is constant or balanced (i.e. |f −1 (0)| = |f −1 (1)|).
This is a promise problem as we are guaranteed the function indeed is balanced or constant.
An example of an MDP, which expresses f as a relation, and which encodes this problem has, as the state
space S = {(x, y) | x ∈ {0, 1}n , y ∈ {0, 1}} ∪ {0, 1, ∅}.
The agent’s actions are A = {(x, y) | x ∈ {0, 1}n , y ∈
{0, 1}} ∪ {q, Balanced, Constant}. The transitions are
specified as follows: the MDP is initialized in the state
∅. An action from the set {(x, y)} causes a deterministic
transition of the environment to the environmental state
with the matching label. This move can be interpreted
as a “loading of a query” (old queries are overwritten, if
sequential loading is executed). The agent can execute a
query, whenever it is in a query environmental state, via
the action q. If the environment is in the state (x, y), this
action is to be interpreted as “Is f (x) = y”? The transition under this query ends up in one of the two root states
root ⊥
root 1
0, 1 depending
onroot 0whether
f (x) = y. If the environment
a=0
a=1
a=g
is not in a query state (i.e. is in one of the “root” states
0 no transition
g
1
{0, 1, ∅}),
happens
under action q. Finally,
a=0 a=1
a=1
the agent
can, at any pointa=0proclaim its guess on whether
g1
00
01
the
function f isg0balanced
or constant by pera=1
a=0
a=0 underlying
a=1
forming the action Balanced or Constant. Regardless of
the state of the environment this action is executed in, a
transition to the root state ∅ ensues, and this transition
is rewarding if the guess is correct. This fully specifies
the MDP.
root

…

root 1

root 0
if f(x
)=y

(x,y)

rd
in
g

(x,y)

(x(m),y(m))

(x′,y′)

re
wa

if
b

al
an

ce
d

(x,y)
(x(m),y(m))

q

(x′,y′)

(x,y)

(x′,y′)

(x′,y′)

(x(m),y(m))

(x′,y′)

Balanced

…

(x(m),y(m))

(x′,y′)
(x(m),y(m))

FIG. 3: MDP(x,y)
for the Deutsch-Jozsa algorithm. The agent loads a
query via action of the form (x, y). m is the total cardinality of the
(x,y)action q executes
(x,y)the query. The agent can
query pair set {(x, y)}. An
guess whether the oracle is balanced
(x′,y′) or constant at any state, by using
(m))
the corresponding action,
this is a rewarding edge if it is correct
(x(m),yand
(pink edge in example). For clarity, some of the edges and actions are
given in gray, and some are not shown.

There are many possible ways to construct MDPs
which encode the Deutsch-Jozsa problem. For instance, a
functional variant would be even simpler: a two state environmental space, encoding just the oracle output, and
action set comprising an input to the oracle x, or a guess
in {Balanced, Constant}. The transition in the case of a
query input is deterministically to the state corresponding to the output, and in the case of a guess, any state
will do (but the reward status depends on the guess of
the agent, naturally). The first formulation we provided
corresponds to the input structure in the quantum instantiation of the Deutsch-Jozsa oracle, where the oracular

output is encoded in a bit-flip of an input value.
Similar constructions can be used to encode COLT
problems, and even algebraic problems suggests that
all more traditional settings where a classical/quantum
speed up has been proven imply a learning separation in
some set of RL settings. This would include speed-ups
based on e.g. efficient factoring [28], speed-ups obtained
certain quantum COLT settings (see [7] for an overview),
and more generally, speed-ups relying on oracular identification problems.
However, a gap in quantum RL, can be achieved
only provided the environment allows a particular type of
quantum access, and provided that there is a way of “converting” (or oracularizing) the environment the learning
agent sees into a suitable quantum oracle. Intuitively,
this oracularization construction must satisfy two conflicting requirements. On one hand, it must allow the
environment to respond to the actions performed by the
agent. But on the other hand, it should not generate entanglement between the agent and parts of the environment that are inaccessible to the agent – because, from
the agent’s perspective, this would cause a superposition
state prepared by the agent to decohere into a mixed
state, useless for quantum approaches. To satisfy these
two conflicting requirements, oraculization makes use of
two subtle tricks: first, it uses multiple rounds of agentenvironment interaction to simulate a single oracle query,
and second, it supposes that the agent can acquire (”scavenge”) those quantum registers that are discarded by the
environment (see [16, 17] for more detail). The settings
of oracular identification problems are naturally mapped
to MDP problems, with a restricted and rigid structure,
which on one hand leads to a simple oraculization, but
are, on the other hand, very restricted, and not “generic”
from a RL perspective. We will now use the DeutschJozsa running example to illustrate how oraculization is
achieved.
First, we fix the desired MDP – say the first, relational
construction in Fig. 3, called the DJ-MDP. This fixes a
family of possible environmental realizations {Ei } where
each Ei is a sequence of CPTP maps, realizing the same
input-output specification given by the DJ-MDP given
classical interaction. For illustration purposes, let us consider the state of the communication register C, under the
action of these maps. If the state of C is |(x, y)i , then
the state of C after the environmental map has been applied is unchanged, as this is what the specification of the
environment (given by the DJ-MDP) does. Thus, it may
seem that the environment does not need to copy this
information for future use – and this would make oraculization very easy – but this is not the case. Suppose
the agent acts by producing a query action, resetting the
register C to |qi . The subsequent state (the bit encoding
the validity of the claim f (x) = y) the environment must
effectuate depends on the previous state that the agent
deleted. That is any realization of the environment must
have memory beyond what is accessible in the communication register. Note, this implies that the maps of the
environment cannot be represented as unitaries acting
solely on the communication register.
However, the environmental maps only need to record
this one single memory step, which can be purged after 2
steps. Thus the environment is, effectively 2-episodic14 .

14

The classical specification does not have a 2-episodic construction,

8
At this point we utilize one of the main tools of oraculization, scavenging, which allows the agent to recover
this one-step memory, and effectuate the oracular instantiation performing |xi |yi 7→ |xi |y ⊕ f (x)i , which allows
it to employ the quantum Deutsch-Jozsa algorithm to its
advantage.
While the relational construction of Fig. 3 did not
lead directly to an unitary environment, for completeness,
here we should point out that the functional picture leads
to an MDP representation which encodes the DJ problem in a more convenient way. In particular the obtained
quantum maps realizing the environment indeed are almost just unitaries equal to the DJ oracle. In this setting,
the environmental states are (x, y) ∈ {0, 1}n × {0, 1}, and
the actions are from the same set. The transitions of
the environment are independent from the current state.
That is, regardless of the current state, an action (x, y)
causes a deterministic transition to the state (x, y⊕f (x)).
The construction above encodes the process of the classical querying of the (DJ) oracle, which can be quantized as
to match the process of querying the standard quantum
DJ oracle – consequently, quantum agents can employ
standard quantum strategies.
What remains to be achieved is to encode the actual
objective of the DJ task, which is to decide (or learn)
whether the maps encode a balanced or a constant function, into the MDP. For this, we simply append the
action set to include the additional two actions/levels
{Balanced, Constant} which cause no transition, but set
the reward bit to the appropriate value. The map realizing this MDP is just a local unitary acting as the
DJ oracle on the subspace of legal queries, and mapping,
e.g., |Balancedi 7→ |Balanced, Reward = 1i (if the secret
function is balanced, analogously for the case of a constant function), on this complementary “guessing” subspace.
Although both MDP constructions stemming from the
DJ task do allow for useful oraculization, the resulting
MDPs are very degenerate, and not particularly interesting from a RL perspective. To make this a bit more
formal we now specify reasonable “generic” MDP properties, which we require a “genuine” MDP to have.
B.

Characterization of genuine RL tasks

What deserves to be called a genuine MDP problem
family is a complex question, which we do not presume
to resolve here, and for most intents and purposes, in this
work we treat the terms “genuine” and “generic” interchangeably. Our objective is more modest, specifically
to identify criteria which invalidate certain MDP families – those which directly map to more specialized tasks
such as oracle identification, algebraic problems or COLT
tasks – while additionally striving to remove other obvious degeneracies.
In particular, our desiderata for “generic” MDP characteristics are thus:

b) the agent’s actions should genuinely influence subsequent states and the reward value, and
c) optimal behavior explicitly depends on the state label,
and not just interaction step counter.
The property a) eliminates direct trivial phrasings of
computational problems, and most direct translations of
conventional COLT settings. The MDP rewarding diameter refers to the maximal length of the shortest sequence
of moves of the agent that lead to a reward, provided the
sequence started from a state that is with bounded probability recurrently reached under every optimal policy –
in other words, in an MDP with a rewarding diameter d,
any optimal agent will, with constant probability, have
to execute d steps between two rewarding events15 . Since
we are interested in scaling statements, i.e. statements
regarding speed-ups with respect to (ever growing) families of MDPs, we additionally demand that the diameter
grows as well.
Property b) eliminates pathological settings where only
every k th move is (potentially) rewarding, but the actual
moves the agent makes in between do not matter. An
example of such a setting is say the standard COLT encoding, where between any two legitimate moves/queries,
we insert meaningless “filler” steps to artificially increase
the effective rewarding diameter.
Finally, c) eliminates deterministic maze settings,
where optimal behavior only requires the repetition of
a fixed sequence of actions. These maze-like cases, albeit
natural, allow for a rather straightforward modification
of computational theory scenarios to MDPs satisfying a)
and b) (but not c)) via a process of unwinding of the MDP
which introduces a size-depth MDP trade-off, which we
describe presently.
The criteria as presented above are meant to convey
certain intuitions about the properties “genuine” RL settings should have, but can nonetheless be in principle
fully formalized in terms of the characterization of the
transition function of the environment, and in terms of
the properties of the underlying MDP graphs. Further,
the criteria as listed are not fully independent. The last
two criteria, for instance, capture two facets of an abstract property of the optimal policy (which can be understood as a matrix), prohibiting it to be of too low a
rank. A low rank policy would mean meaning that the
agent should do the same thing in many states, or that
there are many free entries whose values do not matter.
Moreover, they, for instance, imply that the environment
cannot be deterministic.
Since what is meant by “genuine” RL problem is
subjective, and a matter of context, we do not proceed
further with the full formalization of such (to an extent
arbitrary) criteria. Even though they are quite descriptive, the properties a) − c) can be clearly verified for the
constructions that follow.

a) rewards are delayed, and the MDP rewarding diameter to optimal states should be scaling with the instance
size,
15

however the memory dependencies are such that we can use the
same tricks as in the case when it is.

Note that simply demanding that the MDP has long paths does
not suffice to eliminate otherwise pathological settings: one could
simply add long paths to an otherwise immediate reward setting,
which are never needed for optimal behavior. The rewarding diameter condition eliminates such possibilities.

9
executed at the root lead to the reward and reset the
problem – i.e. the rewarding diameter is constant (two).

IV. SUPER-POLYNOMIAL SPEED-UPS:
CONSTRUCTIONS FROM RECURSIVE
FOURIER SAMPLING

The overall idea is to identify MDPs which describe
task environments which the agent can, via oraculization, “convert” into useful quantum oracles. Overall, the
paradigm can be represented with the following expression:
realized as

quantum

M DP −−−−−−→ env. {Ei } −−−−−−→ env. Eacc
accessible

agent

quantum

information useful

simulates

interrogation

for RL advantage

−−−−−−→ oracle Eq −−−−−−−−→

(4)

Specifically, we construct environments that can be
used to construct RFS-type oracles. Moreover, we prove
that no classical agent can learn efficiently in the given
environments, as this would lead to a contradiction with
the optimal performance of classical RFS solving.
For didactic purposes, we shall first provide an MDP
construction M0 which closely follows the underlying
structure of the RFS problem. This directly translated
MDP M0 has none of the desired “generic” properties
described in Section III. However, we will provide two
intermediary MDPs, M1 and M2 , which will satisfy
properties a) and b). Finally, we will provide two more
demanding modifications realizing M3 which satisfies the
following global properties:
i) it satisfies the “generic MDP” desiderata a), b) and c),
ii) it maintains the classical hardness of learning, and
iii) it reduces via the oraculization process to the
same RFS-type oracle, leading to a quantum-enhanced
learning efficiency.

A.

The basic construction M0

Given an RFS oracle of tree-depth l, over n−bit labels,
the simplest MDP M0 would, as the action set have all the
possible queries to the oracle, and the possible outputs of
the oracle as the set of the states of the environment
(MDP). The only rewarding action is the action with the
label (s(∅)) executed given any state. This MDP satisfies
none of the conditions a)-c) from Section III. The optimal
policy is thus constant, and not particularly interesting.
B.

Unwinding the MDP

We can do better by restricting the action set to the
set of n-bit strings (recall queries to the RFS oracle can
comprise path-labels, so sequences of n-bit strings), with
an additional action denoted “q” (for “query”) used to
denote that the agent wishes to execute a query – this
controls the size of the input in the RFS oracle setting.
Intuitively, the agent can now “input” the desired query,
one n-bit block at a time, marking the end of the query
with q. Note that, in this case, to maintain full observability of this MDP M1 , the state space includes pathlabels, telling the agent which moves it did thus far. This
MDP M1 has non-trivial paths, but the optimal policy is
still not genuinely delayed as the two action of (s(∅)), q)

The problem of constant rewarding diameters can be
circumvented by further restricting the action set to just
A = {0, 1, q}, and instead of inputting labels, the agent
inputs bit by bit. The states are the thus-far input actions
of the agent, to ensure full observability. Non-legal inputs
(e.g. q executed where the number of input bits is not a
multiple of n) lead to subtrees where all paths are of the
same length (e.g. l × n), which revert to the ⊥ state of
the root, without reward. Such an MDP is denoted M2
and it is satisfying both the requirements of a) and b),
as the rewarding action sequence is of length n + 1. A
(partial) illustration of M2 is given in Fig. 4. To explicitly
separate oracle queries from “guesses” of the secret string
s, if the agent performs the q action at the root level,
this encodes a guess, and only a correct guess yields a
reward. This follows the construction we provided for
the Deutsch-Jozsa problem example, and in the section
V, exemplified on a different oracle problem, we will show
an alternative way of encoding guesses.

As mentioned earlier, the standard oracular formulation of the RFS setting (Eqs. (1) and (2)) have
an ambiguity when the secrets and labels come from
the same set. Specifically, the queries at the leaves
of the tree OgRF S (x1 , . . . , xl ), and the queries at
the penultimate layer of the tree (parents of leaves)
OgRF S (x1 , . . . , xl−1 , a), both have the same form. To
resolve this (purely technical) ambiguity, the last layer
accepts n + 1 actions, and the very last bit is used to
designate a leaf or a parent-of-leaf query.

More generally, given any MDP, with a large action
set, where the action set can be encoded as a sequence
of a fewer number of actions, and where the state space
is enlarged as to respond to the intermediary actions by
the elapsed action sequence (this is necessary to maintain full observability of the environment), we can always
increase the MDP’s rewarding diameter, by reducing the
action space. Observe also that the oraculization procedure constructing/simulating Eq from multiple calls to
Eacc , effectively achieves a reversed process. In this case,
the action sequences are promoted to individual actions,
which combinatorially increases the action set, the intermediary states are discarded, and, ultimately, and a
constant MDP reward radius is achieved. Both processes
we refer to as the size-depth trade-off.

Before proceeding to the last step of modification of
the MDP families to ensure the property c), it is worth
quickly confirming that the other global requirements, ii)
and iii), are maintained.

10

root 0

root ⊥
a=1

…

…

…
a=q

a=1

q11
a=1

a=1

q11...1

a=q

a=0

if O(00
0…1…0…

n

q10

a=1

000...1

…

l

q1
a=0

1) = 0

a=0

000...0

a=1

q0

rd

…

001

a=q

a=0

a
rew

000

a=q

a=1

…

a=0

01
if O(000…1) = ⊥

00

q

…

n

a=1

11) = 1

a=0

a=q

1

a=q

if O(11…

0

…

a=0

root 1

a=0

…

…

000...1...0

a=1

000...1...0......1
…

n+1

a=1

000...1...0......1...1

FIG. 4: Illustration of M DP2 . The agent has 3 possible actions at
each step, {0, 1, g}. The tree has l, n−deep sections. Each n−deep
section effectively loads the next n-bit string. The q action is used to
denote that the last sequence of n actions ends the query, effectively
specifying the input length. The labels of the directed edges encode
the criterion under which the transition occurs: e.g. a move to “root
1” occurs from some leaf if that particular query would result in the
output 1 from the oracle. Performing the “query” action at the root
level signifies that the agent will attempt to produce a guess of s. The
maximal input length is n × l + 1. The last layer accepts n + 1 actions,
as the last action resolves the ambiguity between oracular queries to
the leaves of the RFS problem, and queries to the penultimate layer
(with the appropriate guess). The only rewarding transition is given
in pink. Invalid actions (not shown) lead to irrelevant sub-trees of
maximal depth, linking back to any root state.

1.

Quantum learning using M2

First, we need to confirm that the oraculization process
can be applied, and that it helps the agent solve the MDP
optimally. The constructed MDP is not η−episodic, as
the longest path leading to a reset is of length n × l, and
the shortest is of length n.
Whether having differing (upper bounded) cycle
lengths is an issue depends on the exact specification
of the memory purging mechanism of the environment,
and the specification of the scavenging mechanism of the
agent.
However, since we are dealing with environments which
are representable by an MDP, the environmental memory need only store only the most recent state, and the
current action, and all other parts of the history may be
continuously purged.
Further, since the environment is episodic, in the sense
that the “query” action guarantees that the state occurring two steps in the future does not depend on the current state (as the query action reset the MDP to the root
level), we are guaranteed that the scavenged system that
the agent holds once it collects the root state will suffice
to end an episode (and the overall state is pure, provided
the agent submitted a pure state input 16 ).

The overall MDP-specified environment, can be constructed using only commuting Hermitian operations,
thus in a self-reversible fashion17 . Given scavenging and
hijacking capacities (at periods of n × l), this suffices for
the construction of Eq . However, given that our MDP
environments were constructed starting from unitary oracles, it should not be surprising their oraculization can,
in many cases, be further simplified.
a. Simplified oraculization A critical step of oraculization is the erasing of the environmental responses –
in general, the states the environment returns depend on
the previous actions, and in general this implies that the
corresponding registers get entangled under quantum access. To recover the original oracular form, this state information should be purged. In general, this requires the
“uncomputation” of the state information, which requires
the environmental inversion (which is possible if the environment is implemented as a large Hermitian map, which
we assume 18 ). In the constructions we used, the state
information recovered the sequence of actions the agent
utilized: if the agent performed the sequence of actions
0, 1, 1, it is in the environmental state 011 (see Fig. 4
). Note, the state information is required to render the
task environment fully observable, and for this, it would
suffice to have all the state labels unique. The choice of
the state labels collecting explicitly the path the agent
took is but one possible choice. However, it is a particularly convenient choice, as given the scavenged state of
the form
|ψscavanged i = |a1 i |s1 i |a2 i |s2 i · · · |ak i |sk i

we have that sk = a1 a2 . . . ak .. This implies that the
agent can erase the information of the state-registers by
itself, by applying a simple sequence of controlled rotations. This also implies that no environment reversal is
needed to effectuate the environment. However, as mentioned, even in the more general case where the state labels do not encode the path in any known manner (note,
since the labels must be unique to maintain observability, there is some bijection between the state labels and
paths), oraculization is possible by means of environmental reversal. However, if the state labels are exactly paths
(or the bijection is known), the oraculization can be done
without environmental reversal, which removes any assumptions on how the environmental maps are implemented.
The constructed oracle Eq is a simple extension of the
quantum RF S oracle, where the g label is used to indicate
the input length, and all other labels are ignored. The
original RFS oracle can be constructed in a black-box
fashion from Eq , hence, there exists a quantum agent,
which can simulate the access to the RFS oracle, and,
consequently, learn the only rewarding action sequence
specified by s(∅) of the underlying RFS problem using
the algorithm of [19]. Notably, the quantum agent can do
this in time O(n × l × κRF S ) where κRF S is the quantum
query complexity of the underlying RFS problem. This

17

18
16

Note, the overall input comprises all the input actions, and while
they may be entangled, the overall n-action state is pure.

(5)

Note that a unitary U is self-inverse if and only if it is Hermitian,
and a product of two Hermitian operators is Hermitian if they
commute.
Note, this is an assumption on the implementation of the environment, not its specification. All classically specified environments
admit a Hermitian implementation.

11
proves the first technical result given formally with the
following lemma.

a=1

q

a=1

a=0

q1

q0
a=0

q10

…

rd

a=1
a=1

g11...1

…1…0…

…

if O(000

…

…

Lemma 2. No classical learning agent can achieve
(poly(n)−1 , poly(n)−1 )−efficiency in poly(n) number of
interaction steps in M2 .

…

Note, this only occurs if the input was s(∅).

q11

FIG. 5: Illustration of the part of M DP3 differing from M DP2 . The
red arrow illustrates the rewarding path. The action rg causes a
random transition (with some non-extremal probabilities
0 < pi < 1, i = 1, 2 ) to a state in the first half of the rewarding path,
from any root element (just root 1 in illustration).

The two lemmas together imply our first theorem.
Theorem 1. Environments specified by MDP M2 allow a
super-polynomial separation between classical and quantum (, δ)−efficient learning agents, as long as , δ are
not super-polynomially decaying. In particular, the separation holds for constant error and failure parameters.

C.

Augmenting the MDP with a stochastic action

The MDPs constructed thus far still do not satisfy
all the criteria we had outlined earlier in Section III: in
particular, the characteristic c) is not fulfilled. Recall
that this characteristic of the MDP, amongst other consequences, requires a stochasticity of the transition function, on the relevant/rewarding part of the environmental
space.
The property c) asserts that the optimal behavior must
explicitly depend on the state label, and not just on the
interaction step counter. As we explained earlier, full determinism of an MDP necessarily violates c). Hence, we
need to modify the MDP such that the transition function
becomes stochastic. Further, stochasticity must appear
in the part of the space that must be visited by optimal agents20 . This can be achieved by a relatively simple
trick which ensures the stochasticity, while still allowing
the corresponding oraculization Eq to be realized.
This is realized with the final set of modifications yielding the final MDP M3 which we describe next.

20
19

a=1

10) = 0

a=0

…

…

a
rew

000
001
Finally, we need to see the hardness of classical learning
in the same environment. (At this point, it may be worth
while to remind the reader that l is typically chosen to
be O(log(n)) to realize instances with the most obvious
a=g
a=1
separation, thus n × l ∈ O(poly(n)).)
The proof technique we use is that of simulation,
which
000...g
000...1
is closely related to standard reduction methods. We will
provide an interface (also called a reduction), which simulates the MDP M2 from the RFS oracle, a=0
in a black-box
a=0
fashion. The interface is a poly-time algorithm, making
000...1..
the RFS oracle look like the MDP M2 , using only the
al-.0
lowed interfaces. Since we are proving classical hardness,
we can safely use the copying of the inputs, although
even that can be achieved reversibly, hence, remaining
a=g
compatible with quantum interrogation as well.
The interface is defined such that it simply returns
000...1...0......g
the current input action histories, up to the final length
l × n. It observes the sequence, identifies the actual lea=0
a=1
gal query specified by a terminating action “q” , and
if found, it inputs it into the RFS oracle, returning
000...1...0......g...1
the result, and reward if the RFS oracle’s outputs the
value b∅ .19 Otherwise it returns the ⊥ state. Note, rewards are issued only if the query corresponds to the
lowest-level query, that is to the guessing of s(∅). Now,
if there is a learning agent/algorithm that learns the
MDP M2 in time n × l × T, then the composition of
this agent/algorithm with the above specified interface
is a classical algorithm that solves the RFS problem
in time T . Since there is a super-polynomial separation between the minimal possible T and κRF S , there
must be a super-polynomial separation between the quantum, and any classical agent in learning efficiency. In
other words, any (poly(n)−1 , poly(n)−1 )−efficient classical learning agent requires at least n−log(n) steps, whereas
the quantum agent attains the same efficiency (in fact,
(1, 1 − O(exp(−n)) efficiency) in nO(1) steps.
To elaborate on the error, and failure probability, note
that only the single n−bit sequence of s(∅) leads to the reward. If both the error and failure probability are at most
polynomially small, polynomial repetition of the process
will identify s(∅) with constant probability (and by further repetition, exponentially small failure probability).
Since the rewarding path can be checked deterministically, if there exists a classical agent A with only polynomially small error and failure terms, then there exists
a classical agent A0 with exponentially small failure and
zero error terms, which achieves this performance in at
most a polynomially larger number of interaction steps
relative to A, via simple iteration by the Chernoff bound.
We have that

p2

a=g

…

11) = 1

…

01
a=g

p1

1

…

00
a=0M2
Hardness of classical learning in
a=1

a=r g

a=g

a=1

2.

root 1

…

root 0

if O(11…

Lemma 1. The l × n−episodic MDP M2 allows oracroot ⊥
ulization, and a quantum learning agent can learn the optimal policy in expected time O(poly(κRF S )), where κa=0
RF S
is the quantum query complexity of the underlying gener0 a=g
alized RFS problem.
a=0

Without demanding this, we could easily introduce stochastic regions to an MDP which is never visited by the agent, which is a
trivial, yet uninteresting solution.

12
Recall for the moment the structure of the MDP M2 (in
Fig 4), where all the paths are of length n×l,21 and where
all rewarding action paths contain s(∅) as the prefix.22
We will refer to this unique sequence of percept-actions as
the rewarding prefix. Next, for simplicity assume that the
rewarding prefix length n is even, and consider the first
half of the rewarding prefix – the rewarding half-prefix,
which is of length n/2. We will further expand the action
space of the agent, by adding a rg (“random & guess”)
option, which can be advantageously invoked only when
paired with the very first bit23 , that is, when the agent
is at a root state of the MDP. For intuition purposes,
we imagine that the agent separately announces guess
options, however, recall that they are actually combined
with the bit-specification to ensure uniform path length.
M3 is defined such that, if the agent invokes the rg option
at a root state, the subsequent environmental state is
randomly chosen from any of the states appearing in the
half-prefix.
Note that the optimal course of action for any agent
is to always invoke the random option, as it, on average, shortens the rewarding sequence by n/4. However,
it is not known beforehand to which position in the rewarding half-path the transition will lead, meaning the
optimal agent cannot simply blindly output the rewarding sequence. It is thus forced to learn the full optimal
policy specification for the first half of the path. Note
that the agent, irrespective of the position in the halfpath the jump lead to, still needs to exactly reproduce at
least the second half of the rewarding sequence.
At this point, we can describe the quantum agent which
learn in the MDP M3 . We call this agent A3 , and we will
prove its efficiency shortly. Its behavior has three stages.
In the first stage the agent uses oraculization techniques
to effectuate/simulate access to the RFS-type oracle, using which it can effectively run the quantum algorithm
for RFS, in order to learn s(∅). In the second stage, the
agent uses classical access, and blindly executes actions as
prescribed by the string s(∅) step-by-step, and collect the
labels of the states of the MDP along the rewarding path.
Note, these labels were not available in the oraculized instantiation (in fact, one of the key steps of the oraculization procedure is the uncomputation, or deletion of the
state labels). In the final, third stage, having learned the
correct state-action association along the rewarding path,
the agent invokes the randomized short-cut option: first
use the rg action to jump through the first r steps along
the rewarding path (for some random 0 ≤ r ≤ n/2), then
figure out r by looking at the label of the current state
of the MDP, then input the remaining n − r bits of s(∅),
and obtain a reward, in minimal number of steps.
For completeness we mention that the performance of
the agent is technically evaluated via a tester, which if not
chosen carefully could break any entanglement between
the agent and environment (see [16, 17] for details). In

21
22

23

This was enforced by introducing additional ancillary paths which
lead to no-rewards, which ensures strict episodicity.
Recall, in the non-extended MDP, performing the n actions on the
rewarding path leads to a re-set. In the strictly episodic variant,
the agent still has to perform n × (l − 1) moves before the episode
ends, but the choice of moves after the rewarding path does not
matter, as all are rewarded.
If the agent performs this action at any other position, it is led to
a non-rewarding tail of the MDP.

the quantum stages, the interaction is thus left untested,
and then fully classically tested in the classical phases, as
was done in [17].
To obtain the central result of this paper, we still need
to tie up two loose ends which were comparatively simple
for the cases of environments specified by the deterministic MDP M2 . First, we must make sure a quantum agent
can learn in M3 in a polynomial number of interaction
steps. To prove this, we need to ensure that the oraculization methods can still be applied in the case of the
environments which encode M3 – note, the transitions
of optimal behavior now includes stochastic transitions.
Although here we consider only the environments specified by M3 , the arguments we will use are more broadly
applicable.
Finally, we must ensure that the learning in the constructed MDP M3 is still hard for the classical agent.
This is not trivial. Recall, the classical hardness of learning in MDP M2 is easily implied from the classical hardness of the RFS problem. However MDP M3 , which is
modified from M2 , allows options for the classical agent
which do not trivially map to the underlying RFS task.
1.

Efficient quantum learning in MDPs with generic
properties

We first focus on the particular case of the MDPs of the
type M3 , to show they still allow a consistent oraculization approach. Note, intuitively, there could be a problem in these types of environments because the rg move is
stochastic and irreversible. Consequently, it is not clear
how the quantum environment implements this action.
However, in our case, this actually causes no issues as
the quantum agent A3 never needs to perform quantum
superpositions and rg moves simultaneously. Whenever
it does an rg move, it is a classical move (not a superposition). In more formal terms, we have the following properties of M3 . Given an MDP M , and a subset of actions
A0 ⊆ A, with M|A0 we denote the sub-MDP effectuated if
the agent is restricted to using only the actions in A0 . In
the case of M3 we have that M3|A\{rg} = M2 . In other
words, an agent which never uses the randomized guess is
effectively in an environment M2 , which is deterministic.
But in this case, all the oraculization constructions introduced for deterministic cases [17] can again be applied.
This we formulate as the following broadly phrased
Lemma.
Lemma 3. Let M be an MDP specifying a controllable
task environment (i.e., a task environment allowing appropriate quantum access). Further, let M be such that
it has a deterministic sub-MDP M 0 with the following
two properties: i) having access to a (representation of a)
policy which is (−)optimal for M 0 , allows the efficient
learning in M , and ii) there exists a quantum learning
agent A0 which can learn in M 0 efficiently, using standard (or simplified) oraculization methods . Then there
exists a quantum learning agent A which learns efficiently
in M .
Proof. The quantum agent A, which efficiently learns in
M , first uses a quantum learning agent A0 to learn the
(−)optimal policy for M 0 . Such an agent A0 exists by
criterion ii). This trained agent A0 , or rather, the policy
it represents, is the desired representation appearing in
criterion i). By the same criterion, there exists a behavior

13
which leads to efficient learning in M , and A behaves
accordingly.
To make the broad lemma above more concrete, we can
focus on the specific environments we consider in this paper. The sub-MDP M 0 of M3 in question is exactly M2 .
An agent A0 trained to perform with maximal efficiency
in M2 also knows how to navigate the rewarding prefix
M3 (and also “knows” the secret string s(∅) of the underlying RFS problem). An agent A, which has access to
(a simulation of) A0 can simply invoke the randomized
option rg, and from that point on froward the percepts
and actions between the environment and the simulation
A0 which will perform optimally on any part of the rewarding prefix. Such A is an optimal agent. Thus, we
only need a quantum agent A0 to learn how to solve M2 ,
understood as a sub-MDP of M3 realized by restricting
the actions in M3 (concretely, by not allowing the option
rg). This agent is then “called” by A3 to achieve optimal
performance in M3 , by employing the option rg as often
as possible.
It should be highlighted that if the agent applies the
constructions, and inputs the action leading beyond the
deterministic sub-MDP (such as the rg action), the procedure in general breaks: there are no guarantees in the
construction on what happens in this case. However, we
can always define agents which do not employ such behavior.
We note that certain types of randomized environments, where stochasticity cannot be at all influenced by
the agent, can also be beneficially quantized – such constructions may allow further generalizations of M DP3 ,
where random moves occur no matter what the agent
does. We leave this for future work. Lemma 3 established a relatively generic statement, which in combination with the constructions of previous sections shows
how to find environments which have interesting desired
properties a) − c), while still allowing efficient quantum
learning agents. However, as mentioned earlier, whether
or not the realized MDPs are still difficult for classical
agents depends on the details of the constructions. In the
last part of the paper, we prove the classical hardness of
learning specifically in M3 , thereby proving the existence
of environments with a super-polynomial separation for
quantum RL.
2.

Hardness of classical learning using M3

While the classical hardness of learning of M2 was easily implied by the classical hardness of the RFS problem,
the modification added to M3 gives the classical agent
an option which was not available before. It is easy to
see the agent can use this to obtain clearly useful information about the winning path. By using the random
jumps, since the state labels specify the correct rewarding path up to the state reached by the random transition, the classical agent can, for instance, in O(poly(n))
steps the classical agent end up in the very last state
of the half-path. This reveals all the moves leading to
this point. While learning the rewarding path can be

made more convoluted for the agent by permuting the
labels (we only need unique labels for the purpose of observability of the MDP), the agent can still build up the
connectivity map on the path in O(n2 ) queries.
However, as it turns out, even this modification is
not necessary to prove classical hardness of learning in
M3 . We first show an intuitive fact that solving a randomly chosen RFS problem where the prefix is additionally leaked cannot be easier than solving an RFS problem
of half the size. This will allow us to prove the main results using one last simple lemma showing that learning
in M3 is harder than learning in M2 with additional access to the half-prefix.
For technical reasons, we will only consider RFS problems where the function f is the standard inner product.
This somewhat restricts the class of all MDPs our results
could be applied to as, in principle any generalized RFS
(as defined in [19]) could yield a distinct class of MDPs,
but it drastically simplifies the arguments needed for for
Lemma 4. We discuss the possible generalizations in the
Discussion section.
We begin by first clarify the notation and define a few
useful concepts..
First, without loss of generality we assume all the labels
of RFS problems are strings of n bits. Next, with RF S(n)
we denote the family of all such RFS problems with n−bit
labels. Note, an instance of RF S(n) is fully specified by
the function s.
Any algorithm which which uses queries to an unknown
RF S(n) oracle (specified by the function s) to simulate
access to another oracle of a problem in RF S(2n) (with
some other, higher dimensional secret function s0 ) with
the property that s(∅) is a suffix of s0 (∅) is called a lifting
of RF S(n), and the realized larger instance RFS problem
RF S(2n), is called the lifted RFS problem.
The basic idea here is to show that smaller RFS instances can be black-box embedded in larger instances.
This will imply that if one can solve a larger instance if
information about the embedding part is leaked, then one
can also solve the input and unknown smaller instance,
thereby proving the hardness even under leaking of information. Any such construction which constructs an
instance of RF S(2n) compatible with a given RF S(n)
we call a lifting construction. Next, we provide a particular simple lifting construction, which is suitable for
standard RFS problems, and which is based on concatenation.
a. Concatenated lifting construction Given access to
an oracle for one RF S(n), we first choose a full specification of another RFS problem of the same size. Let s
be the (unknown) secret function of the first RFS, and
p be the (fully known) function of the chosen ancillary
RFS. Given a 2n-bit string x, with pref(x) we mean the
first n−bits of x, and with suff(x) we denote the n−bit
suffix. Thus x = pref(x)suff(x) = pref(x) ◦ suff(x), where
◦ denotes concatenation (we may omit this symbol when
there is no danger of confusion).
The secret function s0 of the “glued” RF S(2n) is given
as follows

s0 (x1 , x2 , . . . xk ) = p(pref(x1 ), pref(x2 ), . . . , pref(xk )) ◦ s(suff(x1 ), suff(x2 ), . . . , suff(xk )).

(6)

14
This construction works naturally with the inner product
as f , as f (x, y) = f (pref(x), pref(y)) ⊕ f (suff(x), suff(y)).
In other words, we are dealing with two RF S(n) effectively in parallel, with minimal coupling between the
subspaces. It is clear this is a valid construction of 2n−bit
RFS instances.
b. Uniform lifting The concatenated construction
lifts an n-bit instance to a 2n-bit instance of RFS, however, not all 2n-bit instances of RFS can be realized in
this way. Since we wish to show that learning in M3 is
hard in the average case, we also need to show that the
capacity to solve an average 2n-bit RFS with access to the
leaked part of the winning sequence is hard. To be able
to prove this using the lifting arguments, it is necessary
to provide a lifting construction which can realize any 2nbit RFS instance, given an appropriate n−sized instance.
The instance we capture with the bare concatenated constructions are only those with such a product form, and of
course not all instance factorize in this manner. A lifting
procedure which allows the construction of any RF S(2n)
compatible with a given RF S(n) we call a uniform lifting procedure. Here, we show a method on how the
lifting construction can be altered to simulate access to
another oracle in RF S(2n), such that the modified effective function s00 deviates from s0 in the value it attains at
any chosen path-label by any chosen string of bits. More
specifically, if we chose a path-label (element of domain of
s0 and s00 ) x, and a 2n-bit string d, we construct an oracle
specified by s00 such that s0 (x) ⊕pw s00 (x) = d, where ⊕pw
is point-wise mod-2 addition. This is done in a way that
ensures that the root values remain compatible with the
initial RF S(n) in the suffix. Moreover, we show that such
modifications can be applied sequentially in any order any
number of times. Since we can do this for any chosen vector d, and for any set of chosen domain elements x, this
means we can realize any element of RF S(2n) compatible with the given, unknown instance of RF S(n). The

provided construction uniformly covers the space of lifted
RF S(2n) problems, as any can be reached starting from
any compatible smaller-instance RFS.
Our basic idea is thus to “twirl” the input output relations, on elements of the domain of s0 in a black-box
fashion: each 2n-bit secret is randomized, by bitwise xoring it with a 2n-bit shift, which is chosen independently
at random. This new 2n-bit RFS oracle can be simulated
using the original n-bit RFS oracles, due to bilinearity of
f . In more detail, we need to show how a “twirl” can be
effectuated in the actions of the oracle.
Consider any input x = (x1 . . . xk ) for 2 < k < l,
and let s0 (x) = z, where z is a 2n-bit string. Note
that the function s0 evaluated on (x1 , . . . xk ) appears in
two capacities in an RFS problem. One is a queryvalidity criterion in a call to the oracle of the form
(x1 , . . . xk , a), where a is a 2n-bit string. More precisely
we have that O2n (x1 , . . . xk , ak ) = f (s0 (x1 , . . . xk−1 ), xk )
if s0 (x1 , . . . xk ) = a), thus we need to change the
evaluation of the criterion s0 (x1 , . . . xk ) = a). The
second, inner-product occurrence of the evaluation of
s0 couples the levels of the RFS-tree, where we have
that O2n (x1 , . . . , xk , xk+1 , a) = f (s0 (x1 , . . . , xk ), xk+1 ) if
s0 (x1 , . . . xk+1 ) = a.
Note that we only wish to change the value s attains on
the one query sequence x. Thus, the simulator, interfacing
with the oracle we have, and effectuating an oracle with
hidden function s00 , with altered values on x need only
act non-trivially when queries are of one of the two forms
above. If it identifies we are in the setting of a queryvalidity criterion, we wish we could effectuate the test
s0 (x1 , . . . xk ) ⊕pw z = a.

However, due to the concatenated construction, this simplifies to

s0 (x1 , . . . xk ) ⊕pw z = a ⇔ p(pref(x1 ), . . . pref(xk ))s(suff(x1 ), . . . suff(xk )) = a ⊕pw z ⇔
p(pref(x1 ), . . . , pref(xk )) = pref(a ⊕pw z) && s(suff(x1 ), . . . , suff(xk )) = suff(a ⊕pw z).

Note that the first criterion above we can easily evaluate
as it only depends on the known inputs, and a chosen
instance of RF S(n). The second, however, can also be
checked by querying the other, unknown RF S(n) oracle
by inputting only suffixes of the query, and xor-ing the last
string with suff(a). In other words, to decide a rejection of
input, the simulator checks the two criteria, one of which
requires one call to the unknown oracle of RF S(n).
What remains is understanding what the simulator
needs to do in the case of an inner product occurrence. We proceed analogously. We wish to effectuate
O2n (x1 , . . . , xk , xk+1 , a) = f (s0 (x1 , . . . , xk ) ⊕ d, xk+1 ) if
s0 (x1 , . . . xk+1 ) = a. Note that the validity criterion requires no modification. To evaluate f (s0 (x1 , . . . , xk ) ⊕pw
d, xk+1 ) we have that, by distributivity:

(7)

(8)
(9)

Thus the simulator can effectuate an RF S(2n) with the
underlying labeling function s00 using only access to an
(effective) oracle realizing the functions s and p. Note also
that s00 differs from s0 in any chosen domain value, where
it can attain any possible label. However, to maintain
compatibility of the output, we should not alter the values
at the root, even though such alterations could be decoded
as well, if needed.
Note that the alterations of the type above can easily
be “stacked”, or composed as the occurrences are independent. This means that any labeling function can be obtained, which allows us to achieve uniform sampling over
RF S(2n). This implies the following lemma:

Lemma 4. There exists a uniform lifting procedure which
can, given black-box access to an instance R of RF S(n)
f (s0 (x1 , . . . , xk ) ⊕pw d, xk+1 ) =
with secret string s(∅), generate all instances of RF S(2n)
0
f (s0 (x1 , . . . , xk ), xk+1 ) ⊕ f (d, xk+1 ).
(10) such that the secret string s (∅) of the generated sequences
contains s(∅) as the suffix.
In other words, the simulator need only xor the output (if
In particular, this implies that given uniform distributhe instance passed the validity criterion) with the value
f (d, xk+1 ), which it can easily do.
tion over black-box input instances, we can construct a

15
uniformly distributed instance from the set RF S(2n).
Next, we show that the existence of such a uniform lifting construction implies that solving RF S(n) is still hard
for the classical agent, even in the full information about
the prefix of the secret string s(∅) is leaked, also in the
average case.

same simulation constructions we have given in the proof
of Lemma 2 (which precede the statement of the lemma),
it follows that an efficient agent learning M2 given half of
the winning prefix implies that the corresponding “leaky”
RF S(n) can be solved as well, which is not possible. This
concludes the proof.

Lemma 5. If there exists a construction which uniformly
covers the space of lifted RF S(2n) problems, then solving a
random instance of RF S(2n) given additional information
about the half-prefix cannot be done more efficiently than
solving a random (or a worst case) instance of RF S(n).

Combining the results of classical hardness of learning
in M3 , with the previously established results showing how
efficient quantum learning agents can be constructed for
an broader class of environments in Section IV C 1, we
have our main theorem:

Proof. Suppose there is a construction as in the statement
of the theorem, and an algorithm P which solves a random
RF S(2n) in time T , given side information about the halfprefix. Then given a random instance of RF S(n) we construct a uniform sample from RF S(2n) compatible with
the smaller instance using the construction above. Denote
the secret string of the smaller instance s(∅), where the
secretes of larger instances are denoted with s0 (∅). Note,
the construction need not be efficient, only computable,
as we only care about query complexity. The construction
will realize some RF S(2n) with a known prefix. Since the
small instance was uniformly sampled and since the construction generates an uniform sample from the compatible class, the output instance of the RF S(2n) also from
a uniform distribution. This valid input instance is, along
with the side information about the prefix, fed into P , and
the output is collected. The suffix of the output is, by construction, the solution of the smaller instance. Note, the
only compatibility constraint we maintain is the values of
the suffix of s(∅) of the larger instance, and this is the only
property we maintain from the small instance. However,
even this can be modified by a chosen deviation string d
(see details of construction later) – i.e. we can construct
an instance of RF S(2n) with the only constraint that the
suffix of s0 (∅) is equal to s(∅) ⊕pw d, for any d. That is we
can generate any instance of RF S(2n), and by obtaining
the solution to this instance, recover the solution to the
smaller instance. This means that we can also drop the
assumption on the uniformity of the small instance, and
the claim holds for the worst case as well.

Theorem 2. Environments specified by MDP M3 allow
a super-polynomial separation between classical and quantum (, δ)−efficient learning agents, as long as , δ are not
super-polynomially decaying. In particular, the separation
holds for constant error and failure parameters. Finally
M3 satisfies all three criteria a)−c) for MDPs with generic
properties.

Now we can prove the classical hardness of learning in
M3 .
Lemma 6. No classical learning agent can achieve
(poly(n)−1 , poly(n)−1 )−efficiency in poly(n) number of
interaction steps in M3 .
Proof. First, note that if learning in M2 , in the
setting where the agent is given prior information
about the half-prefix of the winning path is hard
(i.e. (poly(n)−1 , poly(n)−1 )−efficiency is not attainable in
poly(n) time for any classical agent), then learning in M3
is hard as well. To see this note that knowing the prefix
of M2 allows the agent to black-box simulate the corresponding M3 from M2 , by randomly choosing a position
in the winning prefix in M2 , and deterministically moving
to that point. Hence, the existence of an efficient agent
for M3 with leak implies the existence of an an efficient
agent for M2 with information about the prefix.
What remains to be seen is that learning in M2 is
hard even when the prefix is leaked. Lemma 5, along
with (the existence of) the uniform lifting construction
implies that the solving of RF S(n), when half of the secret string is leaked is still classically hard. Then, by the

Proof. The theorem follows from the proof of classical
hardness of M3 in Lemma 6, and the existence of a quantum agent which can efficiently learn in M3 , which is implied by Lemma 3. In essence, the latter relied on the
possibility of applying oraculization techniques to instantiate Eq which is, on the relevant subspace, equal to the
standard RF S oracle, the existence of the efficient quantum algorithm for RFS, which reveals the entire string
s(∅). The fact that M3 satisfies all three criteria a) − c)
holds by construction.
3.

Hierarchical learning and recursive problems

Textbook RL tasks deal with MDP environments, and
problems like optimizing return in the infinite or finite
horizons, on a more abstract level. However, aside from
learning how to solve the local problem, intelligent agents
are expected to also exploit previous experiences in future
situations. One aspect of this is a form of generalization,
where agents trained to solve some problem E should have
an advantage in a similar problem E 0 , relative to an untrained agent. While the possibility for such generalization
critically depends on the notion of “similarity”, one way of
understanding a key feature of generalization is in a type
of information carry-over: optimizing in E provides the
agent with useful information for solving E 0 . The proposals which achieve a quantum speed-up in [17] and also in
this work, can be seen as examples of this paradigm: the
quantum agent accesses a (simplified quantum) environment Eq to learn a key needed for optimal performance in
the full environment. One can generalize this, and imag(k)
ine a cascade of problems {Ak }, where solving of any
task k requires (or is simply significantly mitigated) the
solution of k − 1. In natural learning settings, an example
of this is for instance hierarchical skill learning [36], where
an agent is trained in simpler skills, which are later used
as primitives for more complex tasks – beyond robotics,
this is also how biological agents learn.
The standard RFS problem itself has a flavour of such
hierarchical learning: it is a recursive problem, where the
queries to lower-level instances are locked by the solutions
of higher-level instances (in the RFS tree)24 . At the same

24

Specifically, each RFS tree of depth n, with n-bit labels encodes

16
time, unlocking the secret of a higher-level does not actually help in the unlocking of the secrets of the lower-level
instances. Note, if it were the case that the secrets between layers share known correlations, the problem would
likely have a more efficient classical solution, which utilizes the learned secret strings. On the other hand, the
quantum algorithm does rely on certain consistency criteria (the secrets of the higher level unlock the oracles of the
lower), but not on any correlations between secrets of the
layers.
In a sense, the RFS problem may constitute an example of hierarchical learning suitable for quantum learners,
but not for classical learners. We plan on exploring this
possibility, and its relevance for the theory of (quantum)
RL further in subsequent works.
With this, we move
onto the next example, where the underlying oracle does
not have a recursive structure, and the “secret” is hidden
in the global properties of the underlying MDP, based on
the Simon’s problem.
V. EXPONENTIAL SPEED-UPS:
CONSTRUCTIONS FROM SIMON’S PROBLEM

The constructions of the previous section exemplified
how oracular problems, which have a provable classical/quantum separation can be lifted to reinforcement
learning separations. The last example focused on recursive Fourier sampling, due to its recursive structure which
may match structures appearing in (more) realistic RL
scenarios. RFS has a provable super-polynomial separation, but it has also been shown that there is no straightforward way to enhance the gap to a full exponential difference [37]. However, essentially any oracular problem
which conceals a secret bit-string can be raised to the RL
setting using more-or-less the same constructions. In this
section we show how this is done for the case of Simon’s
problem [20], which admits a true exponential separation,
and which we detailed in section II C 2.
A.

MDP encoding Simon’s problem

Recall, in Simon’s construction, we are given an oracle encoding a function f : {0, 1}n → {0, 1}n , with the
promise that there exists a secret string s ∈ {0, 1}n , such
that f (x) = f (y) if and only if x = y ⊕ s, where ⊕ is the
element-wise modulo 2 addition.
Using the same constructions as in Section IV B, the basic deterministic MDP encoding Simon’s oracle f is given
as follows. First, we have the set of “zeroth-layer” states,
which encode the output of the oracle. Second, a binary
tree, of depth n − 1 encoding the “loading of the query”
the agent performs, up to the very last bit of the query.
Each state of the tree is uniquely labeled, e.g., by collecting the path leading to each query state. The leaves of the

tree encode (n − 1) bits of the query, and the last action
encodes the very last bit, which causes a transition to the
zeroth-layer states, specifically, to the state encoding the
output of the oracle, given the query.
In previous constructions, the possible actions included
“query actions” and a special action designating the agent
is inputting a guess of the secret string. For the case of
Simon’s problem, this is actually not needed. The set of
actions is given by just the set A = {0, 1}, and each query
is simultaneously interpreted as a guess as well. Specifically, the constructed MDP allows one rewarding edge,
the one leading from the path designated by the first n − 1
bits of the hidden string s, and which is realized by the
very final bit of s.
This MDP is illustrated in Fig. 6.
Note, in the example of the RFS and Deutsch-Jozsa
MDPs, we have for simplicity, separated the guess from
the query. However, this is in most cases not necessary:
one can encode the guess in the query itself, as we do for
the Simon’s example, yiedling a reward if the query is also
a correct guess. However, one must be careful that this
does not yield a different, simpler problem, as we elaborate
next.
The structure of Simon’s promise (f (x) = f (y) if and
only if x = y ⊕ s) is encoded in the edges leading from the
children of the inputting tree, to the zeroth-layer states
which encode the 2n−1 distinct possible output states of
the oracle: two leaf states lead to the same zeroth-layer
states, if the corresponding paths differ by the sting s. If
the function f is a permutation (so s is all-zeroes), we have
2n states in the zeroth-layer, but for the moment we do
not consider this case.
In the language of MDPs, the secret is encoded in the
global structure of the graph, revealed by the point-wise
difference between any two paths which lead to the same
final (root) state.
If one follows the constructions of previous section,
where the constructed MDP is equipped with explicitly
“perform query” options, then it is obvious that the encoding is fully faithful, and learning in the MDP corresponds
exactly to solving Simon’s problem. However, it is more
interesting and natural to encode the query and guess in
the same structure, by rewarding the query input which
corresponds to s, as we described above. Such an MDP
encodes a slightly different function, which outputs a flag,
if the query is actually equal to s. More formally, it encodes the function f 0 : {0, 1}n × {0, 1} → {0, 1}n × {0, 1},
where
f 0 (x, b) = (f (x), b ⊕ δx,s ),

(11)

where f is some standard Simon’s problem function.25 We
call this modified problem flagged Simon’s problem.
It should be clear that learning s cannot be easier given
access to f 0 , relative to f . We prove it formally for completeness. We assume that s 6= 0 . . . 0.
Lemma 7. Flagged Simon’s problem has an exponential
classical lower bound.

smaller-instance RFS problems. The smaller instance-tree is a
sub-tree of the overall graph. A corresponding sub-tree can be
realized as follows. First, the last layer is dropped. Second, starting from the root, we choose a bit, and identify all children whose
label does not end with the chosen bit – those nodes, along with
their sub-trees, are dropped. This is iterated on each remaining
node, sequentially through the layers. What remains is tree for
RFS problem over (n − 1)-bit labels.

Proof. We again prove this via simulation. Note that given
access to Simon’s oracle, we can easily check whether some
given string x matches the secret string s. One simply

25

In other words, the ancillary bit is flipped if the query is s.

17

}

n bits
000...00

000...01

000...10
a=1

a=1

a=1

…

111...11

a=0

a=0

a=1
a=0 a=0

0

a=0

a=1

a=1

101...0

000...1

101...1

= 101…1…10

101

…

…

000...0

100

11

a=1

if f(101…1…10) = 00…01

a=0

10
a=0

and rewarding if s

…

n-1

a=1

…

…

001

= 00…01

a=1

if f(000…1…01)

01
…

000

a=0

…

00
a=0

1

a=1

…

a=0

a=0

000...0

a=0

a=1

000...1...0

a=1

101...00

a=1

a=0

101...1...1

}

(n-1) bits
FIG. 6: Illustration of MSP . In the deterministic case, the agent has 2 possible actions at each step, {0, 1}. The actions form a tree of depth
n − 1, the last action causes a transition back to the zeroth layer. The path of n moves encodes the input to the Simon’s oracle, and the resulting
state of the zeroth layer the output. Each path is also interpreted as a “guess”, and if the agent inputs s, the resulting transition is rewarded. The
winning path, and rewarding transition are highlighted in red and pink. The inset figure presents the randomized version which allows the agent
to land on a random element of the half-prefix of the winning path from any zero-layer state (state “all-ones” in illustration).

queries Simon’s oracle on two points t and t ⊕ x, and
checks whether the output is the same. Suppose now that
we have an algorithm A which finds s for the flagged Simon’s problem, under the promise that s 6= 0 . . . 0, using
T queries. Now, given an oracle for the (original) Simon’s
problem, we use the algorithm A, and introduce a simulator, which for each query of A outputs the value f (x) (by
direct query to the Simon’s oracle), and performs a check
if x = s as described earlier. After T queries given by
A (and 2T queries actually performed by the simulator),
if s 6= 0 . . . 0, then one of the checks confirmed a query
by assumption of correctness of A. If not, we output the
guess that s = 0 . . . 0. This proves that there cannot be an
algorithm which learns the secret s of the flagged Simon’s
problem in T ∈ O(2n/2−1 ) steps with zero-error.
For the case of randomized algorithms which can err,
assume A outputs the correct string with polynomially
bounded failure probability p. The process we described
for the deterministic error-free case is repeated c times. If
all fail, we output s = 0 . . . 0. The probability of this being
incorrect is pc . Since 1 − p is at most polynomially decaying in n, overall we have that flagged Simon’s problem
does not allow a randomized algorithm which identifies s
with polynomially bounded error probability, using fewer
queries than Ω(2n/2−1 /poly(n)).
One can use similar arguments to show that learning s
in the flagged Simon’s problem has an exponential classical lower bound also when s can be “all-zeroes”, but one
has to be a bit careful how the simulator is defined given
the input of all-zeroes, and how the analysis treats this
case. In this case, the simulator cannot perform an effi-

cient check, and the simulated oracle is either undefined,
or the output is not guaranteed to be correct. This is
not critical in the case of classical algorithms, as any algorithm which utilizes less than exponentially many queries
has, on average, only an exponentially small chance of
querying all-zeroes 26 . If the classical algorithm errs with
polynomially bounded failure probability given access to
a perfect oracle, then given access to an oracle which errs
only on one input, the overall success probability cannot
differ by more than an exponentially small amount, unless
the total query number is exponential.
Lemma 7 also implies that learning in the deterministic encoding of the MDP cannot be done using less than
exponentially many interaction steps in the classical case.
For completeness, we point out that whenever the oracular problem itself allows the verification of the secret,
encoding the guess in the query is never a problem. The
gRFS problem, as considered in [19] does have an explicit
verification mechanism (the query of length n returns ⊥
unless it is the secret), thus also for the case of RFS MDPs
it is possible to encode the guess in the query.

26

No particular string has any special role in any reasonable algorithm. If the algorithm A finds s in average case scenarios, then
we can simply compose the oracle with a fixed permutation which
shifts all-zeroes to some other string. By assumption this modification still leads to the same average success probability of the
algorithm A. However, now we have uniformly shifted the all-zero
string in the bit-string space.

18
Simon’s problem, with s = s0 ◦ s1 . To uniformize the construction, by Lemma 8 it will suffice to compose f with a
Continuing with the construction of the MDP based on uniformly chosen permutation of the size 2n, which generSimon’s problem, we will next provide a randomized ac- ates a uniformly chosen 2n- sized instance with the secret
tion for the agent. Here we use the same approach as in string s.
Section IV C. This will guarantee all the required “generic”
By combining the hardness of Simon’s problem with
properties of the MDP described in Section III. The action
leak with the reduction in the proof of Lemma 7 showspace is augmented to contain the random-jump action rg,
ing the hardness of the flagged variant, we analogously
which lands the agent at a random state, somewhere in the
get the hardness of the flagged version under leak.
first half of the query specified by the secret s. This MDP,
specific to an instance of flagged Simon’s problem, we will Lemma 10. Flagged Simon’s problem has an exponential
denote MSP (see Figure 6).
classical lower bound, even if half of the secret shift is
The proofs of classical lower bounds, and quantum up- provided.
per bounds for learning in this setting are even simpler
This implies the classical hardness of learning in MSP .
than for the case of constructions based on the RF S problem.
classical learning agent which can
a. Classical lower bound In complete analogy for the Corollary 1. Any
−1
−1
achieve
(poly(n)
,
poly(n)
)−efficiency requires at least
lower bounds proof for the randomized version of the
n/4
O(2
/poly(n))
interaction
steps
in MSP .
RF S−induced MDPs, we only need to prove that solving the (flagged) Simon’s problem given access to the fist
To prove this one uses the same simulators as in the
half of the secret s cannot be (radically) easier than the
previous section.
problem without this information leak.
b. Quantum upper bound We consider a learning
We again prove this by embedding an n−size instance
agent that has quantum access to an environment that
into a 2n instance, followed by a uniformization procedure,
realizes the above MDP. The agent will employ the same
which ensures average case hardness. We begin with a
strategy as in the case of the RFS-family problems. First,
technical claim regarding the relationship of two functions
it will attempt to use the standard oraculization techsatisfying Simon’s promise with the same shift.
niques to simulate the oracle for Simon’s problem. In the
Lemma 8. Let f and g be two n − bit functions, both case of MSP , we again do not need to use the randomized
satisfying Simon’s promise with the same n−bit string s. rg action at this stage. Instead, we simply use oraculizaThen there exists a permutation h ∈ {0, 1}n → {0, 1}n tion to simulate the quantum flagged Simon’s problem orsuch that f (x) = h(g(x)). Conversely, if there exists a acle, and then run Simon’s algorithm to learn s.
Note,
the quantum flagged Simon’s probpermutation h such that f (x) = h(g(x)) and g is satisfying
lem
oracle
realizes the mapping |xi |yi |biAnc →
Simon’s promise with the n−bit string s, then so is f .
|xi |y ⊕ f (x)i |b ⊕ δx,s iAnc . In other words, it acts
Proof. If either of the functions f or g are permutations, also on the ancillary register, flipping the bit, if the query
then both directions are trivial (e.g. h(x) = f (g −1 (x))).
is the secret string – this arises from the reward function.
Suppose f and g satisfy Simon’s problem with the same However, by setting the relevant reward-specifying
√ regshift s. Then f and g act as constants on the same pairs ister into the bit-flip invariant state (|0i + |1i)/ 2 (see
of input bit-strings, as
pg. 31 in[16] for details), we realize the original Simon’s
f (x) = f (y) ⇔ x = s ⊕ y ⇔ g(x) = g(y).
(12) oracle, allowing the standard algorithm to be applied.
As explained in section II C 2, there are multiple options
They can only differ in what values are attained for each for quantum algorithms to recover s using a polynomial
pair, that is, by a permutation on the equivalency class number of interaction steps [20, 38].
xỹ ⇔ x = s ⊕ y. This is the permutation h.
Finally, once s has been learned via quantum access,
To prove the converse, note that since h is a permu- the agent will then seek to extract rewards from the entation, so injective and invertible, we have that f (x) = vironment. To do this, it behaves classically, and utilizes
f (y) ⇔ h−1 (f (x)) = h−1 (f (y)). But then
the randomized rg action, in order to reduce the number
of steps needed to extract a reward.
−1
−1
f (x) = f (y) ⇔ h (f (x)) = h (f (y))
Putting all the above observations for the lower and
⇔ h−1 (h(g(x))) = h−1 (h(g(x)))
upper bounds together, we get our final theorem.
⇔ g(x) = g(y) ⇔ x = s ⊕ y.
(13)
Theorem 3. Environments specified by MDP MSP allow an exponential separation between classical and quanNow we can prove the hardness of Simon’s problem with tum (, δ)−efficient learning agents, as long as , δ are not
super-polynomially decaying. In particular, the separation
information leak.
holds for constant error and failure parameters. Finally
Lemma 9. The Simon’s problem of size 2n, where the MSP satisfies all three criteria a) − c) for MDPs with
oracle additionally leaks the first half of the string s has generic properties.
classical query complexity lower bound of Ω(2n/2 ).
Regarding the oraculization properties, the same disProof. Let f1 be the function corresponding to an n−sized cussion we provided in section IV B 1 a applies. Since the
instance of the Simon’s problem, with secret string s1 . MDP stems from a unitary oracle, provided the state laTo raise this to an 2n- sized instance, we choose another bels are specified by action paths using a known funcn−sized instance with the (known) function f0 and string tion (or, they simply explicitly denote the path leading to
s0 , and define the concatenated function f (x0 ◦ x1 ) = them), oraculization can be simplified, as the agent can
f0 (x0 ) ◦ f1 (x1 ). f is clearly a 2n−sized instance of the delete state information by itself.
B.

Augmenting the MDP with a stochastic action

19
player game-play, and one can easily imagine autonomous
robots (think e.g. Curiosity rover in preparation for a
Mars mission) being pre-trained in a simulation (made as
The results presented so far demonstrate that strong realistic as possible given the information we have, includseparations in learning efficiency between classical and ing e.g. other autonomous and learning robots) of the
quantum-enhanced learning agents can be shown for some environment it will encounter.
families of (quite precisely) specified task environments,
provided the environment allows precise quantum interB. MDP restrictions
action. While these results have foundational relevance,
it is fair to ask to what extent such results are expected
to influence reinforcement learning as applied in the real
The second facet of the applicability of the presented
world. This question has a few facets which we address results to practical RL has to do with the still rigid propseparately.
erties the MDPs have to satisfy before speed-ups can be
obtained, even if oraculization is possible.
As we have explained in section IV C 3, one of the reaA. Oraculization issues
sons why we consider the RFS setting and not just the
arguably simpler MDPs, which additionally allow for a
First, in standard RL settings the environments the greater separation stemming from Simon’s problem, is to
agents interact with are classical, and macroscopic, which highlight certain self-similar features which are present
effectively prohibits useful oraculization. One possibility only in the RFS setting. Such features are reminiscent
to mitigate this concern is to consider quantum RL appli- to features of learning we often encounter in real life.
cations in quantum laboratories, where the environment Going further, it should be clear that quantum learning
agents can be devised for other oracular settings as well,
is manifestly quantum.
In recent years, there has been an increasing interest in and in this sense, the family of MDPs which can dramatutilizing machine learning techniques to mitigate various ically benefit from quantum enhancements is quite large.
obstacles one encounters when complex quantum devices, Nonetheless it is still a union of MDP families with a rigid
such as quantum computers are built. Indeed ideas on how structure. One of the reasons why the MDPs have a rigid
to use machine learning to help in achieving more efficient structure stems from the structure of the underlying orquantum fault tolerant computation, how to mitigate error acle identification problem – this structure, in turn, has
sources, and more generally, ideas on how to use ML to a dual purpose. First is to make the problem easy for a
build a scalable quantum computer similar have been put quantum agent. The second is to make it hard for any clasforward (see e.g. [39] for a review). Some such ideas rely sical agent. From the perspective of applicability, it makes
on reinforcement learning and it makes perfect sense to sense to consider broader sets of environments where the
utilize, if possible, fully coherent methods, i.e., quantum- quantum algorithms can still be applied (with the same efficiency), while giving up on the structure needed to prove
enhanced reinforcement learning 27 .
While this option is intriguing, it is still a restricted classical hardness.
One aspect of this has to do with the promise hidden
application of quantum-enhanced reinforcement learning.
Another, perhaps practically more promising option is in the underlying problem, which can be relaxed, thereby
to take a more abstract perspective, and understand the increasing the applicability of the underlying quantum alpresented quantum enhancements or RL as sub-routines, gorithm for oracle identification. The other is genuinely
occurring internally, in an agent interacting with an oth- linked with the quantum RL setting, specifically to the
erwise classical environment. One example of this occurs process of oraculization, and is thus more interesting from
in in model-based learning [9], where the learning agent our perspective.
Specifically, in the process of oraculization, the agent
constructs an internal representation of the external environment. Since such a representation is internal, it can can, for instance, “ignore” certain options, and recover a
then, at least in principle, be interrogated using all the given oracle. This was, for instance, done in both RFS
presented coherent methods. A second example has to and Simons MDP examples, where the quantum agent
do with constructed simulated environments, which are did not utilize the randomized option – and we had to
used to pre-train agents, before they are placed in the separately prove that this option does not help a classical
real problem settings. As we mentioned in the introduc- agent too much. If we do not insist on classical hardness
tion, in the case of the AlphaGo system, in particular the (or just proofs thereof), this can be greatly generalized.
most powerful AlphaGo Zero variant [11, 12], the system One aspect of this was thus already formalized in Lemma
is trained by utilizing self-play – essentially by playing one 3, which states that whenever the restricting of an agent’s
agent against a copy of itself – before it was tested against actions leaves the agent operating in a sub-MDP which
human and non-human opponents. The opponent here can be usefully oraculized, this opens the door for effiis simulated, and again, at least in principle, all quantum cient quantum algorithms (although, a-priori nothing can
methods could be applied given scalable quantum comput- be said about whether there also exist classical efficient
ers. Of course, such pre-training makes sense beyond two- algorithms). But this too can be generalized.
Note that the restricting of the agent’s actions (to
realize useful sub-MDP) can be understood as a filter/interface, placed between the agent and environment,
27 Naturally, for this to be feasible, at least a constant size quanwhich, intuitively, rejects some of the agent’s moves. But
tum computer should be achievable, which is capable of running
the quantum-enhanced algorithm – it is intriguing to consider the much more elaborate interfaces can be used, and such inpossibility that such a process could be “boot-strapped” and made terfaces capture various notions of “embedding” of one
to correct itself, as an autonomous and intelligent and adapting MDP into another. This also expands the applicability of
quantum fault tolerant method.
our results to all MDPs which embed any of the examples
VI.

QUANTUM REINFORCEMENT LEARNING
AND PRACTICE

20

The presented constructions balance between three
requirements which all have to be fulfilled to achieve
the goals of this work: demonstration of better-thanpolynomial speed ups for genuine RL tasks. First, it
should be hard for a classical agent to learn in a given
MDP, and moreover this should be rigorously provable.
Second, the quantum agent should be able to usefully
“oracularize” the provided environment under reasonable
concessions. Third, the MDP should be interesting, that
is, have properties which are quintessential to RL. The
second and third requirement are in fact in strong collision: interesting RL settings involve long memories, and
dependencies which vary in length which make lousy oracles. To resolve this collision, in this work we settled
for arguably minimal excursion into truly generic properties of RL MDPs – e.g. the randomness we allow occurs
only in the rewarding arm. This has a few consequences,
e.g. the optimal strategy (which uses the stochastic part
of the MDP) is not much better than the strategy which
resides in the deterministic part of the MDP: (n × l) vs
(n × l − n/4) steps between rewards. In order to increase
this separation, the agent would have to classically operate in the randomized section of the environment for
longer, in which case effectively quantizing just the deter-

ministic part of the environment would lead to a less of
advantage. Alternatively, one could attempt to genuinely
quantize/oraculize also the random parts of the environment, however this leads to oracles whose utility is still
not fully understood. Few results in this direction suggest
that improvements in such scenarios may be difficult, as in
many cases noisy or randomized oracles offer no advantage
over classical oracles [40, 41].
As a possible route of future research, one may attempt
to consider larger randomized areas by considering settings
which do not correspond to standard MDPs. For instance,
if the environment is allowed to be time-dependent, then
one could distribute the task into two phases – a deterministic one, where quantum access is used to learn useful information, a key, which is necessary to successfully
navigate later environments. This would entail a full formalization of ideas of hierarchical learning and information transfer we discussed briefly in section IV C 3. For
example, one could consider the notions of information
transfer from one environment to another, where already
liner separations between learning efficiency may lead to
settings where the agent behaves optimally in the limit,
or no better than a random agent (maximal separation).
Similar effects could be achieved in partially observable
MDP cases, however, there the optimal policies may not
be constant, but rather depend on the entire history of
interaction. Finally, it would be particularly interesting
to identify the possibilities of speed-ups in RL settings
which do not utilize a reduction onto oracle identification
problems, but deal directly with environmental maps.
Acknowledgements VD and JMT are indebted to Hans
J. Briegel for numerous discussions which have improved
and influenced many parts of this work. The authors
wish to thank Shelby Kimmel for initial discussions, and
Stephen Jordan, Scott Glancy and Scott Aaronson for
helpful feedback. VD also thanks JMT and Hans J.
Briegel for their hospitality during his stays. JMT acknowledges the support of the National Science Foundation under Grant No. NSF PHY11-25915. Contributions
by NIST, an agency of the US government, are not subject to US copyright. The authors acknowledge funding
from ARL CDQI. This material is based upon work supported by the U.S. Department of Energy, Office of Science, Advanced Scientific Computing Research Quantum
Algorithms Teams program.

[1] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick
Rebentrost, Nathan Wiebe and Seth Lloyd Nature 549,
195–202 (2017) doi:10.1038/nature23474
[2] Esma Aı̈meur, Gilles Brassard, and Sébastien Gambs.
Quantum speed-up for unsupervised learning. Machine
Learning, 90(2):261–287, 2013.
[3] Nathan Wiebe, Ashish Kapoor, and Krysta M. Svore.
Quantum algorithms for nearest-neighbor methods for
supervised and unsupervised learning. Quantum Info.
Comput., 15(3-4):316–356, March 2015.
[4] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd.
Quantum support vector machine for big data classification. Phys. Rev. Lett., 113:130503, Sep 2014.
[5] Seth Lloyd, Silvano Garnerone, and Paolo Zanardi. Quantum algorithms for topological and geometric analysis of
data. Nature Communications, 7:10138, jan 2016.
[6] Zhikuan Zhao, Jack K. Fitzsimons, and Joseph F. Fitzsimons. Quantum assisted gaussian process regression, 2015.
[7] Srinivasan Arunachalam and Ronald de Wolf. A survey of

quantum learning theory. CoRR, abs/1701.06806, 2017.
[8] Richard S. Sutton and Andrew G. Barto. Introduction
to Reinforcement Learning. MIT Press, Cambridge, MA,
USA, 1st edition, (1998).
[9] Stuart Russell and Peter Norvig. Artificial Intelligence:
A Modern Approach. Prentice Hall Press, Upper Saddle
River, NJ, USA, 3rd edition, 2009.
[10] David Silver, Aja Huang, Chris J. Maddison, Arthur
Guez, Laurent Sifre, George van den Driessche, Julian
Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam,
Marc Lanctot, Sander Dieleman, Dominik Grewe, John
Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go
with deep neural networks and tree search. Nature,
529(7587):484–489, Jan 2016. Article.
[11] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian

we have explicitly provided in this work. We leave a more
extensive analysis of this options for future work.
Naturally, at this point it cannot be claimed that we
do not claim that MDPs based on RFS or Simon’s problem, or even problems which embed such structures, “occur frequently in practice” nor that super-polynomial or
exponential speed-ups are possible generically. The latter is certainly not the case, as it would almost certainly violate the results proving the need for structure for
better-than-polynomial speed-ups. Nonetheless, this work
at least opens the possibility that certain genuinely useful reinforcement learning scenarios may too allow superpolynomial improvements. Such approaches may then
have utility in real RL settings the moment quantum computers of a sufficient size become available.

VII.

DISCUSSION

21

[12]

[13]

[14]
[15]

[16]
[17]
[18]

[19]

[20]
[21]

[22]
[23]

[24]
[25]

[26]

[27]

Chen, Timothy Lillicrap, Fan Hui, Laurent Sifre, George
van den Driessche, Thore Graepel, and Demis Hassabis.
Mastering the game of go without human knowledge.
Nature, 550:354–359, 2017. Article.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, Demis Hassabis.
Mastering Chess and Shogi by Self-Play with a General
Reinforcement Learning Algorithm. arXiv:1712.01815v1,
2017. Article.
Giuseppe Davide Paparo, Vedran Dunjko, Adi Makmal,
Miguel Angel Martin-Delgado, and Hans J. Briegel. Quantum speedup for active learning agents. Phys. Rev. X,
4:031002, Jul 2014.
Hans J. Briegel and Gemma De las Cuevas. Projective simulation for artificial intelligence. Scientific Reports, 2:400
EP –, May 2012. Article.
Daniel Crawford, Anna Levit, Navid Ghadermarzy,
Jaspreet S. Oberoi, and Pooya Ronagh. Reinforcement
learning using quantum boltzmann machines, 2016.
Vedran Dunjko, Jacob M. Taylor, and Hans J. Briegel.
Framework for learning agents in quantum environments,
2015.
Vedran Dunjko, Jacob M. Taylor, and Hans J. Briegel.
Quantum-enhanced machine learning. Phys. Rev. Lett.,
117:130501, Sep 2016.
Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26(5):1411–1473,
1997.
Sean Hallgren and Aram W. Harrow. Superpolynomial
Speedups Based on Almost Any Quantum Circuit, ICALP
2008: Automata, Languages and Programming, pages 782–
795, Springer, 2008.
Simon, D.R. On the power of quantum computation. In
Proceedings of 35th FOCS, pp. 116–123 (1996).
R. Beals, H. Buhrman, R. Cleve, M. Mosca and R. de
Wolf, “Quantum Lower Bounds by Polynomials,” Journal
of the ACM, Volume 48, Issue 4, July 2001, pp.778-797.
S. Aaronson and A. Ambainis, “The Need for Structure
in Quantum Speedups,” Theory of Computing, Volume 10
(2014), Article 6, pp.133-166.
A. M. Childs et al, “Exponential algorithmic speedup by
a quantum walk,” STOC ’03: Proceedings of the thirtyfifth annual ACM Symposium on Theory of Computing,
pp.59-68 (2003).
On the Sample Complexity
Sham
Kakade.
of Reinforcement Learning.
PhD thesis, University
College London, 2003.
Tor Lattimore, Marcus Hutter, and Peter Sunehag. The
sample-complexity of general reinforcement learning, 2013.
arXiv:1308.4828.
Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforcement learning.
In Proceedings of the 28th International Conference
on Neural Information Processing Systems, NIPS’15,
pages 2818–2826, Cambridge, MA, USA, 2015. MIT
Press.
URL http://dl.acm.org/citation.cfm?id=
2969442.2969555.
Barry, J., Barry, D. T. and Aaronson, S. Quantum par-

[28]

[29]

[30]

[31]

[32]

[33]

[34]
[35]

[36]

[37]
[38]

[39]

[40]
[41]

tially observable Markov decision processes. Phys. Rev.
A, 90, 032311 (2014).
Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509,
oct 1997. doi:10.1137/s0097539795293172. URL https:
//doi.org/10.1137/s0097539795293172.
Nader H. Bshouty and Jeffrey C. Jackson. Learning DNF
over the uniform distribution using a quantum example
oracle. SIAM Journal on Computing, 28(3):1136–1153,
jan 1998. doi:10.1137/s0097539795293123. URL https:
//doi.org/10.1137/s0097539795293123. Appeared in n
Computational learning theory (COLT) conference proceedings in 1995.
Rocco A. Servedio and Steven J. Gortler. Equivalences
and separations between quantum and classical learnability. SIAM Journal on Computing, 33(5):1067–1092,
jan 2004. doi:10.1137/s0097539704412910. URL https:
//doi.org/10.1137/s0097539704412910.
M. L. Puterman Markov Decision Processes: Discrete
Stochastic Dynamic Programming. Wiley-Interscience,
ISBN:0471727822 (2005).
D. Deutsch and R. Jozsa. Rapid solution of problems by
quantum computation. Proceedings of the Royal Society
A: Mathematical, Physical and Engineering Sciences, 439
(1907):553–558, dec 1992. URL https://doi.org/10.
1098/rspa.1992.0167.
Michael J. Kearns and Robert E. Schapire. Efficient
distribution-free learning of probabilistic concepts. Journal of Computer and System Sciences, 48(3):464–497, Jun.
1994.
R. A. Servedio and S. J. Gortler. Quantum versus classical
learnability. In Proceedings 16th Annual IEEE Conference
on Computational Complexity, pages 138–148, 2001.
Rocco A. Servedio and Steven J. Gortler. Equivalences
and separations between quantum and classical learnability. SIAM Journal on Computing, 33(5):1067–1092, jan
2004.
Simon Hangl and Emre Ugur and Sandor Szedmak and
Justus Piater. Robotic playing for hierarchical complex
skill learning. In Proceedings of 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems
(IROS) (2016)
Scott Aaronson Quantum lower bound for recursive
Fourier sampling. Quant. Inf. Comp., 5, pp. 176–177
(2005).
G. Brassard and P. Hoyer. An exact quantum polynomialtime algorithm for Simon’s problem. In Proceedings of
the Fifth Israeli Symposium on Theory of Computing and
Systems (1997).
V. Dunjko and H. J. Briegel, Machine learning & artificial intelligence in the quantum domain. arXiv:1709.02779
(2017)
O. Regev, L. Schiff. Impossibility of a quantum speed-up
with a faulty oracle. In Proceedings of 35th ICALP , pp.
773–781 (2008).
A. W. Harrow, D. J. Rosenbaum Uselessness for an oracle
model with internal randomness Quantum Inf. Comput.
14, 7&8, pp. 608–624 (2014)

