Controlled quantum search

K. de Lacy*, L. Noakes, J. Twamley, J. B. Wang

*Corresponding author for this work

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

Quantum searching for one of N marked items in an unsorted database of n items is solved O( √n/N) in steps using Grover’s algorithm. Using nonlinear quantum dynamics with a Gross–Pitaevskii-type quadratic nonlinearity, Childs and Young (Phys Rev A 93:022314, 2016, https://doi.org/10.1103/PhysRevA.93.022314) discovered an unstructured quantum search algorithm with a complexity O(min{1/g log(gn), √n}), which can be used to find a marked item after o(log (n)) repetitions, where g is the nonlinearity strength. In this work we develop an quantum search on a complete graph using a time-dependent nonlinearity which obtains one of the N marked items with certainty. The protocol has runtime O(n/(g √N(n − N))), where g is related to the time-dependent nonlinearity. We also extend the analysis to a quantum search on general symmetric graphs and can greatly simplify the resulting equations when the graph diameter is less than 4.

Original languageEnglish
Article number266
Pages (from-to)1-12
Number of pages12
JournalQuantum Information Processing
Volume17
Issue number10
DOIs
Publication statusPublished - 1 Oct 2018

    Fingerprint

Keywords

  • Control system
  • Gross–Pitaevskii
  • Nonlinear quantum search

Cite this