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.
| Language | English |
|---|---|
| Article number | 266 |
| Pages | 1-12 |
| Number of pages | 12 |
| Journal | Quantum Information Processing |
| Volume | 17 |
| Issue number | 10 |
| DOIs | |
| Publication status | Published - 1 Oct 2018 |
Fingerprint
Keywords
- Control system
- Gross–Pitaevskii
- Nonlinear quantum search
Cite this
}
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 journal › Article › Research › peer-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 -