Optimized quantum random-walk search algorithms

Abstract

Shenvi, Kempe and Whaley's quantum random-walk search (SKW) algorithm [Phys. Rev. A 67, 052307 (2003)] is known to require $O(\sqrt{N})$ number of oracle queries to find the marked element, where $N$ is the size of the search space. The overall time complexity of the SKW algorithm differs from the best achievable on a quantum computer only by a constant factor. We present improvements to the SKW algorithm which yield significant increase in success probability, and an improvement on query complexity such that the theoretical limit of a search algorithm succeeding with probability close to one is reached. We point out which improvement can be applied if there is more than one marked element to find.

7 pages, 2 figures. Major revision according to referee report

References in corpus (10)

• A Quantum Random Walk Search Algorithm
• Grover's quantum searching algorithm is optimal
• Quantum computers can search rapidly by using almost any transformation
• Faster quantum walk algorithm for the two dimensional spatial search
• Optimizing the discrete time quantum walk using a SU(2) coin
• Quantum walks based on an interferometric analogy
• Quantum searches on highly symmetric graphs
• Scattering quantum random-walk search with errors
• Scattering model for quantum random walk on the hypercube
• Quantum search algorithms

Cited by in corpus (50)

• Quantum walks: a comprehensive review
• Photons Walking the Line: A quantum walk with adjustable coin operations
• Two-particle bosonic-fermionic quantum walk via 3D integrated photonics
• Anderson localization of entangled photons in an integrated quantum walk
• On the genesis and evolution of Integrated Quantum Optics
• Photonic quantum walk in a single beam with twisted light
• Quantum walks and wavepacket dynamics on a lattice with twisted photons
• Two-particle quantum walks applied to the graph isomorphism problem
• Quantum Walks
• Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
• Non-interacting multi-particle quantum random walks applied to the graph isomorphism problem for strongly regular graphs
• Quantum search algorithms on a regular lattice
• Single-photon entanglement generation by wavefront shaping in a multiple-scattering medium
• Directional correlations in quantum walks with two particles
• Quantum search on graphene lattices
• Entanglement engineering and topological protection by discrete-time quantum walks
• Localisation, delocalisation, and topological transitions in disordered 2D quantum walks
• Solving the Graph Isomorphism Problem with a Quantum Annealer
• Green's function approach for quantum graphs: an overview
• Quantum walks and quantum search on graphene lattices
• Full-revivals in 2-D Quantum Walks
• Quantum walks as a probe of structural anomalies in graphs
• Finding structural anomalies in star graphs: A general approach
• Finding paths in tree graphs with a quantum walk
• Extraordinary behaviors in two-dimensional decoherent alternative quantum walk
• Asymptotic evolution of quantum walks on the $N$-cycle subject to decoherence on both the coin and position degrees of freedom
• Engineering topological states and quantum-inspired information processing using classical circuits
• Strongly trapped two-dimensional quantum walks
• Finding paths with quantum walks or quantum walking through a maze
• Percolation assisted excitation transport in discrete-time quantum walks
• The quantum walk search algorithm: Factors affecting efficiency
• Quantum walk based state transfer algorithms on the complete M-partite graph
• Finding Structural Anomalies in Star Graphs Using Quantum Walks: A General Approach
• Searches on star graphs and equivalent oracle problems
• Chirality from quantum walks without quantum coin
• Pseudo-Hermitian continuous-time quantum walks
• Doubling the Success of Quantum Walk Search Using Internal-State Measurements
• Optimizing the walk coin in the quantum random walk search algorithm through machine learning
• Lackadaisical quantum walk in the hypercube to search for multiple marked vertices
• Quantum walk state transfer on a hypercube
• Quantum Walks on the Line with Phase Parameters
• Suitable bases for quantum walks with Wigner coins
• Scattering Quantum Random Walks on Square Grids and Randomly Generated Mazes
• Recurrence in discrete-time quantum stochastic walks
• Decoding Quantum Search Advantage: The Critical Role of State Properties in Random Walks
• Search and state transfer between hubs by quantum walks
• Persistence of unvisited sites in quantum walks on a line
• Projection Theorem for Discrete-Time Quantum Walks
• Key graph properties affecting transport efficiency of flip-flop Grover percolated quantum walks
• Strong dispersion property for the quantum walk on the hypercube