Controlled quantum search

DOI10.1007/S11128-018-2031-6MaRDI QIDQ1994702zbMATH OpenOpenAlexWikidataFDO

Authors K. de Lacy, Lyle Noakes, J. Twamley, Jingbo Wang

Publication date 1 November 2018

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

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

zbMATH Keywords

control systemGross-Pitaevskiinonlinear quantum search

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Searching and sorting (68P10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum computation (81P68) Quantum control (81Q93) Stochastic systems in control theory (general) (93E03)

Abstract: Quantum searching for one of $N$ marked items in an unsorted database of $n$ items is solved in $mathcalO(sqrtn/N)$ steps using Grover's algorithm. Using nonlinear quantum dynamics with a Gross-Pitaevskii type quadratic nonlinearity, Childs and Young discovered an unstructured quantum search algorithm with a complexity $mathcalO(min1/g,log(gn),sqrtn)$, which can be used to find a marked item after $o(log(n))$ repetitions, where $g$ is the nonlinearity strength [PhysRevA.93.022314]. In this work we develop a structured search on a complete graph using a time dependent nonlinearity which obtains one of the $N$ marked items with certainty. The protocol has runtime $mathcalO((N^{perp}-N)/(GsqrtN{N}^{perp}))if{N}^{perp}>N$, where $N^{perp}$ denotes the number of unmarked items and $G$ is related to the time dependent nonlinearity. If $N^{perp}leqN$, we obtain a runtime $mathcalO(1)$. 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 5.

Recommendations

• Nonlinear quantum search using the Gross–Pitaevskii equation
• Nonadiabatic quantum search algorithms
• An exact quantum search algorithm with arbitrary database
• Graph comparison via nonlinear quantum search
• Unstructured adiabatic quantum search

Cites work

• Nonlinear quantum search using the Gross–Pitaevskii equation
• Quantum feedback control of linear stochastic systems with feedback-loop time delays
• Strengths and Weaknesses of Quantum Computing

Cited in

(7)

• Nonadiabatic quantum search algorithm with analytical success rate
• Graph comparison via nonlinear quantum search
• Quantum search in structured database using local adiabatic evolution and spectral methods
• Nonadiabatic quantum search algorithms
• Continuous-time quantum search and time-dependent two-level quantum systems
• Dynamical Controls for Improving Quantum Search Algorithm Through Flux Qubits System
• Noisy Effect on Nonlinear Quantum Search Algorithm

This page was built for publication: Controlled quantum search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1994702)