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:2503.21090 · ACM Transactions on Quantum Computing

Translation-Invariant Quantum Algorithms for Ordered Search are Optimal

Joseph Carolan, Andrew M. Childs, Matt Kovacs-Deak, Luke Schaeffer

Published Mar 12, 2026• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1145/3800579

Related papers

Optimal Quantum Algorithms for Ordered Search

Joseph Carolan, Andrew M. Childs

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.

quant-pharXiv:2609.34293•Sep 29, 2026•0 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

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

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

Invariant Quantum Algorithms for Insertion into an Ordered List

Edward Farhi, Jeffrey Goldstone, Sam Gutmann +1 more

We consider the problem of inserting one item into a list of N-1 ordered items. We previously showed that no quantum algorithm could solve this problem in fewer than log N/(2 log log N) queries, for N large. We transform the problem into a "translationally invariant" problem and restrict attention to invariant algorithms. We construct the "greedy" invariant algorithm and show numerically that it outperforms the best classical algorithm for various N. We also find invariant algorithms that succeed exactly in fewer queries than is classically possible, and iterating one of them shows that the insertion problem can be solved in fewer than 0.53 log N quantum queries for large N (where log N is the classical lower bound). We don't know whether a o(log N) algorithm exists.

arXiv:quant-ph/9901059•Jan 19, 1999•36 citations

Finding quantum algorithms via convex optimization

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

In this paper we describe how to use convex optimization to design quantum algorithms for certain computational tasks. In particular, we consider the ordered search problem, where it is desired to find a specific item in an ordered list of N items. While the best classical algorithm for this problem uses log2N queries to the list, a quantum computer can solve this problem much faster. By characterizing a class of quantum query algorithms for ordered search in terms of a semidefinite program, we find quantum algorithms using 4log605N ≈ 0.433 log2N queries, which improves upon the previously best known exact algorithm.

European Control Conference (ECC)•Jul 1, 2007•0 citations
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.
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.
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 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.
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 consider the problem of inserting one item into a list of N-1 ordered items. We previously showed that no quantum algorithm could solve this problem in fewer than log N/(2 log log N) queries, for N large. We transform the problem into a "translationally invariant" problem and restrict attention to invariant algorithms. We construct the "greedy" invariant algorithm and show numerically that it outperforms the best classical algorithm for various N. We also find invariant algorithms that succeed exactly in fewer queries than is classically possible, and iterating one of them shows that the insertion problem can be solved in fewer than 0.53 log N quantum queries for large N (where log N is the classical lower bound). We don't know whether a o(log N) algorithm exists.
In this paper we describe how to use convex optimization to design quantum algorithms for certain computational tasks. In particular, we consider the ordered search problem, where it is desired to find a specific item in an ordered list of N items. While the best classical algorithm for this problem uses log2N queries to the list, a quantum computer can solve this problem much faster. By characterizing a class of quantum query algorithms for ordered search in terms of a semidefinite program, we find quantum algorithms using 4log605N ≈ 0.433 log2N queries, which improves upon the previously best known exact algorithm.