Advanced search options

You searched for `subject:(Dimensional Hypercubic Lattices)`

. One record found.

▼ Search Limiters

Indian Institute of Science

1.
Rahaman, Md Aminoor.
Search On A *Hypercubic* Lattice Using Quantum Random Walk.

Degree: 2009, Indian Institute of Science

URL: http://hdl.handle.net/2005/972

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.
*Advisors/Committee Members: Patel, Apoorva.*

Subjects/Keywords: Lattice Theory - Data Processing; Quantum Random Walk; Grover's Algorithm; Dirac Operators; Quantum Computation; Dimensional Hypercubic Lattices; Random Walk Algorithm; Spatial Search; Quantum Physics

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Rahaman, M. A. (2009). Search On A Hypercubic Lattice Using Quantum Random Walk. (Thesis). Indian Institute of Science. Retrieved from http://hdl.handle.net/2005/972

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

Rahaman, Md Aminoor. “Search On A Hypercubic Lattice Using Quantum Random Walk.” 2009. Thesis, Indian Institute of Science. Accessed June 26, 2019. http://hdl.handle.net/2005/972.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Rahaman, Md Aminoor. “Search On A Hypercubic Lattice Using Quantum Random Walk.” 2009. Web. 26 Jun 2019.

Vancouver:

Rahaman MA. Search On A Hypercubic Lattice Using Quantum Random Walk. [Internet] [Thesis]. Indian Institute of Science; 2009. [cited 2019 Jun 26]. Available from: http://hdl.handle.net/2005/972.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Rahaman MA. Search On A Hypercubic Lattice Using Quantum Random Walk. [Thesis]. Indian Institute of Science; 2009. Available from: http://hdl.handle.net/2005/972

Not specified: Masters Thesis or Doctoral Dissertation