Matrix-Free GPU Semidefinite Programming for Quantum Ordered Search at the k=6 Frontier

Quantum computation offers the potential for a significant constant-factor speedup for the Ordered Search Problem (OSP). A classical construction is the $k$-query quantum ordered search algorithm, which can exactly search an $N$-element ordered list and achieves a query complexity improvement of a factor of $\frac{k}{\log_2 N}$. For larger $k$, stronger constant-factor improvements could be obtained by finding the largest admissible list size $N^\star$, a task that can be formulated as a structured semidefinite program (SDP). However, solving this SDP becomes computationally intractable beyond $k=6$, as existing CPU and GPU solvers rely on explicit construction of prohibitively large constraint matrices. In this paper, we introduce a matrix-free GPU SDP framework that evaluates the highly structured constraints in OSP on-the-fly using custom CUDA kernels, reducing memory complexity from quadratic to linear and shifting the bottleneck from memory to computation. Using this approach, we provide strong numerical evidence that the optimal list size for $k=6$ is at least $90,000$, improving the empirical upper bound on the query coefficient from $0.390$ to $0.365$. We further rigorously certify the upper bound $N^\star < 94,000$ by constructing dual infeasibility certificates via matrix-free minimum-eigenvalue estimation.

Quantum computers can solve ordered search, the task behind binary search in a sorted list, with fewer queries than ordinary computers. They cannot fundamentally change the fact that the number of queries grows logarithmically with the list size, but they can improve the constant factor in front of this growth. Understanding the best possible constant factor is a central question in quantum algorithms. One way to make progress is to fix the number of quantum queries and determine the largest list that can be searched exactly. This question can be converted into a large optimization problem. For six quantum queries, this optimization problem becomes too large for existing solvers, because they need to store enormous matrices. We develop a GPU-based method that avoids storing these matrices explicitly. Instead, it computes their effects only when needed, using the special structure of ordered search. This makes it possible to study instances that were previously beyond reach on a single GPU. As a numerical result, our method finds strong evidence that six quantum queries can search a list of 90,000 items. We also rigorously certify that 94,000 items cannot be searched with six queries. Together, these results improve the best known constructive bound on the speedup achievable by exact quantum ordered search and demonstrate a practical way to scale structured optimization problems in quantum algorithms.