Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Information Processing Letters

A lower bound for quantum search of an ordered list

Harry Buhrman, Ronald de Wolf

Published Jun 1, 1999• 18 citations
Publisher
DOI
10.1016/s0020-0190(99)00069-1

Related papers

Optimal Quantum Adversary Lower Bounds for Ordered Search

Andrew M. Childs, Troy Lee

arXiv:0708.3396•Lecture notes in computer science•Jan 1, 2008•20 citations

Quantum bounds for ordered searching and sorting

Peter Høyer, Jan Neerbek, Yaoyun Shi

We consider the quantum complexities of searching an ordered list and sorting an un-ordered list. For searching an ordered list of N elements, we prove a lower bound of \\frac{1}{\\pi}(\\ln(N)-1) on the number of oracle queries that access the list elements. This improves the previously best lower bound of ({1/12}\\log_2(N) - O(1)) due to Ambainis. For sorting N numbers, we prove a lower bound of \\frac{N}{2\\pi}(\\ln(N)-1) on the number of binary comparisons. The previously best lower bound is \\Omega(N). Our proofs are based on a weighted all-pairs inner product argument, and our results generalize to bounded error quantum algorithms. Both results are proven in the so-called quantum black box model, a quantum analogue of classical decision trees. In addition to our lower bound results, we give an exact quantum algorithm for ordered searching using (\\log_3(N) + O(1)) queries, which is roughly 0.631 \\log_2(N). Although our algorithm is worse than that of Farhi, Goldstone, Gutmann and Sipser, which makes 0.526 \\log_2(N) queries, its philosophy is completely different. Our algorithm is a quantum version of the classical binary search algorithm, and it uses a quantum routine for traversing through a binary search tree faster than classically.

•Feb 15, 2001•3 citations

A better lower bound for quantum algorithms searching an ordered list

Andris Ambainis

We show that any quantum algorithm searching an ordered list of n elements needs to examine at least (log,n)/12-O(1) of them. Classically, log/sub 2/ n queries are both necessary and sufficient. This shows that quantum algorithms can achieve only a constant speedup for this problem.

arXiv:quant-ph/9902053•Annual Symposium on Foundations of Computer Science•Jan 20, 2003•50 citations

An alternate algorithm for directed quantum search

Tathagat Tulsi, Lov K. Grover, Apoorva D. Patel

•May 2, 2005•0 citations

A Modified Quantum Search Algorithm

Hossein Mehri‐Dehnavi, Hasan Dashtianeh, Hossein Yahyavi Kuchaksaraei +3 more

International Journal of Theoretical Physics•Sep 7, 2018•6 citations

Lower Bounds for Quantum Search and Derandomization

Harry Buhrman, Ronald de Wolf

We prove lower bounds on the error probability of a quantum algorithm for searching through an unordered list of N items, as a function of the number T of queries it makes. In particular, if T=O(sqrt{N}) then the error is lower bounded by a constant. If we want error <1/2^N then we need T=Omega(N) queries. We apply this to show that a quantum computer cannot do much better than a classical computer when amplifying the success probability of an RP-machine. A classical computer can achieve error <=1/2^k using k applications of the RP-machine, a quantum computer still needs at least ck applications for this (when treating the machine as a black-box), where c>0 is a constant independent of k. Furthermore, we prove a lower bound of Omega(sqrt{log N}/loglog N) queries for quantum bounded-error search of an ordered list of N items.

arXiv:quant-ph/9811046•Nov 18, 1998•18 citations
We consider the quantum complexities of searching an ordered list and sorting an un-ordered list. For searching an ordered list of N elements, we prove a lower bound of \\frac{1}{\\pi}(\\ln(N)-1) on the number of oracle queries that access the list elements. This improves the previously best lower bound of ({1/12}\\log_2(N) - O(1)) due to Ambainis. For sorting N numbers, we prove a lower bound of \\frac{N}{2\\pi}(\\ln(N)-1) on the number of binary comparisons. The previously best lower bound is \\Omega(N). Our proofs are based on a weighted all-pairs inner product argument, and our results generalize to bounded error quantum algorithms. Both results are proven in the so-called quantum black box model, a quantum analogue of classical decision trees. In addition to our lower bound results, we give an exact quantum algorithm for ordered searching using (\\log_3(N) + O(1)) queries, which is roughly 0.631 \\log_2(N). Although our algorithm is worse than that of Farhi, Goldstone, Gutmann and Sipser, which makes 0.526 \\log_2(N) queries, its philosophy is completely different. Our algorithm is a quantum version of the classical binary search algorithm, and it uses a quantum routine for traversing through a binary search tree faster than classically.
We prove lower bounds on the error probability of a quantum algorithm for searching through an unordered list of N items, as a function of the number T of queries it makes. In particular, if T=O(sqrt{N}) then the error is lower bounded by a constant. If we want error <1/2^N then we need T=Omega(N) queries. We apply this to show that a quantum computer cannot do much better than a classical computer when amplifying the success probability of an RP-machine. A classical computer can achieve error <=1/2^k using k applications of the RP-machine, a quantum computer still needs at least ck applications for this (when treating the machine as a black-box), where c>0 is a constant independent of k. Furthermore, we prove a lower bound of Omega(sqrt{log N}/loglog N) queries for quantum bounded-error search of an ordered list of N items.