Correcting for potential barriers in quantum walk search

A randomly walking quantum particle searches in Grover's Θ(√N) iterations for a marked vertex on the complete graph of N vertices by repeatedly querying an oracle that ips the amplitude at the marked vertex, scattering by a "coin" ip, and hopping. Physically, however, potential energy barriers can hinder the hop and cause the search to fail, even when the amplitude of not hopping decreases with N. We correct for these errors by interpreting the quantum walk search as an amplitude amplification algorithm and modifying the phases applied by the coin ip and oracle such that the amplification recovers the Θ(√N) runtime.

• Publication year

  2015

• Venue

  Quantum information & computation

• Publication date

  2015-05-08

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.26421/QIC15.15-16-7arXiv 1505.02035
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Grover search with lackadaisical quantum walks

  2015cited by this paper
• Quantum walk search through potential barriers

  2015cited by this paper
• Quantum walk of a trapped ion in phase space.

  2009cited by this paper
• Quantum Walk in Position Space with Single Optically Trapped Atoms

  2009cited by this paper
• Quantum algorithm for linear systems of equations.

  2008cited by this paper
• Scattering quantum random-walk search with errors

  2007cited by this paper
• Realization of quantum walks with negligible decoherence in waveguide lattices.

  2007cited by this paper
• A Quantum Algorithm for the Hamiltonian NAND Tree

  2007cited by this paper
• Under consideration for publication in Math. Struct. in Comp. Science Decoherence in quantum walks- a review

  2006cited by this paper
• A Polynomial Quantum Algorithm for Approximating the Jones Polynomial

  2005cited by this paper
• Experimental implementation of a discrete-time quantum random walk on an NMR quantum-information processor

  2005cited by this paper
• Coins make quantum walks faster

  2004cited by this paper
• QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS

  2003cited by this paper
• Quantum walk algorithm for element distinctness

  2003cited by this paper
• Effects of a random noisy oracle on search algorithm complexity

  2003cited by this paper
• Quantum random walks: An introductory overview

  2003cited by this paper
• Quantum random-walk search algorithm

  2002cited by this paper
• Arbitrary phases in quantum amplitude amplification

  2000cited by this paper
• Optical Galton board

  1999cited by this paper
• Quantum Counting

  1998cited by this paper
• A fast quantum mechanical algorithm for database search

  1996cited by this paper
• From quantum cellular automata to quantum lattice gases

  1996cited by this paper
• On the absence of homogeneous scalar unitary cellular automata

  1996cited by this paper
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

  1995cited by this paper
• Quantum random walks.

  1993cited by this paper
• Rapid solution of problems by quantum computation

  1992cited by this paper

• Multiparticle quantum walk–based error correction algorithm with two-lattice Bose–Hubbard model

  2022cites this paper
• Quantum walk on the line through potential barriers

  2015cites this paper
• Robust quantum spatial search

  2015cites this paper
• Quantum walk search through potential barriers

  2015influential citation
• Quantum walk on the line through potential barriers

  2015cites this paper