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

arXiv:2609.34293

Optimal Quantum Algorithms for Ordered Search

Joseph Carolan, Andrew M. Childs

quant-phSubmitted Sep 28, 2026• Announced Sep 29, 2026• 0 citations
arXivHTMLPDF

Abstract

Ordered search is the problem of locating a target element in a sorted list of size $n$ using comparison queries. Classically, binary search requires $\lceil \log_2 n\rceil$ queries, which is optimal. Quantum algorithms offer a constant-factor speedup, but the precise constant has been a longstanding open question. We close this gap by exhibiting two new quantum algorithms for ordered search, each using the optimal $\frac{1}π\ln n+o(\log n)$ queries. The first, discovered by Claude Fable 5, is a simple zero-error algorithm derived from a continuum relaxation of the problem. The second, discovered by GPT-5.6-Sol (informed by Claude's zero-error algorithm), is an exact algorithm based on an analytic solution of the polynomial program of Farhi, Goldstone, Gutmann, and Sipser.

Related papers

Translation-Invariant Quantum Algorithms for Ordered Search are Optimal

Joseph Carolan, Andrew M. Childs, Matt Kovacs-Deak +1 more

Ordered search is the task of finding an item in an ordered list using comparison queries. The best exact classical algorithm for this fundamental problem uses \(\lceil \log _{2}{n}\rceil\) queries for a list of length n . Quantum computers can achieve a constant-factor speedup, but the best possible coefficient of \(\log _{2}{n}\) for exact quantum algorithms is only known to lie between \((\ln {2})/\pi \approx 0.221\) and \(4/\log _{2}{605} \approx 0.433\) . We consider a special class of translation-invariant algorithms with no workspace, introduced by Farhi, Goldstone, Gutmann, and Sipser, that has been used to find the best known upper bounds. First, we show that any bounded-error, k -query quantum algorithm for ordered search can be implemented by a k -query algorithm in this special class. Second, we use linear programming to show that the best exact 5-query quantum algorithm can search a list of length 7265, giving an ordered search algorithm that asymptotically uses \(5 \log _{7265}{n} \approx 0.390 \log _{2}{n}\) quantum queries.

arXiv:2503.21090•ACM Transactions on Quantum Computing•Mar 12, 2026•2 citations

Quantum algorithms for the ordered search problem via semidefinite programming

Andrew M. Childs, Andrew J. Landahl, Pablo A. Parrilo

One of the most basic computational problems is the task of finding a desired item in an ordered list of $N$ items. While the best classical algorithm for this problem uses ${\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}N$ queries to the list, a quantum computer can solve the problem using a constant factor fewer queries. However, the precise value of this constant is unknown. By characterizing a class of quantum query algorithms for the ordered search problem in terms of a semidefinite program, we find quantum algorithms for small instances of the ordered search problem. Extending these algorithms to arbitrarily large instances using recursion, we show that there is an exact quantum ordered search algorithm using $4\phantom{\rule{0.2em}{0ex}}{\mathrm{log}}_{605}\phantom{\rule{0.2em}{0ex}}N\ensuremath{\approx}0.433\phantom{\rule{0.2em}{0ex}}{\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}N$ queries, which improves upon the previously best known exact algorithm.

arXiv:quant-ph/0608161•Physical Review A•Mar 26, 2007•46 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

Quantum Search in an Ordered List via Adaptive Learning

Michael Ben-Or, Avinatan Hassidim

We use a Bayesian approach to optimally solve problems in noisy binary search. We deal with two variants: 1. Each comparison can be erroneous with some probability $1 - p$. 2. At each stage $k$ comparisons can be performed in parallel and a noisy answer is returned We present a (classic) algorithm which optimally solves both variants together, up to an additive term of O(\log \log(n)), and prove matching information theoretic lower bounds. We use the algorithm to improve the results of Farhi et al \cite{FGGS99} presenting a quantum (error free) search algorithm in an ordered list of expected complexity less than (\log_2n) / 3.

arXiv:quant-ph/0703231•Mar 24, 2007•12 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•41 citations

Bounds on quantum ordered searching

Peter Høyer, Jan Neerbek

We prove that any exact quantum algorithm searching an ordered list of N elements requires more than \frac{1}π(\ln(N)-1) queries to the list. This improves upon the previously best known lower bound of {1/12}\log_2(N) - O(1). Our proof is based on a weighted all-pairs inner product argument, and it generalizes to bounded-error quantum algorithms. The currently best known upper bound for exact searching is roughly 0.526 \log_2(N). We give an exact quantum algorithm that uses \log_3(N) + O(1) queries, which is roughly 0.631 \log_2(N). The main principles in our algorithm are an quantum parallel use of the classical binary search algorithm and a method that allows basis states in superpositions to communicate.

arXiv:quant-ph/0009032•Sep 8, 2000•3 citations
Ordered search is the problem of locating a target element in a sorted list of size nnn using comparison queries. Classically, binary search requires ⌈log⁡2n⌉\lceil \log_2 n\rceil⌈log2​n⌉ queries, which is optimal. Quantum algorithms offer a constant-factor speedup, but the precise constant has been a longstanding open question. We close this gap by exhibiting two new quantum algorithms for ordered search, each using the optimal 1πln⁡n+o(log⁡n)\frac{1}π\ln n+o(\log n)π1​lnn+o(logn) queries. The first, discovered by Claude Fable 5, is a simple zero-error algorithm derived from a continuum relaxation of the problem. The second, discovered by GPT-5.6-Sol (informed by Claude's zero-error algorithm), is an exact algorithm based on an analytic solution of the polynomial program of Farhi, Goldstone, Gutmann, and Sipser.
Ordered search is the task of finding an item in an ordered list using comparison queries. The best exact classical algorithm for this fundamental problem uses ⌈log⁡2n⌉\lceil \log _{2}{n}\rceil⌈log2​n⌉ queries for a list of length n . Quantum computers can achieve a constant-factor speedup, but the best possible coefficient of log⁡2n\log _{2}{n}log2​n for exact quantum algorithms is only known to lie between (ln⁡2)/π≈0.221(\ln {2})/\pi \approx 0.221(ln2)/π≈0.221 and 4/log⁡2605≈0.4334/\log _{2}{605} \approx 0.4334/log2​605≈0.433 . We consider a special class of translation-invariant algorithms with no workspace, introduced by Farhi, Goldstone, Gutmann, and Sipser, that has been used to find the best known upper bounds. First, we show that any bounded-error, k -query quantum algorithm for ordered search can be implemented by a k -query algorithm in this special class. Second, we use linear programming to show that the best exact 5-query quantum algorithm can search a list of length 7265, giving an ordered search algorithm that asymptotically uses 5log⁡7265n≈0.390log⁡2n5 \log _{7265}{n} \approx 0.390 \log _{2}{n}5log7265​n≈0.390log2​n quantum queries.
One of the most basic computational problems is the task of finding a desired item in an ordered list of NNN items. While the best classical algorithm for this problem uses log2N{\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}Nlog2​N queries to the list, a quantum computer can solve the problem using a constant factor fewer queries. However, the precise value of this constant is unknown. By characterizing a class of quantum query algorithms for the ordered search problem in terms of a semidefinite program, we find quantum algorithms for small instances of the ordered search problem. Extending these algorithms to arbitrarily large instances using recursion, we show that there is an exact quantum ordered search algorithm using $4\phantom{\rule{0.2em}{0ex}}{\mathrm{log}}_{605}\phantom{\rule{0.2em}{0ex}}N\ensuremath{\approx}0.433\phantom{\rule{0.2em}{0ex}}{\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}N$ queries, which improves upon the previously best known exact algorithm.
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 use a Bayesian approach to optimally solve problems in noisy binary search. We deal with two variants: 1. Each comparison can be erroneous with some probability 1−p1 - p1−p. 2. At each stage kkk comparisons can be performed in parallel and a noisy answer is returned We present a (classic) algorithm which optimally solves both variants together, up to an additive term of O(\log \log(n)), and prove matching information theoretic lower bounds. We use the algorithm to improve the results of Farhi et al \cite{FGGS99} presenting a quantum (error free) search algorithm in an ordered list of expected complexity less than (\log_2n) / 3.
We prove that any exact quantum algorithm searching an ordered list of N elements requires more than \frac{1}π(\ln(N)-1) queries to the list. This improves upon the previously best known lower bound of {1/12}\log_2(N) - O(1). Our proof is based on a weighted all-pairs inner product argument, and it generalizes to bounded-error quantum algorithms. The currently best known upper bound for exact searching is roughly 0.526 \log_2(N). We give an exact quantum algorithm that uses \log_3(N) + O(1) queries, which is roughly 0.631 \log_2(N). The main principles in our algorithm are an quantum parallel use of the classical binary search algorithm and a method that allows basis states in superpositions to communicate.