MathDB

Quantum query complexity of high-accuracy convex optimization

Let EnE_n be the explicit family of nn-dimensional ellipsoids considered in the cited problem, accessed through a membership oracle. Determine the quantum membership-query complexity of producing, for every c∈Rnc\in\mathbb{R}^n with ∥c∥2=1\|c\|_2=1, a point xx satisfying x∈Enx\in E_n and cTx≥max⁡y∈EncTy−Θ(n−2)c^{\mathsf T}x\geq\max_{y\in E_n}c^{\mathsf T}y-\Theta(n^{-2}). In particular, determine whether every such quantum algorithm requires Ω(n)\Omega(n) membership queries, closing the remaining logarithmic gap between the known near-linear lower bound and the best upper bounds. The analogous question may also be posed when xx is required only to have distance at most Θ(n−2)\Theta(n^{-2}) from EnE_n.

References

Primary source

arXiv

Additional references

complexity-theoryconvex-optimizationquantum-computingquery-complexity
Posted

Progress summary

Refreshed
Claimed progress

A new unrefereed preprint nearly matches the best known quantum algorithms, but a logarithmic-sized gap remains.

The problem concerns the number of quantum queries required for highly accurate convex optimization. The latest work also treats related determinant, eigenvalue, and gradient-query problems.

September 2026 lower-bound advance

A manuscript posted by its authors supplies near-linear lower bounds for membership-oracle optimization and related problems, substantially narrowing the gap with known upper bounds. It does not close the remaining polylogarithmic gap, and the manuscript is unrefereed.

Current status (as of September 2026): Near-linear lower bounds are claimed for the main and related query models, but the exact quantum query complexity remains open because a polylogarithmic gap persists and the manuscript has not been refereed.

Sources

Solutions 0

No solutions have been posted yet.