Controlled quantum search

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

Research output: Contribution to journalArticleResearchpeer-review

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.

LanguageEnglish
Article number266
Pages1-12
Number of pages12
JournalQuantum Information Processing
Volume17
Issue number10
DOIs
Publication statusPublished - 1 Oct 2018

Fingerprint

nonlinearity
Nonlinearity
Symmetric Graph
Quantum Algorithms
Quantum Dynamics
Gross
Complete Graph
Nonlinear Dynamics
Search Algorithm
repetition
Simplify
Graph in graph theory

Keywords

  • Control system
  • Gross–Pitaevskii
  • Nonlinear quantum search

Cite this

de Lacy, K. ; Noakes, L. ; Twamley, J. ; Wang, J. B. / Controlled quantum search. In: Quantum Information Processing. 2018 ; Vol. 17, No. 10. pp. 1-12.
@article{ccb14b966424411b8d3d8ce0f3a89a02,
title = "Controlled quantum search",
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.",
keywords = "Control system, Gross–Pitaevskii, Nonlinear quantum search",
author = "{de Lacy}, K. and L. Noakes and J. Twamley and Wang, {J. B.}",
year = "2018",
month = "10",
day = "1",
doi = "10.1007/s11128-018-2031-6",
language = "English",
volume = "17",
pages = "1--12",
journal = "Quantum Information Processing",
issn = "1570-0755",
publisher = "Springer, Springer Nature",
number = "10",

}

de Lacy, K, Noakes, L, Twamley, J & Wang, JB 2018, 'Controlled quantum search' Quantum Information Processing, vol. 17, no. 10, 266, pp. 1-12. https://doi.org/10.1007/s11128-018-2031-6

Controlled quantum search. / de Lacy, K.; Noakes, L.; Twamley, J.; Wang, J. B.

In: Quantum Information Processing, Vol. 17, No. 10, 266, 01.10.2018, p. 1-12.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Controlled quantum search

AU - de Lacy,K.

AU - Noakes,L.

AU - Twamley,J.

AU - Wang,J. B.

PY - 2018/10/1

Y1 - 2018/10/1

N2 - 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.

AB - 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.

KW - Control system

KW - Gross–Pitaevskii

KW - Nonlinear quantum search

UR - http://www.scopus.com/inward/record.url?scp=85052558442&partnerID=8YFLogxK

U2 - 10.1007/s11128-018-2031-6

DO - 10.1007/s11128-018-2031-6

M3 - Article

VL - 17

SP - 1

EP - 12

JO - Quantum Information Processing

T2 - Quantum Information Processing

JF - Quantum Information Processing

SN - 1570-0755

IS - 10

M1 - 266

ER -