Record Details

Search On A Hypercubic Lattice Using Quantum Random Walk

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title Search On A Hypercubic Lattice Using Quantum Random Walk
 
Creator Rahaman, Md Aminoor
 
Subject Lattice Theory - Data Processing
Quantum Random Walk
Grover's Algorithm
Dirac Operators
Quantum Computation
Dimensional Hypercubic Lattices
Random Walk Algorithm
Spatial Search
Quantum Physics
 
Description 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.
 
Contributor Patel, Apoorva
 
Date 2010-12-30T06:50:38Z
2010-12-30T06:50:38Z
2010-12-30
2009-06-05
 
Type Thesis
 
Identifier http://hdl.handle.net/2005/972
 
Language en_US
 
Relation G23425