 Author
 Date
 32017
 Title
 Optimizing the Number of Gates in Quantum Search
 Journal
 Quantum Information and Computation
 Volume  Issue number
 17  3&4
 Pages (fromto)
 251261
 Document type
 Article
 Faculty
 Interfacultary Research Institutes
 Institute
 Institute for Logic, Language and Computation (ILLC)
 Abstract

In its usual form, Grover's quantum search algorithm uses $O(\sqrt{N})$ queries and $O(\sqrt{N} \log N)$ other elementary gates to find a solution in an $N$bit database. Grover in 2002 showed how to reduce the number of other gates to $O(\sqrt{N}\log\log N)$ for the special case where the database has a unique solution, without significantly increasing the number of queries. We show how to reduce this further to $O(\sqrt{N}\log^{(r)} N)$ gates for every constant~$r$, and sufficiently large~$N$. This means that, on average, the circuits between two queries barely touch more than a constant number of the $\log N$ qubits on which the algorithm acts. For a very large $N$ that is a power of~2, we can choose~$r$ such that the algorithm uses essentially the minimal number $\frac{\pi}{4}\sqrt{N}$ of queries, and only $O(\sqrt{N}\log(\log^{\star} N))$ other gates.
 URL
 go to publisher's site
 Link
 Final publisher version
 Language
 English
 Permalink
 http://hdl.handle.net/11245.1/67343f474a61427983d56c56519a3cd3
 Downloads
Disclaimer/Complaints regulations
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.