IISc Logo    Title

etd AT Indian Institute of Science >
Centres under the Director (formely kown as Division of Information Sciences) >
Supercomputer Education and Research Centre (serc) >

Please use this identifier to cite or link to this item: http://etd.iisc.ernet.in/2005/972

Title: Search On A Hypercubic Lattice Using Quantum Random Walk
Authors: Rahaman, Md Aminoor
Advisors: Patel, Apoorva
Keywords: Lattice Theory - Data Processing
Quantum Random Walk
Grover's Algorithm
Dirac Operators
Quantum Computation
Dimensional Hypercubic Lattices
Random Walk Algorithm
Spatial Search
Submitted Date: 5-Jun-2009
Series/Report no.: G23425
Abstract: Random walks describe diffusion processes, where movement at every time step is restricted only to neighbouring locations. Classical random walks are constructed using the non-relativistic Laplacian evolution operator and a coin toss instruction. In quantum theory, an alternative is to use the relativistic Dirac operator. That necessarily introduces an internal degree of freedom (chirality), which may be identified with the coin. The resultant walk spreads quadratically faster than the classical one, and can be applied to a variety of graph theoretical problems. We study in detail the problem of spatial search, i.e. finding a marked site on a hypercubic lattice in d-dimensions. For d=1, the scaling behaviour of classical and quantum spatial search is the same due to the restriction on movement. On the other hand, the restriction on movement hardly matters for d ≥ 3, and scaling behaviour close to Grover’s optimal algorithm(which has no restriction on movement) can be achieved. d=2 is the borderline critical dimension, where infrared divergence in propagation leads to logarithmic slow down that can be minimised using clever chirality flips. In support of these analytic expectations, we present numerical simulation results for d=2 to d=9, using a lattice implementation of the Dirac operator inspired by staggered fermions. We optimise the parameters of the algorithm, and the simulation results demonstrate that the number of binary oracle calls required for d= 2 and d ≥ 3 spatial search problems are O(√NlogN) and O(√N) respectively. Moreover, with increasing d, the results approach the optimal behaviour of Grover’s algorithm(corresponding to mean field theory or d → ∞ limit). In particular, the d = 3 scaling behaviour is only about 25% higher than the optimal value.
URI: http://etd.iisc.ernet.in/handle/2005/972
Appears in Collections:Supercomputer Education and Research Centre (serc)

Files in This Item:

File Description SizeFormat
G23425.pdf732.84 kBAdobe PDFView/Open

Items in etd@IISc are protected by copyright, with all rights reserved, unless otherwise indicated.


etd@IISc is a joint service of SERC & IISc Library ||
|| Powered by DSpace || Compliant to OAI-PMH V 2.0 and ETD-MS V 1.01