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

European Control Conference (ECC)

Finding quantum algorithms via convex optimization

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

Published Jul 1, 2007• 0 citations
Publisher

Abstract

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.

DOI
10.23919/ecc.2007.7069011

Related papers

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 algorithms and lower bounds for convex optimization

Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li +1 more

While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function over an n -dimensional convex body using O ~ ( n ) queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the best-known classical algorithm. We also study limitations on the power of quantum computers for general convex optimization, showing that it requires Ω ~ ( n ) evaluation queries and Ω ( n ) membership queries.

arXiv:1809.01731•Quantum•Jan 13, 2020•43 citations

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

An Improved Quantum Algorithm for Searching an Ordered List

Brian Jacokes

The best known quantum algorithm for searching an ordered list of N items is recursive and requires 3 log52 N ≈ 0.526 log2 N queries. We find an improved base case for this recursion, yielding an algorithm that requires only 4 log434 N ≈ 0.457 log2 N queries. This algorithm is more than twice as fast as the best possible classical algorithm, which requires log2 N queries.

•Jan 1, 2007•7 citations

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

On quantum algorithms and limitations for convex optimization and lattice problems

Y. Chen

Optimization is the process of selecting the best option from all possibilities, and problems related to finding the best option among many options are called optimization problems. A few examples of such problems are route picking, partial loading, crew scheduling, and portfolio optimization, and those problems naturally appear everywhere in society and in our daily lives. Most optimization problems could be solved by listing all possibilities and then searching for the best one, but we aim to find a systematic strategy (known as an algorithm) that finds the optimal solution in the least amount of time, as brute-force searching is often too time-consuming. That is, we would like to find optimal algorithms for finding optimal solutions. Quantum physics provides a more accurate explanation and prediction of nature in many cases than classical physics. Therefore, a quantum computer has the potential to be more powerful and useful than a classical one for solving optimization problems, though the extent of this advantage remains an active area of research. Moreover, designing algorithms for a quantum computer requires fundamentally different ideas and concepts than for a classical computer. In this thesis, we explore the uses of quantum computers in solving several fundamental optimization problems. We specifically consider solving linear regression, finding the top eigenvectors of a matrix, and finding the shortest nonzero vector of a lattice. More precisely, we provide near-optimal quantum algorithms that are asymptotically better than the best-possible classical algorithms for linear regression with $\ell_1$-norm constraint (known as Lasso) and for approximating the top eigenvectors of a matrix. Our algorithms for finding the shortest nonzero vector of a lattice are asymptotically better than the best known classical algorithms. On the other hand, there are some problems for which no useful computational advantage is possible, even when we use quantum computers. This situation, however, can sometimes be beneficial if we do not want quantum computers to solve specific problems fast - say, problems relevant to post-quantum cryptography. In such a situation, we would like evidence demonstrating the difficulty of solving these problems on a quantum computer. To this end, we propose variants of Boolean satisfiability problems that are believed to not be more efficiently solvable on a quantum computer, and then via reductions use those (conjectured) quantum lower bounds to study the quantum limitations of several popular optimization problems like lattice problems, quantum strong simulation, and hitting set problems.

•Jan 1, 2024•0 citations
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.
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.
While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function over an n -dimensional convex body using O ~ ( n ) queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the best-known classical algorithm. We also study limitations on the power of quantum computers for general convex optimization, showing that it requires Ω ~ ( n ) evaluation queries and Ω ( n ) membership 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.
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.
Optimization is the process of selecting the best option from all possibilities, and problems related to finding the best option among many options are called optimization problems. A few examples of such problems are route picking, partial loading, crew scheduling, and portfolio optimization, and those problems naturally appear everywhere in society and in our daily lives. Most optimization problems could be solved by listing all possibilities and then searching for the best one, but we aim to find a systematic strategy (known as an algorithm) that finds the optimal solution in the least amount of time, as brute-force searching is often too time-consuming. That is, we would like to find optimal algorithms for finding optimal solutions. Quantum physics provides a more accurate explanation and prediction of nature in many cases than classical physics. Therefore, a quantum computer has the potential to be more powerful and useful than a classical one for solving optimization problems, though the extent of this advantage remains an active area of research. Moreover, designing algorithms for a quantum computer requires fundamentally different ideas and concepts than for a classical computer. In this thesis, we explore the uses of quantum computers in solving several fundamental optimization problems. We specifically consider solving linear regression, finding the top eigenvectors of a matrix, and finding the shortest nonzero vector of a lattice. More precisely, we provide near-optimal quantum algorithms that are asymptotically better than the best-possible classical algorithms for linear regression with ℓ1\ell_1ℓ1​-norm constraint (known as Lasso) and for approximating the top eigenvectors of a matrix. Our algorithms for finding the shortest nonzero vector of a lattice are asymptotically better than the best known classical algorithms. On the other hand, there are some problems for which no useful computational advantage is possible, even when we use quantum computers. This situation, however, can sometimes be beneficial if we do not want quantum computers to solve specific problems fast - say, problems relevant to post-quantum cryptography. In such a situation, we would like evidence demonstrating the difficulty of solving these problems on a quantum computer. To this end, we propose variants of Boolean satisfiability problems that are believed to not be more efficiently solvable on a quantum computer, and then via reductions use those (conjectured) quantum lower bounds to study the quantum limitations of several popular optimization problems like lattice problems, quantum strong simulation, and hitting set problems.