A Survey on Grid-world Navigation by Reinforcement Learning
- To start with --- Toword a solution to the "Jeep Problem"
- [1]
T. Lane, and A. Wilson (2005)
"Toward a Topological Theory of Relational Reinforcement Learning for Navigation Tasks." (6 pages)
- "We describe relational policies for such environments that are relocatable by virtue of being parameterized solely in terms of the relations (distance and direction) between the agentfs current state and the goal state."
- "We demonstrate that this formulation yields significant learning improvements in completely homogeneous environments for which exact policy relocation is possible. We also examine the effects of non-homogeneities such as walls or obstacles and show that their effects can be neglected if they fall outside of a closed-form envelope surrounding the optimal path between the agent and the goal."
-
"We exploit recent results by Ravindran and Barto (Ravindran & Barto 2002; 2003; Ravindran 2004) on the equivalence of options (partial policies) under homeomorphic transforms to construct goal-seeking policies described only in terms of the relationship between current state and goal state, independentlyof absolute coordinate."
-
[1.1]
Ravindran, B., and Barto, A. G. (2002)
"Model minimization in hierarchical reinforcement learning."
In Holte, R., ed., Proceedings of the 2002 Symposium on Abstraction,
Reformulation, and Approximation (SARA-2002).
-
[1.2]
Ravindran, B., and Barto, A. G. 2003.
"Relativized options: Choosing the right transformation."
In Fawcett, T., and Mishra, N., eds., Proceedings of the Twentieth International Conference on Machine Learning, 608.615. Washington, DC: AAAI Press.
-
[1.3]
Ravindran, B. (2004) "An Algebraic Approach to Abstraction in Reinforcement Learning."
Ph.D. Dissertation, Department of Computer Science, University of Massachusetts, Amherst, MA.
-
"Ravindran and Barto extending model minimization work by Dean and Givan (Dean & Givan 1997), have studied such policy relocations."
-
"Unlike methods that have been developed for MDPs with 'rooms' or 'corridors' (Hauskrecht et al. 1998; Parr 1998a), our results are most applicable to open and largely unobstructed spaces such as free space or open field navigation."
-
[1.5]
Hauskrecht, M., Meuleau N., Boutilier C., Kaelbling, L. P., and Dean, T. (1998)
"Hierarchical solution of Markov decision processes using macro-actions.
In Cooper, G. F., and Moral, S., eds., Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI-98), Morgan Kaufmann.
-
[1.6]
Parr, R. E. (1998)
"Hierarchical Control and Learning for Markov Decision Processes."
Ph.D. Dissertation, University of California at Berkeley.
- [B]
E. Rieffel and W. Polak (2000)
"An Introduction to Quantum Computing for Non-Physicists"
Los Alamos Physics preprint archive, http://xxx.lanl.gov/abs/quantph/ 9809016.
(45 pages)
- The author of "Finding Solutions to NP Problems: Philosophical Differences Between Quantum
and Evolutionary Search Algorithms" claims the best tutorial among othres which were writtne
by physisits.
-
"Accessing the results is equivalent to making a measurement, which disturbs the quantum state."
-
"a register of n qubits can be in a superposition of all 2^n possible values."
-
"only one classical bit's worth of information can be extracted from a qubit."
-
"all quantum state transformations have to be reversible.
While the classical NOT gate is reversible, AND, OR and NAND gates are not.
Thus it is not obvious that quantum transformations can carry out all classical computations."
-
"Boyer et.al. [Boyer et al. 1996] provide a detailed analysis of the performance of Grover'
algorithm."
-
BOYER, M., BRASSARD, G., HOYER, P., AND TAPP, A. 1996. Tight bounds on quantum search. In
Proceedings of the Workshop on Physics of Computation: PhysComp '96 (Los Alamitos, CA, 1996).
Institute of Electrical and Electronic Engineers Computer Society Press. Preprint at
Los Alamos Physics reprint Archive, http://xxx.lanl.gov/abs/quant-ph/9605034. => OK
-
"Quantum error correction must reconstruct the exact encoded quantum state. Given the
impossibility of cloning or copying the quantum state, this reconstruction appears harder
than in the classical case. However, it turns out that classical techniques can be modified
to work for quantum systems."
-
"Decoherence, the distortion of the quantum state due
to interaction with the environment, is a key problem."
-
"Colin Williams and Scott Clearwater's book "Explorations in QuantumComputing"
[Williams and Clearwater 1998] comes with software, in the form of Mathematica notebooks, that
simulates some quantum algorithms like Shor's algorithm" (This is a book not a paper)
-------------------
-
"The state space of a quantum system, consisting of the positions, momentums, polarizations,
spins, etc. of the various particles, is modelled by a Hilbert space of wave functions.
We will not look at the details of these wave functions. For quantum computing we need
only deal with finite quantum systems and it suffices to consider finite dimensional complex
vector spaces with an inner product that are spanned by abstract wave functions such
as |¨>."
-
"Quantum state spaces and the tranformations acting on them can be described in terms
of vectors and matrices or in the more compact bra/ket notation invented by Dirac in 1958."
-
"Kets like |x> denote column vectors and are typically used to describe quantum states."
- [C]
I. Carneiro, M. Loo, X. Xu, M. Girerd, V Kendon, and P. L. Knight (2005)
"Entanglement in coined quantum walks on regular graphs"
New Journal of Physics Vol. 7, pp 156--185
(29 pages)
- The author of "Finding Solutions to NP Problems: Philosophical Differences Between Quantum
and Evolutionary Search Algorithms" claims the best tutorial among othres which were writtne
by physisits.
-
"For an overview of the development of quantum walks for quantum computing, see
the recent reviews by Kempe [6] and Ambainis [7]."
[C6] Kempe J 2003 Contemp. Phys. 44 302.27 (Preprint quant-ph/0303081) -> not-yet found
[C7] Ambainis A 2003 Int. J. Quantum Inform. 1 507 (Preprint quant-ph/0403120)
-
"Like classical random walks, quantum walks come in both discrete time [C12]--[C15] and
continuous time [C16] versions."
[C12] Y. Aharonov, L. Davidovich and N. Zagury (1993)
"Quantum Random Walks. hys. Rev. A 48(2) pp. 1687--1690 => OK
[C13] Watrous J 2001 J. Comp. System Sci. 62 376 (Preprint cs.CC/9812012) => OK
[C14] Aharanov D., Ambainis A., Kempe J. and Vazirani U2001 Proc. 33rd Annual ACMSymp.
on Theory of Computing (STOC 2001) (NewYork: Assoc. for Comp. Machinery)
pp 50.9 (Preprint quant-ph/0012090) => OK
[C15] Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, and John Watrous (2001)
"One-Dimensional Quantum Walks."
In Proceedings of the Thirty-Third Annual ACM Symposium on the Theory of Computing, pages 37--49, 2001. => OK
[C16] Farhi E and Gutmann S 1998 Phys. Rev. A 58 915 (Preprint quant-ph/9706062) => OK
-
"The discrete and continuous time versions of classical random walks can be related in
a straightforward manner by taking the limit of the discrete walk as the size of the time step
goes to zero. In the quantum case, the discrete and continuous time walks have different sized
Hilbert spaces so there is no simple limit that relates the two basic formulations."
-
"There is also an example of a problem where the algorithmic powers of discrete
and continuous time walks differ. Spatial search, where there is a cost associated with moving
from one data element to another, can be accomplished faster with a discrete time quantum walk,
but a continuous time quantum walk only performs as well for spatial dimensions greater than
four [17]. A continuous time walk with extra degrees of freedom has also been formulated by
Childs and Goldstone [18] that does correspond to the limit of the discrete time walk and can
perform equally well on spatial search."
[17] Childs A and Goldstone J 2004 Phys. Rev. A 70 022314 (Preprint quant-ph/0306054) => OK
[18] Childs A M and Goldstone J 2004 Phys. Rev. A 70 042312 (Preprint quant-ph/0405120) => OK
"Our work in this paper investigates the properties of coins in discrete quantum walks.
We follow on from prior work on quantum coins by Mackay et al [19] and Tregenna et al
[20], broadening the types of graphs studied. "The question of what is particularly quantum
in a quantum walk is an interesting one which has attracted much attention [21].[23]."
[19] Mackay T D, Bartlett S D, Stephenson L T and Sanders B C 2002
J. Phys. A: Math. Gen. 35 2745 (Preprint quant-ph/0108004) => OK
[20] Tregenna B, Flanagan W, Maile R and Kendon V 2003 New J. Phys. 5 83
(Preprint quant-ph/0304204) => OK
[21] Kendon V M and Sanders B C 2004 Phys. Rev. A 71 022307
(Preprint quant-ph/0404043) => OK
[22] Knight P L, Roldan E and Sipe J E 2003 Phys. Rev. A 68 020301(R)
(Preprint quant-ph/0304201) => OK
[23] Knight P L, Roldan E and Sipe J E 2003 Opt. Commun. 227 147
(Preprint quant-ph/0305165) => OK
-
"we address this issue by investigating the evolution of the quantum mechanical entanglement as
the quantum walk progresses."
-
"Since the range of higher-dimensional coin operators is too large for systematic numerical
study, for the remainder of this paper we concentrate on two natural choices" --- Grover's and DFT coins.
"Equation (1) represents the most general
expression [24] for a unitary coin operator with two degrees of freedom."
[24] Bach E, Coppersmith S, Goldschen M P, Joynt R andWatrous J 2004
J. Comput. Syst. Sci. 69 562.92
-
"The Grover operator was first introduced by Moore and Russell
[25] in their study of quantumwalks on the hypercube."
[25] Moore C and Russell A 2002 Proc. 6th Int. Workshop on Randomization and
Approximation Techniques in Computer Science (RANDOM '02)
ED. J. D. P. Rolim and S Vadhan (Berlin: Springer) pp 164.78 (Preprint quant-ph/0104137)
-
"We studied the entanglement for the walk on the glued trees graph,
but it did not provide useful indications of the progress of the walk,
so we do not present any of these results here."
-
"The DFT coin operator is unbiased for any degree, so the spreading depends
only on the relative phases, which can be controlled by the coin labelling."
- Approaches to A-Needle-in-a-Haystack
- Search for a Needle in Conputer Science
Grover [D] above refered three papers writing
"Various important computer science problems can be represented in this form [D3] [D5] [D9]."
Then ...
- Can GP simulate Quantum Computation?
This might give us a good insight to a bridge between Quantum-computation and traditional one.
- [E]
L. Spector H. Barnum, H. J. Bernstein, and N. Swamy (1996)
"Finding a Better-than-Classical Quantum AND/OR Algorithm using Genetic Programming"
Proceedings, of the 1999 Conhgress on Evolutionary computation.
(8 pages)
-
"For those new to quantum computing Steane provides a good overview [E7],
Braunstein provides an accessible on-line tutorial
[E8], Williams and Clearwater provide a text with a CD
ROM containing Mathematica code for simulating quantum
computers [E9], and Milburn provides an introduction for the
general reader [E10]."
[E7] A. Steane, .Quantum computing,. Reports on
Progress in Physics, vol. 61, pp. 117.173, 1998,
http://xxx.lanl.gov/abs/quant-ph/9708022.
[E8] S. L. Braunstein, .Quantum computation: a tutorial,
. Available only electronically, on-line at
URL http ://chemphys.weizmann.ac.il/
~schmuel/comp/comp.html, 1995.
[E9] C. P.Williams and S. H. Clearwater, Explorations in Quantum
Computing, Springer-Verlag, TELOS, 1997.
[E10] G. J. Milburn, SchrNodingerfs Machines: The Quantum Technology
Reshaping Everyday Life, W. H. Freeman & Co., 1997.
-
"Because practical quantum computer hardware is not yet
available, we must test the tness of evolved quantum algorithms
using a quantum computer simulator that runs on
conventional computer hardware. This entails an exponential
slowdown, so we must be content to simulate relatively small
systems."
-
"The basic unit of information in a quantum computer is a
qubit, which is like a classical bit except that a qubit can exist
in a superposition of states and can become entangled with
other qubits.that is, its value can be linked to the values of
other qubits in non-classical ways."
"We will give a fuller
treatment of the quantum mechanics of these algorithms in a future article."
(Now we can check what has happened via google search for example.)
- Quantum Random Walks
-
[C6]
J. Kempe (2003)
"Quantum Random Walks -- An Introductory Overview'
Contemporary Physics, Vol. 44 Issue 4 (also preprint quant-ph/0303081), pp. 307-327.
(20 pages)
-
"We will give a thorough introduction to the necessary terminology without
overburdening the reader with unnecessary mathematics."
-
"An excellent comprehensive introduction to quantum information and computation
can be found in [1]."
[1] M.A. Nielsen and I.L. Chuang. Quantum Computation
and Quantum Information. Cambridge University Press,
Cambridge, UK, 2000."
-
"This example - which might be thought of as a precursor to
later models - is taken from the work of three physicists
in 1993, Y. Aharonov, L. Davidovich and N. Zagury [5].
Their work for the first time coins the term fquantum random walkf."
-
[C7]
A. Ambainis
"Quantum Walks and Their Algorithmic Applications"
International Journal of Quantum Information,
Vol 1 (also preprint quant-ph/0403120), 2003, pp. 507--518.
(11 pages)
-
Author refer 4 papers as recent work regarding Quantum Walk Search as
[C7-10] N. Shenvi, J. Kempe, K. Whaley. Quantum random-walk search algorithm, Physical Review
A, 67:052307, 2003. Also quant-ph/0210064.
[C7-11] A. Childs, J. Goldstone. Spatial search by quantum walk, quant-ph/0306054.
[C7-12] A. Ambainis. Quantum walk algorithm for element distinctness. quant-ph/0311001.
[C7-13] A. Ambainis, J. Kempe, A. Rivosh. Coins make quantum walks faster, quant-ph/0402107.
-
"there is a clever reduction to the walk on line [7]."
[7] A. Childs, E. Farhi, S. Gutmann. An example of the difference between quantum and
classical random walks. Journal of Quantum Information Processing, 1:35, 2002. Also
quant-ph/0103020.
-
"Thus, we have a variant of continous quantum walk on line, with matrix H slightly different from
one described in section 2.2."
----------
The first algorithm of this type
(searching the Boolean hypercube) was discovered by Shenvi et al. [10].
- Quantum Walk Search
The following 4 papers are those Ambainis [C7] refered to in his paper.
-
[C7-10]
N. Shenvi, J. Kempe, and B. Whaley (2003)
"A Quantum Random Walk Search Algorithm"
Physical Review A, Vol 67 pp. 052307--052318. (also preprint quant-ph/0210064).
(13 pages)
-
"previous to a very recent paper by Childs et. al. [6], there had been
no quantum algorithms based on the random walk model."
-
"Current research uses two distinct models for quantum random walks, based on either discrete time steps or on continuous time evolution.
Discrete time quantum random walks were introduced as a possible new tool for quantum
algorithms generalizing discrete classical Markov chains. ... In the continuous-time walk
the adjacency matrix of the graph is used to construct a Hamiltonian which gives rise to
a continuous time evolution."
-
"The discrete time random walk can be described by the repeated application of
a unitary evolution operator U. This operator acts on a Hilbert space HCxHS ...
where HC is the Hilbert space associated with a quantum coin and
HS is the Hilbert space associated with the nodes of the graph."
-
"the coin is a quantum coin and can therefore exist in a superposition of sta"
-
"An important feature of the discrete time quantum random walk that has significance
for its use in development of quantum algorithms, is that by virtue of its definition
this walk will be efficiently implementable on a quantum computer
whenever its classical counterpart is."
-
"We refer the reader to the recent papers [2], [3], [11] and [12] for
some results obtained from discrete time quantum random walks."
[2] D. Aharonov, A. Ambainis, J. Kempe, and U. Vazirani, in Proceedings of ACM Symposium on Theory of Computing
(STOC) (ACM, New York, NY, 2001), pp. 50.59, LANL preprint quant-ph/0012090.
[3] A. Ambainis, E. Back, A. Nayak, A. Vishwanath, and J. Watrous, in Proc. 33rd STOC (ACM, New York, NY, 2001), pp.
60.69.
[11] C. Moore and A. Russell, Proc. RANDOM, to appear (2002), lanl-arXive quant-ph/0104137.
[12] J. Kempe, quant-ph/0205083 (2002).
-
"Our random walk search algorithm will be based on a random walk on the n-cube, i.e. the hypercube of dimension n [11, 12]. The hypercube is a graph with N = 2n nodes, each of which can be labelled by an n-bit binary string."
-
"We define the search space of the algorithm to be the set of all n-bit binary strings,
x = {0, 1}^n. We consider the function f(x) = {0,1}, such that f(x) = 1 for exactly
one input x_target. Our goal is to find x_target."
-
"Each iteration in Grover's algorithm corresponds to a rotation in this subspace.
In this paper, we have shown that the random walk search algorithm can also be viewed
as a rotation in a two-dimensional subspace."
-
"The random walk search analyzed here was based on a discrete walk on the hypercube."
"The probability distribution generated by running quantum walk for t steps and measuring it
has been studied in more detail in refs. [5, 15, 16, 17, 18]."
[5] A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, and J. Watrous. One-dimensional quantum walks.
Proceedings of STOCf01, pp. 37-49.
Proceedings of the thirty-third annual ACM symposium on Theory of computing table of contents
Year of Publication: 2001
[15] A. Nayak, A. Vishvanath. Quantum walk on the line. quant-ph/0010117
[16] N. Konno. A New Type of Limit Theorems for the One-Dimensional Quantum Random Walk.
quant-ph/0206103.
[17] H. Carteret, M. Ismail, B. Richmond. Three routes to the exact asymptotics for
the onedimensional quantum walk. Journal of Physics A, 36:8775-8795, 2003. Also quant-ph/0303105.
[18] G. Grimmett, S. Janson, P. Scudo. Weak limits for quantum random walks. quant-ph/0309135
-
[C7-11]
A. M. Childs, and J. Goldstone
"Spatial search by quantum walk"
(12 pages)
-
"Suppose we had N items stored in a d-dimensional physical space, and that these
items could be explored in superposition by a quantum computer making local moves
(a 'quantum robot' [3])."
[3] P. Benioff, Space searches with a quantum robot, quant-ph/0003006, in Quantum Computation
and Information,eds. S. J. Lomonaco and H. E. Brandt (AMS, 2002). => OK 9 May
-
"Here we consider the continuous time quantum walk [5]. On certain graphs, this quantum walk can
yield exponentially faster hitting times than its classical counterpart [5, 6]. Indeed, a recent
result shows that the continuous time quantum walk can solve a certain black box problem
exponentially faster than any classical algorithm [7]."
[5] E. Farhi and S. Gutmann, Quantum computation and
decision trees, quant-ph/9706062, Phys. Rev. A 58, 915
(1998).
[6] A. M. Childs, E. Farhi, and S. Gutmann, An example
of the difference between quantum and classical random
walks, quant-ph/0103020, Quantum Information Processing 1, 35 (2002). => OK 9 May
[7] A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann,
and D. A. Spielman, Exponential algorithmic speedup by
quantum walk, quant-ph/0209131, Proc. 35th ACM Sym-
posium on Theory of Computing, 59 (2003).
-
"The continuous time quantum walk on a graph takes
place in an N-dimensional Hilbert space spanned by
states |ji, where j is a vertex in G."
- One-dimensional Quantum Random Walks cited by Shenvi et al. (2003) above.
-
[C7-5]
A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, and J. Watrous (2001)
"One-dimensional quantum walks."
Proceedings of the 33rd annual ACM symposium on Theory of computing (STOC'01) pp. 37-49.
(13 pages)
-
"In the classical case, it is wellknown
that a random walk on a (two-way infinite) line has expected distance $\Theta(\sqrt t)$
from the origin at time t,
and the probability of being at a distance $Omega(t)$ from the origin is exponentially small.
In contrast, observation of a quantum particle doing a Hadamard walk on the line after t steps
yields an expected distance $\Theta(t)$ from the origin. Moreover, the location of the particle
is almost uniformly distributed over the interval $[-t/\sqrt 2, t/\sqrt 2]$, so that the quantum
walk spreads quadratically faster than the classical random walk."
-
"Various quantum variants of random walks have previously been studied by a few authors
[6, 12, 24, 32], but their results are, for the most part, unrelated to ours."
---
[6] A. Childs, E. Farhi, S. Gutmann. An example of the
difference between quantum and classical random
walks. LANL preprint archive, quant-ph/0103020.
[12] E. Farhi and S. Gutmann. Quantum computation and
decision trees. Physical Review A, 58:915{928, 1998.
[24] D. Meyer. From quantum cellular automata to
quantum lattice gases. Journal of Statistical Physics,
85:551{574, 1996. Also available from the Los Alamos
Preprint Archive, quant-ph/9604003.
[32] J. Watrous. Quantum simulations of classical random
walks and undirected graph connectivity. Journal of
Computer and System Sciences, 62(2): 376-391, 2001.
-
"The (pure) quantum states of our systems may be identified with unit vectors in the Hilbert
space $l_2(Z)\otimesl_2 (\Sigma)$, for which the set ${| n \in N, d \in \Sigma}$ forms
an orthonormal basis. Each state |n>|d> is identified with the classical state (n,d)."
-
"It is yet unclear whether quantum walks are interesting from an algorithmic point of view. Any
speed-up of a known classical algorithm based on random walks (such as those mentioned in Section
1) seems to involve the analysis of quantum walks on graphs much more complex than the line."
-----
-
"To study the properties of quantum walks, we consider the wave function describing the position
of the particle and analyze how it evolves with time. Let
$\Psi(n,t) = (\psi_L (n,t), \psi_R (n,t))^T$
be the two component vector of amplitudes of the particle being at point n at time t,
with the chirality being left (upper component) or right (lower component)."
-----
-
"Similarly, let $P(n, t) = p_L(n, t) + p_R(n, t)$ be the probability of being at position
n at time t."
-----
-
[C7-15]
A. Nayak, A. Vishvanath.
"Quantum walk on the line." quant-ph/0010117
(20 pages)
-
"As explained below (and also shown by [13]), it is still possible to construct a unitary walk
if the particle has an extra degree of freedom that assists in its motion."
[13] David A. Meyer. From quantum cellular automata to quantum lattice gases.
Journal of Statistical Physics, 85:551.574, 1996. => OK (05/04)
-
"A walk on the line by such a particle
may be described as follows. At every time step, its chirality undergoes a rotation (a unitary transformation
in general) and then the particle moves according to its final chirality state."
-
"The problem of evaluating, or even approximating, path integrals to determine the time
development of a wave function is well known to be notoriously hard. We circumvent this barrier
by taking the Schrodinger approach, which takes advantage of the time and space homogeneity of
the quantum walk."
-
"The Fourier transform of the
wave function is thus easily analysed, and transformed back to the spatial domain. It is
noteworthy that this technique is standard in the analysis of classical random walk [5]."
-
"Finally, we ask if it is possible to design quantum algorithms to generate certain desirable
superpositions efficiently.those corresponding to distributions that are classically hard to
sample from (much in the spirit of [15])."
"We can calculate the probability of observing the particle doing the quantum walk at any given
point $n = \alpha t$ from the wave function derived above. Below we give the asymptotic
distribution for points $\alpha = n/t$ between
$-1/\sqrt{2} + \epsilon$ and $-1/\sqrt{2} - \epsilon$
for an arbitrarily small constant $\epsilon> 0$."
-
[C7-17]
H. Carteret, M. Ismail, B. Richmond.
Three routes to the exact asymptotics for the onedimensional
quantum walk. Journal of Physics A, 36:8775-8795, 2003. Also quant-ph/0303105.
(26 pages)
-
"Meyer therefore considered the wave function as a two component vector of amplitudes
of the particle being at point n at time t."
-
"The first authors to discuss the quantum random walk were Y. Aharonov,
Davidovich and Zagury, in [2] where they described a very simple realization
of the quantum random walk in quantum optics."
[2] Y. Aharonov, L. Davidovich, and N. Zagury, Quantum random walks, Phys.
Rev. A 48 (1993), 1687.
-
"We refer to the paper by Ambainis, Bach, Nayak, Vishwanath and Watrous [3] for proper
definitions and references."
[3] A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, and J. Watrous,
One-Dimensional Quantum Walks, Proceedings of ACM Symposium on Theory
of Computation (STOCf01), July 2001, Association for Computing Machinery,
New York, 2001, pp. 37.49.
- Yet other citation by Shenvi et al. (2003) above.