Quick Navigation

Overview Topics Abstract Importance Paper Tools References Reactions Discussion Publication

Topics

Trapped Ion Quantum Computing

Improving the query complexity of quantum spatial search in two dimensions

arXiv
Authors: Abhijith J., Apoorva Patel

Year

2018

Paper ID

23718

Status

Preprint

Abstract Read

~2 min

Abstract Words

113

Citations

N/A

Abstract

The question of whether quantum spatial search in two dimensions can be made optimal has long been an open problem. We report progress towards its resolution by showing that the oracle complexity for target location can be made optimal, by increasing the number of calls to the walk operator that incorporates the graph structure by a logarithmic factor. Our algorithm does not require amplitude amplification. An important ingredient of our algorithm is the implementation of multi-step quantum walks by graph powering, using a coin space of walk-length dependent dimension, which may be of independent interest. Finally, we demonstrate how to implement quantum walks arising from powers of symmetric Markov chains using our methods.

Why This Paper Matters

  • This paper contributes to the Trapped-Ion Quantum Computing research area in the Quantum Articles archive.
  • It adds a 2018 reference point for readers tracking recent quantum research.
  • The question of whether quantum spatial search in two dimensions can be made optimal has long been an open problem.

Paper Tools

Become a member to use research tools

Sign in to open papers, visit source links, share, cite, compare, copy DOI links, request category corrections, and build your reading list.

Become a member Sign in
Show Paper arXiv Publisher Share Cite This Paper Copy URL Compare Copy DOI Add to Reading List Category Correction Request

References & Citation Signals

[1] DOI https://doi.org/arXiv:1810.12600 [2] arXiv https://arxiv.org/abs/1810.12600 [3] Publisher https://arxiv.org/abs/1810.12600

Local Citation Graph (Related-Paper Links)

Current Paper #23718

External citation index: OpenAlex citation signal

Community Reactions

Quick sentiment from readers on this paper.

Score: 0
Likes: 0 Dislikes: 0

Sign in to react to this paper.

Discussion & Reviews (Moderated)

Average Rating: 0.0 / 5 (0 ratings)

No written reviews yet.