Show simple item record

dc.contributor.advisorPatel, Apoorva
dc.contributor.authorRahaman, Md Aminoor
dc.date.accessioned2010-12-30T06:50:38Z
dc.date.accessioned2018-07-31T05:08:52Z
dc.date.available2010-12-30T06:50:38Z
dc.date.available2018-07-31T05:08:52Z
dc.date.issued2010-12-30
dc.date.submitted2009-06-05
dc.identifier.urihttp://etd.iisc.ac.in/handle/2005/972
dc.description.abstractRandom 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.en_US
dc.language.isoen_USen_US
dc.relation.ispartofseriesG23425en_US
dc.subjectLattice Theory - Data Processingen_US
dc.subjectQuantum Random Walken_US
dc.subjectGrover's Algorithmen_US
dc.subjectDirac Operatorsen_US
dc.subjectQuantum Computationen_US
dc.subjectDimensional Hypercubic Latticesen_US
dc.subjectRandom Walk Algorithmen_US
dc.subjectSpatial Searchen_US
dc.subject.classificationQuantum Physicsen_US
dc.titleSearch On A Hypercubic Lattice Using Quantum Random Walken_US
dc.typeThesisen_US
dc.degree.nameMSc Enggen_US
dc.degree.levelMastersen_US
dc.degree.disciplineFaculty of Engineeringen_US


Files in this item

This item appears in the following Collection(s)

Show simple item record