Robust quantum spatial search

DOI10.1007/S11128-016-1322-ZzbMATH Open1348.81184arXiv1508.00207OpenAlexW2342160560MaRDI QIDQ331506FDOQ331506

Authors: Avatar Tulsi 

Publication date: 27 October 2016

Published in: Quantum Information Processing (Search for Journal in Brave)

Abstract: Quantum spatial search has been widely studied with most of the study focusing on quantum walk algorithms. We show that quantum walk algorithms are extremely sensitive to systematic errors. We present a recursive algorithm which offers significant robustness to certain systematic errors. To search N items, our recursive algorithm can tolerate errors of size O(1/sqrt{ln N}) which is exponentially better than quantum walk algorithms for which tolerable error size is only O(ln N/sqrt{N}). Also, our algorithm does not need any ancilla qubit. Thus our algorithm is much easier to implement experimentally compared to quantum walk algorithms.

Full work available at URL: https://arxiv.org/abs/1508.00207

Recommendations

• Faster quantum-walk algorithm for the two-dimensional spatial search
• Spatial search using the discrete time quantum walk
• Gate imperfection in the quantum random-walk search algorithm
• Spatial quantum search in a triangular network
• Spatial search on a honeycomb network

zbMATH Keywords

quantum spatial searchrecursive spatial searchrobust spatial searchsystematic errors

Mathematics Subject Classification ID

Searching and sorting (68P10) Quantum computation (81P68)

Cites Work

• Faster quantum-walk algorithm for the two-dimensional spatial search
• Coins make quantum walks faster
• Quantum search of spatial regions
• Quantum random walks do not need a coin toss
• Spatial search and the Dirac equation
• Quantum walk search through potential barriers
• Reliable quantum computers
• Strengths and Weaknesses of Quantum Computing
• Search on a hypercubic lattice using a quantum random walk. II. \(d=2\)
• Spatial search on a honeycomb network
• Phase matching in quantum searching.
• Search by quantum walks on two-dimensional grid without amplitude amplification
• Title not available (Why is that?)
• Search on a hypercubic lattice using a quantum random walk. I. \(d>2\)
• Gate imperfection in the quantum random-walk search algorithm

Cited In (5)

• Robustness of quantum walk search with neighbors measurement
• Vertices cannot be hidden from quantum spatial search for almost all random graphs
• Impact of the malicious input data modification on the efficiency of quantum spatial search
• Title not available (Why is that?)
• Quantum walks on hypergraphs

This page was built for publication: Robust quantum spatial search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q331506)