Optimal Quantum Algorithms for Ordered Search
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 ⌈ 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) 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
- Circuit-depth optimization of quantum partial-search algorithms
- When is global evolutionary search useful for variational quantum algorithms? A landscape-first study
- Near-Optimal Bounds on the Density of Low-Energy States of k-Local Hamiltonians and Faster Quantum Algorithms
- Quantum algorithms for optimal control: large-scale finite-horizon linear-quadratic regulation
- Optimal inequalities for completely bounded polynomials and the limitations of quantum query algorithms
BibTeX
@misc{carolan2026optimal,
title = {{Optimal Quantum Algorithms for Ordered Search}},
author = {Joseph Carolan and Andrew M. Childs},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.34293},
eprint = {2609.34293},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.34293},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Quantum Algorithms for Ordered Search
AU - Joseph Carolan
AU - Andrew M. Childs
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.34293
UR - https://arxiv.org/abs/2609.34293
AB - Ordered search is the problem of locating a target element in a sorted list of size n using comparison queries. Classically, binary search requires ⌈ log_2 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) 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.
ER -