Robust quantum spatial search

DOI10.1007/S11128-016-1322-ZMaRDI QIDQ331506zbMATH OpenOpenAlexFDO

Authors Avatar Tulsi

Publication date 27 October 2016

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

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

zbMATH Keywords

quantum spatial searchrecursive spatial searchrobust spatial searchsystematic errors

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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
• Quantum walks on hypergraphs
• scientific article; zbMATH DE number 2103521 (Why is no real title available?)

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)